Asked by Joao Roberto de la Rosa
on 12 Sep 2018

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

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.

Joao Roberto de la Rosa
on 12 Sep 2018

John D'Errico
on 12 Sep 2018

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

Joao Roberto de la Rosa
on 12 Sep 2018

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

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 6 Comments

## John D'Errico (view profile)

## Direct link to this comment

https://de.mathworks.com/matlabcentral/answers/418558-matrix-grouping-result-of-combinations#comment_609147

## Joao Roberto de la Rosa (view profile)

## Direct link to this comment

https://de.mathworks.com/matlabcentral/answers/418558-matrix-grouping-result-of-combinations#comment_609153

## John D'Errico (view profile)

## Direct link to this comment

https://de.mathworks.com/matlabcentral/answers/418558-matrix-grouping-result-of-combinations#comment_609162

## Joao Roberto de la Rosa (view profile)

## Direct link to this comment

https://de.mathworks.com/matlabcentral/answers/418558-matrix-grouping-result-of-combinations#comment_609177

## John D'Errico (view profile)

## Direct link to this comment

https://de.mathworks.com/matlabcentral/answers/418558-matrix-grouping-result-of-combinations#comment_609313

## Joao Roberto de la Rosa (view profile)

## Direct link to this comment

https://de.mathworks.com/matlabcentral/answers/418558-matrix-grouping-result-of-combinations#comment_609399

Sign in to comment.