all possible *UNIQUE* permutations of a binary vector

3 ビュー (過去 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 件のコメント
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 ExchangeCreating and Concatenating Matrices についてさらに検索

Community Treasure Hunt

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

Start Hunting!

Translated by