Генерация всех сочетаний без повторений с использованием MATLAB


April 2019


2.3k раз


У меня есть 4 комплекта каждый из которых содержит 6 элементов, из которых я хочу, чтобы генерировать все возможные векторы размера 8 были первые два элемента из SET1 вторых 2 из set2 третьей 2 из SET3 вперед 2 из SET4 без повторения в точках, взятых из каждого множества таких что элементы 1,2 / 3,4 / 5,6 / 7,8 всегда различны. Мои комбинации целевого номера есть (6choose2) ^ 4. Любая помощь, пожалуйста.


1 ответы


So I found a way to get your combinations. You should really have given an more minimal example to explain your problem (that's how I solved it by the way).

The procedure is:

  • Get all the {2 element} unique combination for each set.
  • Then build an index of the result you obtain. Normally there should be an index for each subset but since they are all the same length, the number of unique combinations will be the same so you can just reuse 4x the same index.
  • Get all the combinations of these 4 sets of indices
  • Finally, rebuild the final matrix based on the indices combinations

The code look like:

%// prepare a few helper numbers
nSets = 4 ;
nElemPerSet = 2 ;
nCombs =  nchoosek( numel(D1) ,nElemPerSet).^nSets ; %// <= nCombs=50625

%// for each set, get the unique combinations of 2 elements
s1 = nchoosek( D1 , nElemPerSet ) ;
s2 = nchoosek( D2 , nElemPerSet ) ;
s3 = nchoosek( D3 , nElemPerSet ) ;
s4 = nchoosek( D4 , nElemPerSet ) ;

%// now get the index of all the combinations of the above subsets
s = 1:size(s1,1) ;
combindex = all_combinations( repmat({s},1,4) ) ; %// <= size(combindex)=[50625 4]

%// now rebuild the full combinations based on above indices
combinations = zeros( nCombs , nSets*nElemPerSet ) ;
for ic = 1:nCombs
    combinations(ic,:) = [s1(combindex(ic,1),:) s2(combindex(ic,2),:) s3(combindex(ic,3),:) s4(combindex(ic,4),:)] ;

There is probably a way to get rid of the last loop with an intelligent use of arrayfun but I leave that as an exercise to the reader.

This code works for your initial values of D1, D2, D3 and D4 as described in your question, but if you or anybody want to run it step by step to understand what's happening, I strongly recommend to try it with much simpler starting values. Something like:

%// define 4 non-complex sets of 4 values each (all different)
nVal=4 ;
D1 = 1:nVal ;
D2 = D1(end)+1:D1(end)+nVal ;
D3 = D2(end)+1:D2(end)+nVal ;
D4 = D3(end)+1:D3(end)+nVal ;

Note the use of the function all_combinations. This is just the answer I was mentioning in the comment (Generate a matrix containing all combinations of elements taken from n vectors) repackaged in a function. I suggest you have a look and bookmark it if you deal with combination problem often (also you can upvote it if it helps you, which it does here).

The repackaged function is:

function combs = all_combinations( vectors )
%// function combs = all_combinations( vectors )
%// example input :
%//     vectors = { [1 2], [3 6 9], [10 20] }; %//cell array of vectors
%// Credit: Luis Mendo : https://stackoverflow.com/questions/21895335/generate-a-matrix-containing-all-combinations-of-elements-taken-from-n-vectors

n = numel(vectors);             %// number of vectors
combs = cell(1,n);              %// pre-define to generate comma-separated list
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1}); %// the reverse order in these two
%// comma-separated lists is needed to produce the rows of the result matrix in
%// lexicographical order 
combs = cat(n+1, combs{:});     %// concat the n n-dim arrays along dimension n+1
combs = reshape(combs,[],n);    %// reshape to obtain desired matrix

Связанные вопросы