all possible UNIQUE permutations of a binary vector

Question

eyal lampel 2013-6-11

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/78669-all-possible-unique-permutations-of-a-binary-vector

评论： winkmal 2020-9-25

采纳的回答： Andrei Bobrov

在 MATLAB Online 中打开

hello all, i am trying to make a griddler/nonogram puzzel solver with matlab.

to do so i need to find all possible UNIQUE permutations of a binary vector. for example :

input Vector: [1 0 1 0]

output matrix:

          [1 0 1 0       
           1 0 0 1
           0 1 0 1
           0 0 1 1
           0 1 1 0
           1 1 0 0]
 untile now i've been using the following code:
  if true
    inVec=[1 0 1 0]
    outMat=perms(inVec);
    outMat=unique(outMat,'rows')
  end

This was perfectly fine but for inVec longer then 10 i get an: 'out of memory' error.

is it possible to do this without using perms/unique ? i need this for up to inVec length 20.

Thanks Lampel.

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

请先登录，再进行评论。

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

Answer 1

Andrei Bobrov 2013-6-11

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/78669-all-possible-unique-permutations-of-a-binary-vector#answer_88409

编辑：Andrei Bobrov 2013-6-12

在 MATLAB Online 中打开

c = [0 1];
cc = c(fullfact([2 2 2 2]));
out = cc(sum(cc,2) == 2,:);

ADD: use Roger Stafford's idea from answer

A = [1 1 0 0];
n = numel(A);
k = sum(A);
c = nchoosek(1:n,k);
m = size(c,1);
out = zeros(m,n);
out(sub2ind([m,n],(1:m)'*[1 1],c)) = 1;

4 个评论
显示 2更早的评论隐藏 2更早的评论

Ash Ash 2019-6-12

编辑：Ash Ash 2019-6-12

在 MATLAB Online 中打开

A = [1 1 0 0];
n = numel(A);
k = sum(A);
c = nchoosek(1:n,k);
m = size(c,1);
out = zeros(m,n);
% out(sub2ind([m,n],(1:m)'*[1 1],c)) = 1;
out(sub2ind([m,n],(1:m)'*ones(1,k),c

I suggest this minor edit to accomodate any type of A input

winkmal 2020-9-25

编辑：winkmal 2020-9-25

在 MATLAB Online 中打开

I guess instead of

out(sub2ind([m,n],(1:m)'*ones(1,k),c

you meant:

out(sub2ind([m,n],(1:m)'*ones(1,k),c)) = 1;

Also, I have found slightly better performance with

out = zeros(m, n, 'uint8');

请先登录，再进行评论。

Answer 2

Jan 2013-6-11

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/78669-all-possible-unique-permutations-of-a-binary-vector#answer_88410

编辑：Jan 2013-6-11

在 MATLAB Online 中打开

Using UINT8 instead of DOUBLE will reduce the memroy footprint by a factor of 8.

[EDITED] Bad statistics removed. For 20 elements with 10 enabled bits you get 20!/(10! * (20-10)!) possible solutions, which mean 184'756 * 20 bytes if you use UINT8 values.

Another solution if speed matters: FEX: VChooseK

nElem    = 20;
nEnabled = 10;
Index    = VChooseK(uint8(1):uint8(nElem), nEnabled);
Result   = [under construction], see Andrei's solution

2 个评论
显示无隐藏无

eyal lampel 2013-6-11

Thanks jan It was very helpfull to know UINT8 reduce the memory print by a factor of 8. permutation of 20 elements leads to huge number. BUT becuse this is a binary vector the unique vectors is not such a large number.

winkmal 2020-9-25