How to obtain discernable permutations of a vector ?

Hi everyone,

I have the following problem : let's say I have the vector v=(1,1,1,0,0) and I want to generate the permutations of this vector. The problem is, if I simply use perms(v), matlab is going to generate many degenerate vectors because it does not understand that the elements of my vector are similar (so for instance I will have like ten exemplars of (1,0,1,1,0) , then ten of (0,1,1,1,0), etc). Of course I can easily make a code that gets rid of those degenerate vectors, but it is very time consuming when the length of the vector gets bigger.

Thank you for your help guys.

Alex.

Answer 1

[Roger Stafford]

In your particular example, (1,1,1,0,0), the number of possible distinct permutations is 5!/3!/2! = 10 (corrected), and these can be generated using matlab's 'nchoosek' function. In general if there are a copies of one number, b of another number, c of another, d of another, etc., the total number of distinct permutations will be (a+b+c+d+...)!/(a!*b!*c!*d!*...). In Answers #69232, #84215, and #140986, as well as newsgroup #337667, I have given examples of ways of calling on 'nchoosek' to solve problems of this kind.

Answer 2

[szenicer]

Hi Roger,

Thanks for your answer. I've tried your code, it's great ! Concerning the exemple with (1,1,1,0,0), could you explain the way you're using nchoosek to generate those distinct permutations? Because that was also my first idea but I couldn't get anything simple. Maybe I've missed something trivial there.

Thanks again.

Alex.

[Roger Stafford]

   x = [1,1,1,0,0];
   n = size(x,2);
   k = nnz(x);

   C = nchoosek(1:n,k);
   m = size(C,1);
   A = zeros(m,n);
   for ix = 1:m
     A(ix,C(ix,:)) = 1;
   end

The ten rows of A will have all possible distinct permutations of the 1's and 0's in x.

[szenicer]

Oh I see, thanks so much !