2

Suppose I have a list of length 2k, say {1,2,...,2k}. The number of possible ways of grouping the 2k numbers into k (unordered) pairs is n(k) = 1*3* ... *(2k-1). So for k=2, we have the following three different ways of forming 2 pairs

(1 2)(3 4)

(1 3)(2 4)

(1 4)(2 3)

How can I use Matlab to create the above list, i.e., create a matrix of n(k)*(2k) such that each row contains a different way of grouping the list of 2k numbers into k pairs.

obchardon
  • 10,614
  • 1
  • 17
  • 33
Raymond Kan
  • 21
  • 2
  • 1
    This question has been asked many times in different languages. Python examples: [1](https://stackoverflow.com/q/45704859/), [2](https://stackoverflow.com/q/10568081/), [3](https://stackoverflow.com/q/5360220/), R examples: [1](https://stackoverflow.com/q/30998216/), [2](https://stackoverflow.com/q/47213670/). Perhaps looking at those approaches will help. – Wolfie Jan 20 '21 at 10:59

3 Answers3

0
clear
k = 3;
set = 1: 2*k;
p = perms(set); % get all possible permutations
% sort each two column
[~, col] = size(p);
for i = 1: 2: col
    p(:, i:i+1) = sort(p(:,i:i+1), 2);
end
p = unique(p, 'rows'); % remove the same row
% sort each row
[row, col] = size(p);
for i = 1: row
    temp = reshape(p(i,:), 2, col/2)';
    temp = sortrows(temp, 1);
    p(i,:) = reshape(temp', 1, col);
end
pairs = unique(p, 'rows'); % remove the same row

pairs =
    
         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

As someone think my former answer is not useful, i post this.

Lucien Xhh
  • 317
  • 1
  • 6
  • Why have you added a new answer rather than editing the existing answer? Since the other answer was not working, as noted by the OP, it should probably be deleted in light of you posting a new answer – Wolfie Jan 20 '21 at 08:40
  • Someone think the existing one is not useful, i don't want to have my new answer misunderstood. Plus, i think the former can inspires others. – Lucien Xhh Jan 20 '21 at 08:44
  • This is a Question and Answer site, if your answer is not correct then it is redundant. People reading this page will be doing so because of this specific question, not looking for inspiration – Wolfie Jan 20 '21 at 08:56
  • This works, but only for small k. If I want to do k=7, then I will run out of memory. Ideally, one would like to directly generate the pairs instead of generating all the permutations of (1,...,2k) and eliminate the redundant ones. – Raymond Kan Jan 20 '21 at 09:15
  • @Raymond Kan Exactly, when k = 10, the matrix will be 654729075x10 (48.8GB). Surely i can write a new function based on the source code of `perms` or `nchoosek` to directly generate the pairs, but the funcition will only run for k <10. Please tell us what k do you want, and then we can choose a better way to solve. – Lucien Xhh Jan 20 '21 at 10:25
  • @Wolfie That's your viewpoint of stack overflow, not mine. You're chasing answers, but I think the process of thinking is more important. – Lucien Xhh Jan 20 '21 at 10:33
0

I have the following brute force way of enumerating the pairs. Not particularly efficient. It can also cause memory problem when k>9. In that case, I can just enumerate but not create Z and store the result in it.

function Z = pair2(k)
   count = [2*k-1:-2:3];
   tcount = prod(count);
   Z = zeros(tcount,2*k);
   x = [ones(1,k-2) 0];
   z = zeros(1,2*k);
   for i=1:tcount
       for j=k-1:-1:1
           if x(j)<count(j)
              x(j) = x(j)+1;
              break
            end
            x(j) = 1;
       end
       y = [1:2*k];
       for j=1:k-1
           z(2*j-1) = y(1);
           z(2*j) = y(x(j)+1);
           y([1 x(j)+1]) = [];
       end
       z(2*k-1:2*k) = y;
       Z(i,:) = z;
   end
Raymond Kan
  • 21
  • 2
  • The number of different partitions is `(2n)!/(2^n * n!)`, which will very quickly grow with `n` - you likely need to limit the scope of what you're trying to do once you have this list if you need `n>9`! – Wolfie Jan 20 '21 at 10:51
  • I agree, I should not store the partition, I can just enumerate each possibility in the loop and do the necessary work for that partition, then move on to the next one. This way, I can do larger k, say k=12. – Raymond Kan Jan 20 '21 at 10:59
  • That will help with the memory constraint, but you will soon hit a time constraint iterating over than large of a loop! – Wolfie Jan 20 '21 at 11:01
-1
k = 3;
set = 1: 2*k;
combos = combntns(set, k);
[len, ~] = size(combos);
pairs = [combos(1:len/2,:) flip(combos(len/2+1:end,:))];

pairs =
         
         1     2     3     4     5     6
         1     2     4     3     5     6
         1     2     5     3     4     6
         1     2     6     3     4     5
         1     3     4     2     5     6
         1     3     5     2     4     6
         1     3     6     2     4     5
         1     4     5     2     3     6
         1     4     6     2     3     5
         1     5     6     2     3     4

You can also use nchoosek instead of combntns. See more at combntns or nchoosek

Lucien Xhh
  • 317
  • 1
  • 6
  • Thanks, but this is not generating what I need. There are altogether 1x3x5 = 15 different ways of grouping {1,2...,6} into 3 pairs. For example, I also should have [1 6 2 3 4 5] – Raymond Kan Jan 20 '21 at 06:53
  • 1
    Sorry for that I misunderstood your question. But it seems that you can use `nchoosek' to write a function yourself to solve this problem. I think in Stack Overflow we need inspire each other and improve ourselves, but do not indulge in a request. At least you should post your code and prove your attempt. – Lucien Xhh Jan 20 '21 at 07:38