all possible *UNIQUE* permutations of a binary vector

2 次查看（过去 30 天）
eyal lampel
eyal lampel 2013-6-11
评论： winkmal 2020-9-25
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.

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

采纳的回答

Andrei Bobrov
Andrei Bobrov 2013-6-11
编辑：Andrei Bobrov 2013-6-12
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更早的评论
Ash Ash
Ash Ash 2019-6-12
编辑：Ash Ash 2019-6-12
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
winkmal 2020-9-25
编辑：winkmal 2020-9-25
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');

请先登录，再进行评论。

更多回答（1 个）

Jan
Jan 2013-6-11
编辑：Jan 2013-6-11
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
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
winkmal 2020-9-25
I wanted to try your solution, but VChooseK never finished... :(

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by