CODEWITHSUNDEEP
matlabcombinationsdiscrete-mathematics
fina
fina

Reputation: 329

Matlab generate all possible team combinations

There's lots of questions that are similar to mine but I haven't found quite what I'm looking for yet. I'm working on a project to optimize teaming in a class, and am not sure how to generate all possible team combinations.

Say I have a vector that's a list of numbered people, like 

<1,2,3,4,5....,n>

I want to generate all possible combinations of teams with k people per team, where k is smaller than n. The output should be matrices where the rows are the teams. Each matrix will have k columns, and n/k rows (corresponding to the number of teams).

For example, say my vector is<1,2,3,4>. I want all combinations of teams of 2. My possible output matrices would be [1,2;3,4],[1,3;2,4], and [1,4;2,3]. I'd like to know how to scale this up to any n and k value.

Upvotes: 2

Views: 578

Answers (2)

tashuhka
tashuhka

Reputation: 5126

It is quite overkilling, but it seems to work:

n = 4;
k = 2;

allCombinations = perms(1:n);

numComb = size(allCombinations,1);
selCombinations = zeros(size(allCombinations));
cellCombinations = cell(numComb,1);
for ii = 1:numComb
    candidate = sortrows(sort(reshape(allCombinations(ii,:),[],k),2));
    selCombinations(ii,:) = candidate(:);
    cellCombinations{ii} = candidate;
end

[~,idx] = unique(selCombinations, 'rows');
cellCombinations{idx}

I create all the possible combinations of n elements, and then I select the unique combinations that follow your criteria.

Upvotes: 1

Luis Mendo
Luis Mendo

Reputation: 112669

I have done only some incomplete testing, but this seems to work.

Code:

%// Data:
n = 6; %// number of people
k = 2; %// team size. Assumed to divide p

%// Let's go:
M = unique(perms(ceil((1:n)/k)), 'rows').'; %'// the transpose is for convenience
result = NaN(n/k, k, size(M,2)); %// preallocate
for t = 1:n/k
    [ii, ~] = find(M==t);
    result(t,:,:) = reshape(ii, k, []);
end
result = result(:,:,all(diff(result(:,1,:))>0, 1));

The result matrices are given by result(:,:,1), result(:,:,2) etc.

Explanation:

The key steps are:

  • Line M = unique(perms(ceil((1:n)/k)), 'rows').': this assigns k different team numbers, one to each group of n/k people, and creates all different permutations of those numbers. So this includes all possible team groupings.

  • for loop: this translates the above representation into the matrix format you want: each team is described by a row containing n/k labels from the set {1,2,...,n}, telling which people belong to that team. Within each row, those labels are always increasing.

  • Line result = result(:,:,all(diff(result(:,1,:))>0, 1)): this removes matrices that are row-permutations of others. It does so by keeping only matrices whose first column is increasing.

Examples:

For n=4; k=2,

>> result
result(:,:,1) =
     1     2
     3     4
result(:,:,2) =
     1     3
     2     4
result(:,:,3) =
     1     4
     2     3

For n=6; k=2,

>> result
result(:,:,1) =
     1     2
     3     4
     5     6
result(:,:,2) =
     1     2
     3     5
     4     6
result(:,:,3) =
     1     2
     3     6
     4     5
result(:,:,4) =
     1     3
     2     4
     5     6
...

Upvotes: 2

Related Questions