All possible combinations with varying lengths

Question

Hey I have an array of numbers:

[1,2,3,4,5,6,7,8]

I need to find every combination of then numbers with varying lengths:

[1,2]
[1,3]
[1,4]
.
.
.
[1,2,3,4,5,8]
[1,2,3,4,5,6,7]
[1,2,3,4,5,6,8]
[1,2,3,4,5,6,7,8]

NOTE: it does not matter what order the numbers are inside the array.

I want be pass the arrays to a function inside a loop so varying sized vectors should not be a worry.

I have tried perms() inside a loop however it returns far too many results.

Any help is appreciated.

Answer 1

You can use a trick to generate all variable-size combinations with nchoosek: introduce 0 to represent "no number" (assuming your numbers are never 0). That will generate duplicates, so you need to apply unique to the rows of the resulting matrix. Finally, remove zeros from each row and store the results into a cell array:

v = [1,2,3,4,5,6,7,8]; %// data

n = numel(v);
vz = [zeros(1,n-1) v]; %// add n-1 zeros to represent the absence of a number
r = nchoosek(vz,n); %// generate combinations, one in each row
r = unique(r,'rows'); %// remove duplicate rows
result = arrayfun(@(k) nonzeros(r(k,:)).', 1:size(r,1), 'uni',0); %'// delete 0's

Answer 2

MATLAB has this function NCHOOSEK for combinations, but this is for a fixed size only. So, we were needed to run this through a loop of varying sizes.

Code:

v=1:8;
for k = 1:numel(v)-1  
    in1 = nchoosek(v,k+1);
    your_func(in1);
end

Answer 3

Since you want permutations you will need to run perm on the results from nchoosek. Martrix S has combination results and matrix P below has the permutation result:

v = [1,2,3,4,5,6,7,8];
S ={};
for ii =1:length(v);
    S{ii} = nchoosek(v,ii);
end
P={};
for kk = 1:length(S)
    data = S{kk};
    for jj = 1:size(data,1)
        P{jj} = perms(data(jj,:));
    end
end

Answer 4

What you're looking for is the power set of your array. I don't know much about matlab, but Rosetta Code claims the following as an implementation of the algorithm, and it looks okay to me:

function pset = powerset(theSet)

    pset = cell(size(theSet)); %Preallocate memory

    %Generate all numbers from 0 to 2^(num elements of the set)-1
    for i = ( 0:(2^numel(theSet))-1 )

        %Convert i into binary, convert each digit in binary to a boolean
        %and store that array of booleans
        indicies = logical(bitget( i,(1:numel(theSet)) )); 

        %Use the array of booleans to extract the members of the original
        %set, and store the set containing these members in the powerset
        pset(i+1) = {theSet(indicies)};

    end

end