All combinations out of a two-column-matrix in matlab

Question

I have got a question regarding all the combinations of matrix-rows in Matlab. I currently create a combination-matrix out of a two-column-matrix:

Input:

1 2 
1 3
1 4
2 3
2 4
3 4

What I get is the following:

1 2 3 4
1 3 2 4
1 4 2 3

And when the input-matrix has entries from 1:6 it looks like this:

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

Right now I've implemented the following solution, which works nearly perfect (Thanks to Luis Mendo):

M = [1 2 
     1 3
     1 4
     2 3
     2 4
     3 4]; %// example data
n = floor(max(M(:))/2); %// size of tuples. Compute this way, or set manually

p = nchoosek(1:size(M,1), n).'; %'// generate all n-tuples of row indices
R = reshape(M(p,:).', n*size(M,2), []).'; %// generate result...
R = R(all(diff(sort(R.'))),:); %'//...removing combinations with repeated values

The problem I have now is the size. I need this matrix for an optimization algorithm, but the nchoosek-command creates a hugh matrix which gets shortend with the last command-line. I can actually use this solution only for an input-vector with the lenght of 15 digits, because the nchoosek-command cannot handle more.

What I am searching now, is a way to create theses combinations without the nchoosek-command. Does somebody has an idea how to?

Thanks and best regard

Jonas

Answer 1

It is not clear from your explanations, but I assume:

1. All the rows in M are unique.
2. Seek for the combinations of rows M where no number occurs twice.
3. The length of each combination is floor(max(M(:))/2)*2.

Then using recursion, this should work.

function [ U ] = searchappend( R,M, d, max_d )

    % termination criteria
    if d==max_d
        U=R;
        return;
    end

    lM = length(M(:,1));
    k=0;
    U = [];

    % seek for the row to append
    for i=1:lM
        if sum(ismember(M(i,:),R))==0
            S = [R,M(i,:)];
            T = searchappend(S, M(i+1:end,:), d+1, max_d);
            if k==0 && (~isempty(T))
                k=k+1;
                U = [U;T];
            end
        end
    end

end
_____________

lM = length(M);
n = floor(max(M(:))/2); 
A = [];

for i=1:(lM-n+1)
    R = M(i,:);
    T = searchappend(R,M(i+1:end,:),1,n);

    if ~isempty(T)
        A = [A;T];
    end

end

Note that I did not optimize it so it may be slow. The complexity should be O(n!) where n is the number of rows in M.