all possible *UNIQUE* permutations of a binary vector

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.

Answer 1

[Andrei Bobrov]

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;

[Andrei Bobrov]

see ADD part

[eyal lampel]

Thanks! Roger Stafford's answer was exactly what I was looking for

[Ash Ash]

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]

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]

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

[eyal lampel]

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]

I wanted to try your solution, but VChooseK never finished... :(