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

Question

Matt Slattery-Holmes 2022-8-14

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1779280-i-want-to-find-all-order-preserving-shuffles-of-two-vectors

评论： Matt Slattery-Holmes 2022-8-14

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!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2022-8-14

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1779280-i-want-to-find-all-order-preserving-shuffles-of-two-vectors#answer_1026415

编辑：Jan 2022-8-14

在 MATLAB Online 中打开

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Matt Slattery-Holmes 2022-8-14

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!

请先登录，再进行评论。