Permutations of array retaining sub-array groups together

How can I obtain in an efficient way all the permutations of an array with n elements such that all the sub-array groups defined are always together?

For example: Consider the array [ 1 (2 3) 4 ]. Here (2,3) is one sub-group and the parentheses are just put for clarity. Output expected is then: [ 1 (2 3) 4 ; 1 (3 2) 4 ; 1 4 (2 3) ; 1 4 (3 2) ; ... so on].

There can be multiple such groups and the groups can be comprised of more than 2 elements as well. So, let's say A = [ 1 2 3 4 5 6 7 8] is the array to be permuted and there is another vector of same size containing information about the groups like G = [ 1 2 2 2 3 4 5 5 ] implying that I need to permute [1 (2 3 4) 5 6 (7 8)]. This way of describing the arrays to approach the problem is just a suggestion but I am open to better suggestions. Thanks a lot for your time.

Answer 1

[Bruno Luong]

Try this:

A = [ 1 2 3 4 5 6 7 8]
G = [ 1 2 2 2 3 4 5 5 ]

l = diff(find([true,diff(G)>0,true]));
Ag = mat2cell(A, 1, l);
Ap = cellfun(@perms, Ag, 'unif',0);
I = cellfun(@(x) 1:size(x,1), Ap, 'unif',0);
[I{:}] = ndgrid(I{:});
AP = cellfun(@(Ap,r) Ap(r,:), Ap, I, 'unif',0);
c = perms(unique(G));
AP = arrayfun(@(i) cell2mat(AP(:,c(i,:))), 1:size(c,1), 'unif', 0);
AP = cat(1, AP{:})

[Sumit Chourasiya]

Thanks.

Answer 2

[Sindar]

I believe the best way to describe your arrays-with-subgroups is using cell arrays:

my_array =  {1 [2 3] 4}
my_array = 
    {[1]}    {1×2 double}    {[4]}

Then, you can use perms to permute the order of the cells:

my_array_permutations = perms(my_array)
my_array_permutations = 
    {[       4]}    {1×2 double}    {[       1]}
    {[       4]}    {[       1]}    {1×2 double}
    {1×2 double}    {[       4]}    {[       1]}
    {1×2 double}    {[       1]}    {[       4]}
    {[       1]}    {[       4]}    {1×2 double}
    {[       1]}    {1×2 double}    {[       4]}
    

I haven't quite figured out how to get the whole thing back as a normal matrix, but mashing it into cell2mat in the right way is a possibility. This will at least work for individual rows:

cell2mat(my_array_permutations(1,:))
ans = 1×4    
     4     2     3     1

For the general problem, an easy way to create these sort of cell arrays is by listing the number of elements per subgroup:

A = [ 1 2 3 4 5 6 7 8]
% [1 (2 3 4) 5 6 (7 8)]
% G = [ 1 2 2 2 3 4 5 5 ]
G = [1 3 1 1 2];
A_g = mat2cell(A,1,G)
A_grouped = 
    {[1]}    {1×3 double}    {[5]}    {[6]}    {1×2 double}
A_perms = perms(A_grouped);

Finally, you might want to add a pre-emptive check of whether you can actually handle the number of permutations, since factorials grow very fast (5 subgoups: 120 perms | 10 groups: 3 million perms | 20 groups: 2e18 perms)

[Sumit Chourasiya]

Thanks a lot. This works as well.