All combinations from a set of rows without repetition of elements

30 次查看（过去 30 天）
Timo
Timo 2018-2-16
编辑： Timo 2018-2-19
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
  3 个评论
显示 1更早的评论
Jos (10584)
Jos (10584) 2018-2-16
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
Timo 2018-2-16
编辑：Timo 2018-2-16
[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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

David Goodmanson
David Goodmanson 2018-2-17
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
  1 个评论
Timo
Timo 2018-2-19
编辑：Timo 2018-2-19
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

请先登录，再进行评论。

更多回答（1 个）

Jos (10584)
Jos (10584) 2018-2-16
You might be interested in a faster alternative for nchoosek(n,k) when k equals 2:
https://uk.mathworks.com/matlabcentral/fileexchange/20144-nchoose2
  1 个评论
Timo
Timo 2018-2-16
编辑：Timo 2018-2-16
It does not help much as the problem is mainly related to combining the pairs but thanks for the suggestion though.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by