Home all possible combinations of a set in Matlab
Reply: 2

all possible combinations of a set in Matlab

user70299
1#
user70299 Published in 2017-12-07 22:29:15Z

I'm trying to find all possible combinations of a set but the order of the elements are also important for my problem.

For example for the set set={A, B, C}, the possible subsets are subsets={A},{B},{C},{A,B},{A,C},{B,A},{B,C},{C,A},{C,B},{A,B,C},{A,C,B},{B,A,C},{B,C,A},{C,A,B},{C,B,A}.

Are there any Matlab function to find that?

Thanks in advance.

nekomatic
2#
nekomatic Reply to 2017-12-08 16:43:32Z

I couldn't bear to see all those for loops in Tommaso's answer, so here's one with no loops:

a = {'A' 'B' 'C'};

% Build an array of binary vectors which we will use to select subsets of
% the array to be permuted
nGroups = 2^numel(a) - 1;
selector = dec2bin(1:nGroups) == '1'; % hack to convert numbers to binary vectors
selectVectors = arrayfun(@(x) selector(x,:), 1:size(selector, 1), 'UniformOutput', false);

% Get the permutations of each subset of the array
permsCell = cellfun(@(s) perms(a(s)), selectVectors, 'UniformOutput', false);

% Rearrange the permutations into a one-dimensional cell array with one
% permutation in each element
rowsAsCells = @(ca) arrayfun(@(x) ca(x,:), 1:size(ca,1), 'UniformOutput', false);
permsAsRows = cellfun(rowsAsCells, permsCell, 'UniformOutput', false);
result = cat(2, permsAsRows{:});

This returns a cell array with one permutation in each element, like Tommaso's second solution.

Whether this version is preferable is a matter of taste ;-)

Tommaso Belluzzo
3#
Tommaso Belluzzo Reply to 2017-12-08 11:19:13Z
a = {'A' 'B' 'C'};
a_len = numel(a);

res_len = 0;

for i = 1:a_len
    res_len = res_len + (factorial(a_len) / factorial(a_len - i));
end

res = cell(res_len,a_len);
res_off = 1;

for i = 1:a_len
    bin = nchoosek(a,i);

    for j = 1:size(bin,1)
        bin_j = bin(j,:);

        per = perms(bin_j);
        per_hei = size(per,1);

        res_ran = res_off + per_hei - 1;
        res(res_off:res_ran,:) = [per repmat({''},size(per,1),a_len - i)];
        res_off = res_off + per_hei;
    end
end

Alternatively, if you don't want results organized into equally sized columns, but rather inserted into a single vector with variable length:

a = {'A' 'B' 'C'};
a_len = numel(a);

res_len = 0;

for i = 1:a_len
    res_len = res_len + (factorial(a_len) / factorial(a_len - i));
end

res = cell(res_len,1);
res_off = 1;

for i = 1:numel(a)   
    bin = nchoosek(a,i);

    for j = 1:size(bin,1)
        bin_j = bin(j,:);
        per = perms(bin_j);

        for y = 1:size(per,1)
            res{res_off,1} = {per{y,:}};
            res_off = res_off + 1;
        end
    end
end
You need to login account before you can post.

About| Privacy statement| Terms of Service| Advertising| Contact us| Help| Sitemap|
Processed in 0.332827 second(s) , Gzip On .

© 2016 Powered by mzan.com design MATCHINFO