I want to find all order-preserving shuffles of two vectors

3 views (last 30 days)
Say I have two vectors a1 = [3,1,1] and a2 = [4,2] and I want to find all ways of combining these two vectors which preserve the order of the individual vectors elements'
So here, my output might look like
3,1,1,4,2
3,1,4,1,2
3,1,4,2,1
3,4,1,2,1
3,4,2,1,1
4,3,2,1,1
4,2,3,1,1
3,4,1,1,2
4,3,1,1,2
4,3,1,2,1
I know that there is nchoosek(length(a1)+length(a2),length(a1)) vectors in the output, but I am not sure if there is a nice easy function already existing which does this for me, or if I need to cobble something together, and if it is the latter, could anyone suggest a way that would do this efficiently?
Also, the order of the output elements doesnt matter.
Thanks!

Accepted Answer

Jan
Jan on 14 Aug 2022
Edited: Jan on 14 Aug 2022
3 methods for educational purpose:
a = [3,1,1];
b = [4,2];
na = numel(a);
nb = numel(b);
% Indices of elements of the vector a in the output matrix R:
v = 1:na + nb;
ind = nchoosek(v, na);
nR = size(ind, 1);
R = zeros(nR, na + nb);
for k = 1:nR
inda = ind(k, :);
R(k, inda) = a;
indb = v;
indb(inda) = [];
R(k, indb) = b;
end
R
R = 10×5
3 1 1 4 2 3 1 4 1 2 3 1 4 2 1 3 4 1 1 2 3 4 1 2 1 3 4 2 1 1 4 3 1 1 2 4 3 1 2 1 4 3 2 1 1 4 2 3 1 1
% Alternative 1:
Q = false(nR, na + nb);
Q(sub2ind(size(Q), repelem((1:nR)', 1, na), ind)) = true;
R = zeros(nR, na + nb);
for k = 1:nR
R(k, Q(k, :)) = a;
R(k, ~Q(k, :)) = b;
end
R
R = 10×5
3 1 1 4 2 3 1 4 1 2 3 1 4 2 1 3 4 1 1 2 3 4 1 2 1 3 4 2 1 1 4 3 1 1 2 4 3 1 2 1 4 3 2 1 1 4 2 3 1 1
% Alternative 2:
Q = false(na + nb, nR);
Q(sub2ind(size(Q), ind, repelem((1:nR)', 1, na))) = true;
R = zeros(na + nb, nR);
R(Q) = repmat(a, 1, nR);
R(~Q) = repmat(b, 1, nR);
R = R.'
R = 10×5
3 1 1 4 2 3 1 4 1 2 3 1 4 2 1 3 4 1 1 2 3 4 1 2 1 3 4 2 1 1 4 3 1 1 2 4 3 1 2 1 4 3 2 1 1 4 2 3 1 1
Try which version is faster for your data.
  1 Comment
Matt Slattery-Holmes
Matt Slattery-Holmes on 14 Aug 2022
Thank you very much. I managed to brute force this after asking the question, but the way I found is horrible and slow, the methods you have come up with are much nicer!

Sign in to comment.

More Answers (0)

Community Treasure Hunt

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

Start Hunting!