MATLAB Answers

Permutations of array retaining sub-array groups together

7 views (last 30 days)
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.

  0 Comments

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 13 Sep 2020
Edited: Bruno Luong on 13 Sep 2020
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{:})

More Answers (1)

Sindar
Sindar on 13 Sep 2020
Edited: Sindar on 13 Sep 2020
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)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by