function [L,s] = apriori(X, s_min)

m = size(X,2); % number/size of instances
C = speye(m);  % candidates (intialization: candidates of size 1)
L = {};        % frequent itemsets
s = {};        % support

for k = 1:m
    % frequent itemsets of size k
    L{k}  = sparse(0, m);
    s{k}  = [];
    C_new = sparse(0, m);
    for i = 1:size(C, 1)
        si = support(X, C(i,:));
        if si >= s_min
            % q_j = number of equal entries of i-th candidate and j-the 
            % frequent itemset of size k
            q = C(i,:) * L{k}';
            for j = find(q == k-1)
                % candidate of size k + 1
                c = L{k}(j,:) | C(i,:);
                if ~any(C_new*c' == k + 1)
                    % new candidate (does not exist in C_new)
                    C_new(end+1,:) = c;
                end
            end
            L{k}(end+1,:) = C(i,:);
            s{k}(end+1)   = si;
        end
    end
    if size(C_new, 1) == 0
        % no new candidates
        break
    end
    C = C_new;
end

L = cell2mat(L');
s = cell2mat(s)';
if ~isempty(s)
    [s,i] = sort(s, 'descend');
    L = L(i,:);
end
