How to generate all collections of n subsets of 1:v?

So for example, given n=3 and v=2, then I would want the function to generate:

{[1],[1],[1]}

{[1],[1],[2]}

{[1],[2],[2]}

{[2],[2],[2]}

{[1],[1],[1,2]}

{[1],[1,2],[2]}

{[1],[1,2],[1,2]}

{[1,2],[1,2],[1,2]}

{[1,2],[1,2],[2]}

{[1,2],[2],[2]}

As you can see I want to allow repetition in the n elements of each collection but no repetition within each subset (ie {[1],[1]} is allowed but {[1,1]} is not).

Many thanks in advance for any help.

[Steven Lord]

How large values of n and v do you want to use? Knowing this will help determine if what you're asking is feasible or would require multiple universes worth of atoms to store the results.

[mapmap]

@Steven Lord Preferably up to about n,v=8 but anything would be better than nothing.

[Bruno Luong]

For n=8 and v=8 you would have

>> (2^8-1)^8

ans =

   1.7878e+19

possible combinations.

[Steven Lord]

That's a lot of possible combinations. Probably not "more atoms than there are in the universe" but definitely "would take an infeasibly large amount of time to process each collection". At 1 combination per second:

>> years(seconds((2^8-1)^8))
ans =
          566534541986.593

If you explain more about the problem you're trying to solve where you think you need to generate all these collections, we may be able to suggest a more efficient method of solving that problem without brute-forcing about 1.8e19 combinations.

Answer 1

[Bruno Luong]

v = 2;
n = 3;
B = 1:2^v-1;
c = repmat({B},1,n);
[c{:}] = ndgrid(c{:});
c = cat(n+1,c{:});
c = reshape(c,[],n);
B = arrayfun(@(b) find(dec2bin(b,v)-'0'), B, 'unif', 0);
R = B(c);

for k=1:size(R)
    cellfun(@(a) fprintf('[%s] ', num2str(a)), R(k,:));
    fprintf('\n');
end

Result is

[2] [2] [2] 
[1] [2] [2] 
[1  2] [2] [2] 
[2] [1] [2] 
[1] [1] [2] 
[1  2] [1] [2] 
[2] [1  2] [2] 
[1] [1  2] [2] 
[1  2] [1  2] [2] 
[2] [2] [1] 
[1] [2] [1] 
[1  2] [2] [1] 
[2] [1] [1] 
[1] [1] [1] 
[1  2] [1] [1] 
[2] [1  2] [1] 
[1] [1  2] [1] 
[1  2] [1  2] [1] 
[2] [2] [1  2] 
[1] [2] [1  2] 
[1  2] [2] [1  2] 
[2] [1] [1  2] 
[1] [1] [1  2] 
[1  2] [1] [1  2] 
[2] [1  2] [1  2] 
[1] [1  2] [1  2] 
[1  2] [1  2] [1  2] 

Answer 2

[Andrei Bobrov]

v = 2;
n = 3;

s = 1:v;
c = [];
for ii = 1:v
    k = num2cell(nchoosek(s,ii),2);
    c = [c, k(:)'];
end
idx = fullfact(ones(1,n)*numel(c));
out = c(idx);