MATLAB Answers

0

Matrix grouping result of combinations

Latest activity Edited by David Goodmanson on 30 Jun 2019
given the list below:
listResult = combnk(1:6,2)
listResult =
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
how could I get an array (5 x 3) with the pairs above so that each row contains all elements of the set (1: 6). ex :
1 2 3 4 5 6
1 3 2 5 4 6
1 4 2 6 3 5
1 5 2 4 3 6
1 6 2 3 4 5

  6 Comments

Many thanks for the help John. You are completely right, the [1 2 3 4 5 6] is a right choice. Forgive me for the comment above. In fact I still had not found a solution that used this sequence and made the inappropriate comment without the purpose of offending. John would you know how to transform the result of combnk(1:6,2) directly into the matrix you generated?
That I cannot say how to do, at least not yet. So let me first be sure what you are asking. Given the set of 15 pairs (will it always be exactly 6 numbers? Or are you asking how to do this in general, thus, to find such a set for any even number? For example, will you next want to do this from the set of pairs from nchoosek(1:8,2)?
Are you asking to find ALL such ways to do this? Or just ANY one way to accomplish that?
It will not always be a set of exactly 6 numbers. I'm looking for a solution in general and I'm using 6 just as an example.
I do not need to know how many ways this can be done.
I'm looking for just one solution that meets two rules:
  1. Use all combinations without repeating any pair,
  2. Each row contains all numbers in the set, which in this example is 1:6 .

Sign in to comment.

3 Answers

Answer by John D'Errico
on 12 Sep 2018
 Accepted Answer

Hmm. How about this as a start, a constructive way to build the array you seem to be asking to create.
I'll presume that the goal is to start with the set of pairs nchoosek(1:n,2), where n is an even number. For example, given n=4, we get 6 pairs.
nchoosek(1:4,2)
ans =
1 2
1 3
1 4
2 3
2 4
3 4
Now we want to build an array with n-1 rows, and n columns, so an (n-1)xn array composed of those pairs.
Each of the n-1 rows must contain a permutation of the numbers 1:n. And since each row contains all numbers 1:n, and there will only be n-1 pairs in the set of all pairs generated that contain the number n, there can only be n-1 rows. And any pair can only be used once.
That tells us the first two columns, without loss of generality, can be created as:
1 2
1 3
...
1 n
Lets see what happens for n==4. There is now only one pair that can be used for the second column. So we can easily fill out the array.
1 2 3 4
1 3 2 4
1 4 2 3
This is the only way to build the array you are asking for when n==4. Any other solution can be viewed as a simple transposition that could be untangled by means of a sort of each pair. So we could exchange columns 3 and 4, for example, but that is not a distinct solution. Now, move to the case of n==6. (It is often the case that we can build intuition about a process by working through it with pencil and paper.) Thus, for n==6 we can start with:
1 2
1 3
1 4
1 5
1 6
We can exchange elements in any row of that set without changing anything significant. And we can randomly permute the rows. So, suppose that we now augment that to start like this:
1 3 2 6 4 5
1 2
1 4
1 5
1 6
There are 8 pairs remaining.
2 3
2 4
2 5
3 4
3 5
3 6
4 6
5 6
We can choose two of those pairs to fill out the second row. It could be done in one of these two ways:
1 2 3 4 5 6
1 2 3 5 4 6
1 2 3 6 4 5 ### Is excluded, since [4 5] has been used
So the problem now branches. That suggests one solution could be to solve this in a recursive manner, filling out the array one row at a time, but doing so recursively from the pairs remaining. Just doing that by pencil and paper, I could have gotten this array:
1 3 2 6 4 5
1 2 3 4 5 6
1 4 2 5 3 6
1 5 2 3 4 6
1 6 2 4 3 5
And there are other choices I could have made along the way. Each branch reflects a choice that I had to make, but there were some alternatives. For example, this next array shows one such alternative, where I changed the third row, by swapping the second and third pairs in that row.
1 3 2 6 4 5
1 2 3 4 5 6
1 4 3 6 2 5
1 5 2 3 4 6
1 6 2 4 3 5
So if you are asking how many ways this can be done, we can see that I can always swap pairs within any row.
So I'm still not positive what is your final goal. If the goal is to find one such array from the set of pairs nchoosek(1:n,2) for even n, then my answer is I would just build up that array one row at a time from the pairs remaining. This should be doable in a loop. Or, if you want to find ALL ways of creating that array, then I would use a recursive scheme. In any event, I don't think the code is difficult, it just requires care in how you write it, emulating the scheme you would use by pencil and paper and crossing out pairs that have been used already. If your real question is to know how many ways exist to distinctly create that array, then you need to decide which results are distinct. Thus, are these choices of rows distinct?
1 2 3 4 5 6
1 2 5 6 3 4
I might argue they are not distinct from what I think you seem to have said, since the same three pairs are used in both cases.

  2 Comments

John, thank you very much for your contribution. You really showed me a path that I had not yet tried to follow. Your proposal is quite intelligent. I have tried to solve with a recursive code (for a much larger set) and at the end of the process has left some unallocated pairs. In other words, a faulty code. John, once again thank you for your tremendous effort and time spent helping out, thank you very much.
I'm glad to be of help.
I wonder if a simple data structure to store the set of pairs available is just a square boolean array. Thus
triu(true(n,n),1)
ans =
6×6 logical array
0 1 1 1 1 1
0 0 1 1 1 1
0 0 0 1 1 1
0 0 0 0 1 1
0 0 0 0 0 1
0 0 0 0 0 0
So the non-zero elements of this array correspond to all pairs of interest to you. Zero them out when used, and pass the array around as necessary. It might be simpler than searching through a list of explicit pairs of numbers.

Sign in to comment.


Answer by Walter Roberson
on 12 Sep 2018

result = squeeze(num2cell(reshape(perms(1:6),[],2,3),2));
This will give you a 720 x 3 cell array in which each entry is a 1 x 2 double.
It is not clear exactly what output you were hoping for. Perhaps a 1 x 3 cell array in which the entries were 720 x 2 arrays ??

  1 Comment

Many thanks for the help Walter. Your answer worked with the permutations and I need to group the combinations in such a way that all 15 pairs of combinations resulting from c (6.2) are allocated in a 5 x 3 matrix where there is no repetition of the elements in the rows.

Sign in to comment.


Answer by David Goodmanson on 29 Jun 2019
Edited by David Goodmanson on 30 Jun 2019

Hello Joao,
Maybe I need to write better blurbs.
Here is a general solution for even n, with a verification check that shows that the solution meets the rules. I have run it up to n = 6000.
It's an interesting problem. I found the first version basically by experimentation. Once the pattern was established, the second version reproduces it and is less transparent but runs about ten times faster.
% There are n(n-1)/2 possible pairs of integers from the set
% {1..n}, where the order in each pair does not matter
% (n things taken two at a time).
% For n even, construct an (n-1) x n matrix of pairs
% [ for each row, the first pair is columns 1 and 2,
% the second pair is columns 3 and 4, etc. ]
% such that [1] each row contains all n numbers
% and [2] no pair is included more than once in the matrix.
% The order of the pairs in each row does not matter.
n = 10;
% version 1, commented out
% % collect the result in matrix A
% A =zeros(n-1,n);
% a = 1:n;
% rowcount = 1;
% A(1,:) = a;
% i1 = reshape(2:n-1,2,[])'; % e.g. n=8, i1 is [2 3; 4 5; 6 7]
% i2 = i1+1; % i2 is [3 4; 5 6; 7 8]
% % alternately swap numbers indicated in all the rows of i1,
% % then all the rows of i2
% while rowcount < n-1
% a = swappair(a,i1);
% rowcount = rowcount+1;
% A(rowcount,:) = a;
% a = swappair(a,i2);
% rowcount = rowcount+1;
% A(rowcount,:) = a;
% end
% version 2, faster
% construct matrix A
A = zeros(n-1,n);
A(:,1) = 1;
A(:,2) = 2:n;
u10 = [1:n flip(1:n)]';
u2 = [flip(2:n) 2:n]';
for q = n:-2:4
A(:,q) = u10(q:q+n-2);
A(:,q-1) = u2(n-q+2:2*n-q);
end
% to check, first stack all the pairs of A
% into an n(n-1)/2 x 2 matrix B with sorted rows
q = n-1;
B = reshape(A(:),2*q,[]);
B1 = B(1:q,:); % all the column 1 elements of A
B2 = B(q+1:end,:); % all the column 2 elements of A
B = [B1(:),B2(:)];
B = sortrows(B);
% for comparison with B, independently create matrix C
% that contains all pairs with sorted rows
[C1 C2] = meshgrid(1:n,1:n);
C = [C1(:), C2(:)];
C(C(:,1) == C(:,2),:) = []; % eliminate pairs such as [1 1]
C = sort(C,2);
C = sortrows(C);
C =C(2:2:end,:); % each pair is listed twice
max(max(abs(B-C))) % check, should be zero
function b = swappair(a,ind)
for k = 1:size(ind,1)
m = ind(k,1);
n = ind(k,2);
fm = find(a == m);
fn = find(a == n);
a(fm) = n;
a(fn) = m;
end
b = a;
end

  0 Comments

Sign in to comment.