Permutations of array retaining sub-array groups together

5 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.

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)

Categories

Find more on Creating and Concatenating Matrices in Help Center and File Exchange

Products


Release

R2019b

Community Treasure Hunt

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

Start Hunting!