Creating permutations of all possible non-repeated combinations within N elements

Dear all, was wondering if i) there is a name for the following combinatorics problem; ii) is there a way to code it within Matlab and generate all results?

I have N elements, and would like to generate all possible permutations of non-repeated combinations with varying bracket sizes. For instance, for N = 5 elements, we have the following possible permutations:

• Max group combination size of 5: (ABCDE)
• Max group combination size of 4: (A) (BCDE); (BCDE) (A); (B) (ACDE); (ACDE) (B); (C) (ABDE); (D) (ABCE); (E)(ABCD) etc.
• Max group combination size of 3: (AB) (CDE); (A) (B) (CDE); (AC) (BCD); (A) (C) (BCD) etc.
• Max group combination size of 2: (AB) (CD) (E); (AB) (C) (D) (E); (AB) (CE) (D) etc.
• Max group combination size of 1: (A) (B) (C) (D) (E); (B) (C) (D) (E) (A); etc.

Note that, within the brackets, order does not matter i.e. they are just combinations. But beyond the brackets, permutation must occur, for instance, (AB) (CDE) and (CDE) (AB) are two possible permutations.

My apologies in advance for the unclear/vague wording. Thank you for your help!

Answer 1

[Guillaume]

Ignoring for a moment your requirement that "beyond the brackets, permutation must occur", you're asking for all the partitions of a set (the number of which is given by the Bell number. A search gives a number of algorithms here, and here for example and even a submission on matlab's file exchange.

Your additional requirement that permutations of subsets are to be taken into account is odd, but once you've generated the partitions, you can use perms to generate these:

N = 5;
partitions = SetPartition(N); %using Bruno Luong's submission on file exchange
generatepermutations = @(partition) cellfun(@(p) partition(p), num2cell(perms(1:numel(partition)), 2), 'UniformOutput', false);
permparts = cellfun(generatepermutations, partitions, 'UniformOutput', false);
permparts = vertcat(permparts{:});

[eugene479]

Thank you so much for the very elegant solution! Deeply appreciated, especially since I'm just starting out on Matlab.

Answer 2

[the cyclist]

This is known as "partitioning" a set. I'm not sure if there is anything in base MATLAB to do this, but there are some entries on the File Exchange for doing this. Here is one.

[eugene479]

Thank you for your help!