MATLAB: All combinations from a set of rows without repetition of elements

all combinationswithout repetition

I want to find all the possible combinations from a set of pairs. This example will help explaining the problem better. Say I have this line of code: c=nchoosek(1:6,2) , it gives:
c =
     1     2
     1     3
     1     4
     1     5
     1     6
     2     3
     2     4
     2     5
     2     6
     3     4
     3     5
     3     6
     4     5
     4     6
     5     6
out=
Now I want to find all the possibles combinations using 3 pairs from the set c such that all the elements in the final array are unique. For example [1 2], [3 4] and [5 6] —-> [1 2 3 4 5 6] is a good combination [1 2 ], [1 3] and [5 6] —-> [1 2 1 3 5 6] is a combination I do not want because 1 is repetitive.
These are all the combinations that work
out =
     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
     1     3     2     6     4     5
     1     4     2     3     5     6
     1     4     2     5     3     6
     1     4     2     6     3     5
     1     5     2     3     4     6
     1     5     2     4     3     6
     1     5     2     6     3     4
     1     6     2     3     4     5
     1     6     2     4     3     5
     1     6     2     5     3     4
Is there a fast way of doing this for c=nchoosek(1:n,2) and n is very large? I wrote a script that works fine using c1=nchoosek(1:size(c,1),3) when size(c,1) is not too large but the code is very slow when size(c,1) is very large.
If there is another way of doing this without nchoosek, the order of the tow pairs does not matter in the final result, for example [1 2 3 4 5 6} and [2 1 3 4 5 6] count as one combination.
Thanks

Best Answer

Hi Timo,
It appears that for n even, the number of possible combinations of nonintersecting pairs is the product of all the odd integers less than n. The following code seems to work. The matrix B is one answer, but A = n+1-fliplr(B) puts A into a form like yours; if you run this for n=6 you can see the difference. Past n = 10 you are going to need semicolons!
For n = 18 this takes about 8 seconds on my PC and creates a matrix with 17!! x 18 = 6.2e8 elements. I went to uint8 numbers for the matrices so each of the them has as only as many bytes as elements, 620MBytes.
n = 6
B = paircombs(n)
A = n+1-fliplr(B)
function m = paircombs(n)
  if n==2
    m = uint8([1 2]);
  else
        % stack n-1 copies of previous matrix, which contains
        % values from 1 to n-2
    q = paircombs(n-2);
    qrow = size(q,1);
    m = repmat(q, n-1,1);             
        % append two new columns with values n-1, n
    onz = ones(1,size(m,1),'uint8')';
    m = [m (n-1)*onz n*onz];
        % split rows of matrix into n-1 sections, and in all but one section 
        % swap value n-1 with one of values 1..n-2
    for k = 1:n-2
      ind = k*qrow+1:(k+1)*qrow;
      msub = m(ind,:);
      msub(msub==(n-(k+1))) = n-1;
      msub(:,end-1) = n-(k+1);
      m(ind,:) = msub;
    end
  end
end
Related Question