All combinations from a set of rows without repetition of elements

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

[Jos (10584)]

just to be sure: a combination like [2 6 1 3 5 4] is already represented by [1 3 2 6 4 5] in your list, so should not be in the output?

[Jos (10584)]

and what should the output be when n>6? Always a unique combination of 3 outputs of nchoosek(n,2) ignoring the 7th to nth values?

[Timo]

[2 6 1 3 5 4] is not in the output because it is represented by [1 3 2 6 4 5] . The permutations of the pairs does not matter %-----------------------------------------------------

 1- n should be even
 2- a unique combination of n/2 outputs of nchoosek(n,2) so that the length of the final combination is n.

Answer 1

[David Goodmanson]

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

[Timo]

Nice code David ! I run into memory issues with higher values of n and that makes total sense due to the very large number of rows (possible combinations).

Thanks for the effort

Answer 2

[Jos (10584)]

You might be interested in a faster alternative for nchoosek(n,k) when k equals 2:

https://uk.mathworks.com/matlabcentral/fileexchange/20144-nchoose2

[Timo]

It does not help much as the problem is mainly related to combining the pairs but thanks for the suggestion though.