Fastest solution for all possible combinations, taking k elements out of n possible with k>2 and n large

Question

I am using MATLAB to find all of the possible combinations of k elements out of n possible elements. I stumbled across this question, but unfortunately it does not solve my problem. Of course, neither does nchoosek as my n is around 100.

Truth is, I don't need all of the possible combinations at the same time. I will explain what I need, as there might be an easier way to achieve the desired result. I have a matrix M of 100 rows and 25 columns.

Think of a submatrix of M as a matrix formed by ALL columns of M and only a subset of the rows. I have a function f that can be applied to any matrix which gives a result of either -1 or 1. For example, you can think of the function as sign(det(A)) where A is any matrix (the exact function is irrelevant for this part of the question).

I want to know what is the biggest number of rows of M for which the submatrix A formed by these rows is such that f(A) = 1. Notice that if f(M) = 1, I am done. However, if this is not the case then I need to start combining rows, starting of all combinations with 99 rows, then taking the ones with 98 rows, and so on.

Up to this point, my implementation had to do with nchoosek which worked when M had only a few rows. However, now that I am working with a relatively bigger dataset, things get stuck. Do any of you guys think of a way to implement this without having to use the above function? Any help would be gladly appreciated.

Here is my minimal working example, it works for small obs_tot but fails when I try to use bigger numbers:

value = -1; obs_tot = 100; n_rows = 25;
mat = randi(obs_tot,n_rows);
while value == -1
    posibles = nchoosek(1:obs_tot,i);
    [num_tries,num_obs] = size(possibles);
    num_try = 1;
        while value == 0 && num_try <= num_tries
        check = mat(possibles(num_try,:),:);
        value = sign(det(check));
        num_try = num_try + 1;
        end
    i = i - 1;
end
obs_used = possibles(num_try-1,:)';

Answer 1

Preamble

As yourself noticed in your question, it would be nice not to have nchoosek to return all possible combinations at the same time but rather to enumerate them one by one in order not to explode memory when n becomes large. So something like:

enumerator = CombinationEnumerator(k, n);
while(enumerator.MoveNext())
    currentCombination = enumerator.Current;
    ...
end

Here is an implementation of such enumerator as a Matlab class. It is based on classic IEnumerator<T> interface in C# / .NET and mimics the subfunction combs in nchoosek (the unrolled way):

%
% PURPOSE:
%
%   Enumerates all combinations of length 'k' in a set of length 'n'.
%
% USAGE:
%
%   enumerator = CombinaisonEnumerator(k, n);
%   while(enumerator.MoveNext())
%       currentCombination = enumerator.Current;
%       ...
%   end
%

%% ---
classdef CombinaisonEnumerator  < handle

    properties (Dependent) % NB: Matlab R2013b bug => Dependent must be declared before their get/set !
        Current; % Gets the current element.
    end

    methods
        function [enumerator] = CombinaisonEnumerator(k, n)
        % Creates a new combinations enumerator.

            if (~isscalar(n) || (n < 1) || (~isreal(n)) || (n ~= round(n))), error('`n` must be a scalar positive integer.'); end
            if (~isscalar(k) || (k < 0) || (~isreal(k)) || (k ~= round(k))), error('`k` must be a scalar positive or null integer.'); end
            if (k > n), error('`k` must be less or equal than `n`'); end

            enumerator.k = k;
            enumerator.n = n;
            enumerator.v = 1:n;            
            enumerator.Reset();

        end
        function [b] = MoveNext(enumerator)
        % Advances the enumerator to the next element of the collection.

            if (~enumerator.isOkNext), 
                b = false; return; 
            end

            if (enumerator.isInVoid)
                if (enumerator.k == enumerator.n),
                    enumerator.isInVoid = false;
                    enumerator.current = enumerator.v;
                elseif (enumerator.k == 1)
                    enumerator.isInVoid = false;
                    enumerator.index = 1;
                    enumerator.current = enumerator.v(enumerator.index);                    
                else
                    enumerator.isInVoid = false;
                    enumerator.index = 1;
                    enumerator.recursion = CombinaisonEnumerator(enumerator.k - 1, enumerator.n - enumerator.index);
                    enumerator.recursion.v = enumerator.v((enumerator.index + 1):end); % adapt v (todo: should use private constructor)
                    enumerator.recursion.MoveNext();
                    enumerator.current = [enumerator.v(enumerator.index) enumerator.recursion.Current]; 
                end
            else
                if (enumerator.k == enumerator.n),
                    enumerator.isInVoid = true;
                    enumerator.isOkNext = false;
                elseif (enumerator.k == 1)
                    enumerator.index = enumerator.index + 1;
                    if (enumerator.index <= enumerator.n)
                        enumerator.current = enumerator.v(enumerator.index);
                    else 
                        enumerator.isInVoid = true;
                        enumerator.isOkNext = false;
                    end                                       
                else
                    if (enumerator.recursion.MoveNext())
                        enumerator.current = [enumerator.v(enumerator.index) enumerator.recursion.Current];
                    else
                        enumerator.index = enumerator.index + 1;
                        if (enumerator.index <= (enumerator.n - enumerator.k + 1))
                            enumerator.recursion = CombinaisonEnumerator(enumerator.k - 1, enumerator.n - enumerator.index);
                            enumerator.recursion.v = enumerator.v((enumerator.index + 1):end); % adapt v (todo: should use private constructor)
                            enumerator.recursion.MoveNext();
                            enumerator.current = [enumerator.v(enumerator.index) enumerator.recursion.Current];
                        else 
                            enumerator.isInVoid = true;
                            enumerator.isOkNext = false;
                        end                                                               
                    end
                end
            end

            b = enumerator.isOkNext;

        end
        function [] = Reset(enumerator)
        % Sets the enumerator to its initial position, which is before the first element.

            enumerator.isInVoid = true;
            enumerator.isOkNext = (enumerator.k > 0);

        end
        function [c] = get.Current(enumerator)
            if (enumerator.isInVoid), error('Enumerator is positioned (before/after) the (first/last) element.'); end
            c = enumerator.current;
        end
    end

    properties (GetAccess=private, SetAccess=private)
        k = [];
        n = [];
        v = [];
        index = [];
        recursion = [];
        current = [];
        isOkNext = false;
        isInVoid = true;
    end

end

We can test implementation is ok from command window like this:

>> e = CombinaisonEnumerator(3, 6);
>> while(e.MoveNext()), fprintf(1, '%s\n', num2str(e.Current)); end

Which returns as expected the following n!/(k!*(n-k)!) combinations:

1  2  3
1  2  4
1  2  5
1  2  6
1  3  4
1  3  5
1  3  6
1  4  5
1  4  6
1  5  6
2  3  4
2  3  5
2  3  6
2  4  5
2  4  6
2  5  6
3  4  5
3  4  6
3  5  6
4  5  6

Implementation of this enumerator may be further optimized for speed, or by enumerating combinations in an order more appropriate for your case (e.g., test some combinations first rather than others) ... Well, at least it works! :)

Problem solving

Now solving your problem is really easy:

n = 100;
m = 25;
matrix = rand(n, m);

k = n;
cont = true;
while(cont && (k >= 1))

    e = CombinationEnumerator(k, n);
    while(cont && e.MoveNext());

       cont = f(matrix(e.Current(:), :)) ~= 1;

    end

    if (cont), k = k - 1; end 

end