3

I want to generate all combinations of sets of pairs of 3 men and 2 women. There are many examples for pairing (e.g see this), but none of them deals with sets of pairs.

For instance, if I have:

Men   = {'M1', 'M2'};
Women = {'W1', 'W2', 'W3'};

The result I want is the following sets:

(M1, W1), (M2, W2)
(M1, W1), (M2, W3)
(M1, W2), (M2, W1)
(M1, W2), (M2, W3)
(M1, W3), (M2, W1)
(M1, W3), (M2, W2)

Thank you.

Community
  • 1
  • 1
user2627824
  • 33
  • 6

3 Answers3

2

Actually it's quite simple. To populate a set of k pairs, you need k men and k women, so let's find all possible combinations of k men and k women first:

%// Find all possible combinations of sets of k pairs of men and women
k = 2;
idx_m = nchoosek(1:numel(Men), k);             % // Indices of men
idx_w = nchoosek(1:numel(Women), k);           % // Indices of women
idx_w = reshape(idx_w(:, perms(1:k)), [], k);  % // All permutations

Then let's construct all possible combinations of sets of k men and k women:

[idx_comb_w, idx_comb_m] = find(ones(size(idx_w , 1), size(idx_m , 1)));
idx = sortrows([idx_m(idx_comb_m(:), :), idx_w(idx_comb_w(:), :)]);
idx = idx(:, reshape(1:size(idx, 2), k, [])'); %'// Rearrange in pairs

The resulting matrix idx contains the indices of men and women in the sets (first column is men, second column - women, third column - men, and fourth column - women, and so on...).

Example

Men = {'M1', 'M2'};
Women = {'W1', 'W2', 'W3'};

%// Find all possible combinations of sets of k pairs of men and women
k = 2;
idx_m = nchoosek(1:numel(Men), k);
idx_w = nchoosek(1:numel(Women), k);
idx_w = reshape(idx_w(:, perms(1:k)), [], k);
[idx_comb_w, idx_comb_m] = find(ones(size(idx_w , 1), size(idx_m , 1)));

%// Construct pairs from indices and print sets nicely
idx = sortrows([idx_m(idx_comb_m(:), :), idx_w(idx_comb_w(:), :)]);
idx = idx(:, reshape(1:size(idx, 2), k, [])');

%// Obtain actual sets
sets = cell(size(idx));
sets(:, 1:2:end) = Men(idx(:, 1:2:end));
sets(:, 2:2:end) = Women(idx(:, 2:2:end));

%// Print sets nicely
sets_t = sets';
fprintf([repmat('(%s, %s), ', 1, k - 1), '(%s, %s)\n'], sets_t{:})

Here the resulting array sets is already adapted to include the actual values from Men and Women. The result is:

(M1, W1), (M2, W2)
(M1, W1), (M2, W3)
(M1, W2), (M2, W1)
(M1, W2), (M2, W3)
(M1, W3), (M2, W1)
(M1, W3), (M2, W2)
Eitan T
  • 32,660
  • 14
  • 72
  • 109
0

This example is working using the FEX file allcomb 

men = {'M1', 'M2', 'M3'};
women = {'W1', 'W2'};
allPeople = [men, women];
%// Play with vector index because allcomb doesn't work with cell
[~, id_men] = ismember(men,allPeople);
[~, id_women] = ismember(women,allPeople);


%// give all combinations for men/women
setOfMenWomen = allcomb(id_men,id_women);
%// give all combinations of pairs
nComb = size(setOfMenWomen,1);
setOfPair = nchoosek(1:nComb,2);
%// give all combinations for men/women/men/women
setOfPairMenWomen = cell2mat(arrayfun(@(id) setOfMenWomen(id,:), setOfPair, 'UniformOutput', 0));
%// get ids of set of pairs with the same men twice
isDoubleMen = setOfPairMenWomen(:,1) == setOfPairMenWomen(:,3);
%// get ids of set of pairs with the same women twice
isDoubleWomen = setOfPairMenWomen(:,2) == setOfPairMenWomen(:,4);
%// We don't want to have set of pairs with twice same men or same women
cond = isDoubleWomen | isDoubleMen;
setOfPairMenWomen(cond,:) = [];

%//results :
allPeople(setOfPairMenWomen)
Matthieu
  • 90
  • 1
  • 9
  • It works well but there are duplicated combinations, exactly twice. – user2627824 Jul 28 '13 at 17:57
  • You are right, at the moment I did not find any elegant way to avoid this :/ Until I find something best you can take the first half of the arrays setOfPairMenWomen(1:6,:) which is the exact opposite of the last part. – Matthieu Jul 28 '13 at 22:55
  • Thank you. But when I increase the members to 3 Men and 3 Women, 4Men and 3 Women, the number of set of pairs is supposed to be 6 and 24, respectively. But your result was different that means the result does not show all combinations. Can you fix it? – user2627824 Jul 28 '13 at 23:31
  • For 3vs3 I have 18 combinations and for 4vs3 36 combinations. How do you compute your total amount of combinations ? – Matthieu Jul 28 '13 at 23:45
  • I used permutation,i.e. kPq, k is relatively higher number between men and women, and q is lower number. For 3vs2, 3P2= 3*2=6, for 4vs3 = 4*3*2 = 24. For 3vs3, 3P3= 3*2*1=6. This is a people pairing, if there is 1 man and 1 woman, they should be paired. – user2627824 Jul 29 '13 at 01:21
  • Maybe I have misunderstood but I'm not sure this relation is correct. If there is 1M&1W the result is impossible (no pair) or I did not understand the initial request. – Matthieu Jul 29 '13 at 08:19
  • For me, the minimum of people is 2M&2W otherwise you can't have a pair of people. For the moment this code sample reacts as I expect. – Matthieu Jul 29 '13 at 08:23
0

I cannot see exactly what your question is. Do you search for an algorithm or an implementation in MATLAB? I will try to answer with a mathematical approach.

You might be able to solve your problem by formulating it as a graph problem: Your set of persons is the set of vertices. Form edges by connecting all men to all women. Now find the set of (maximum) matchings.

It depends a bit on what exactly you want: Do you want for example the element ((M1, W1)) to be part of your solution? Then you're searching for matchings (see Hosoya index for the number of elements in your solution set). If you want only elements where no further pairing can be added, then you only consider maximum matchings.

This might help if you extend your problem to generic non-gendered pairs: http://en.wikipedia.org/wiki/Telephone_number_(mathematics)

Ingo Schalk-Schupp
  • 843
  • 10
  • 26