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

[n,m] = size(X);        % number/size of instances
k_max = m;              % maximal size of itemsets
C     = speye(m);       % candidates (intialization: candidates of size 1)
L     = {sparse(0, m)}; % frequent itemsets
s     = {};             % support

for k = 1:k_max
    % 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
            % find(L{k} * C(i,:)' == k-1): itemesets, die in k-1 elementen übereinstimmen
            % hole mir die liste der frequent item sets, mit denen ich die
            % aktuelle verschmelzen kann, damit ein frequent itemset der
            % länge k +1 entsteht
            p = find(L{k} * C(i,:)' == k-1);
            for j = 1:length(p)
                % candidate of size k + 1
                c = L{k}(p(j),:) | C(i,:); % |: veroderung von matrizen
                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
