Matrix grouping result of combinations

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

[John D'Errico]

You seem to be looking for permutations of the numbers 1:6.

But you give no reason why the above rows were chosen, yet excluding many others that are fully valid. For example, why is the row

1 3  2 6  4 5

not included?

[Joao Roberto de la Rosa]

Hi John , You are right, the sequence "1 3 2 6 4 5" is valid because it contains all elements of the group. But if you proceed, you will realize that there will be no matrix solution; in other words will not be possible to complete all rows. That's exactly what I'm trying to solve.

[John D'Errico]

So you are looking for 5 permutations of the numbers 1:6, such that each of the 15 combinations of 2 numbers are listed?

Your claim that [1 3 2 6 4 5] is NOT a valid choice is simply wrong, and I can prove that to be true, since I can construct such a set from the one you already gave.

Thus, start with the set:

S0 = [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];

lut = [1 3 2 6 4 5];
lut(S0)
ans =
   1     3     2     6     4     5
   1     2     3     4     6     5
   1     6     3     5     2     4
   1     4     3     6     2     5
   1     5     3     2     6     4

So you will see that S1 has 5 rows, each a permutation of the numbers 1:6. All 15 possible sets of pairs are included.

If it bothers you that some of them are reversed in order, that can be fixed easily enough with a sort.

[Joao Roberto de la Rosa]

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?

[John D'Errico]

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?

[Joao Roberto de la Rosa]

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 .

Answer 1

[John D'Errico]

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.

[Joao Roberto de la Rosa]

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.

[John D'Errico]

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.

Answer 2

[Walter Roberson]

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 ??

[Joao Roberto de la Rosa]

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.

Answer 3

[David Goodmanson]

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