Permuting All Possible (0, 1) value arrays

I am having writing an algorithm to generate all possible permutations of an array of this kind:

n = length

k = number of 1's in array

So this means if we have k 1's we will have n-k 0's in the array.

For example: n = 5; k = 3;

So o开发者_运维百科bviously there are 5 choose 3 possible permutations for this array because

n!/(k!(n-k)!

5!/(3!2!) = (5*4)/2 = 10

possible values for the array

Here are all the values:

11100

11010

11001

10110

10101

10011

01110

01101

01011

00111

I am guessing i should use a recursive algorithms but i am just not seeing it. I am writing this algorithm in C++.

Any help would be appreciated!

Just start with 00111 and then use std::next_permutation to generate the rest:

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s = "00111";
    do
    {
        std::cout << s << '\n';
    }
    while (std::next_permutation(s.begin(), s.end()));
}

output:

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

You can split up the combinations into those starting with 1 (n-1, k-1) and those starting with 0 (n-1, k).

This is essentially the recursive formula for the choose function.

What you want is actually a combination since the 1's and 0's are indistinguishable and therefore their order doesn't matter (e.g. 1 1 1 vs 1 1 1).

I recently had to rewrite a combination function myself because my initial version was written recursively in a very straightforward way (pick an element, get all the combinations of the remaining array, insert the element in various places) and did not perform very well.

I searched StackOverflow and just seeing the pictures in this answer lit up the iconic lightbulb over my head.

If you want to do this recursively, observe that the set of permutations you want is equal to all the ones that start with "1", together with all the ones that start with "0". So in calculating (n,k), you will recurse on (n-1,k-1) and (n-1,k), with special cases where k = 0 and k = n.

This recursion is the reason that the binomial coefficients appear as the values in Pascal's triangle.

Homework and recursive algorithm? OK, here you go:

Base case: You have two elements, name them "a" and "b" and produce the concatenations ab, then ba.

Step: If your second Element is longer than 1, split it up in first field/letter and the other part, and pass that recursively as parameters to the function itself.

That will work for any strings and arrays.

Its about 0-1 permutations, so probably its much more eficient to iteratively increment an integer and in case it has desired bits count, print out its binary representation.

Here a sketch:

void printAllBinaryPermutations(int k, int n)  
{  
  int max = pow(2, n) - 1;  
  for(int i=0; i<=max;i++)  
  {  
    if(hasBitCountOf(i, k)) // i has k 1's?  
    {  
      printAsBinary(i, n);  
    }  
  }  
}  


bool hasBitCountOf(int v, int expectedBitCount)  
{  
    int count = 0;  
    while(v>0 && count<= expectedBitCount)  
    {  
        int half = v >> 1;  
        if(half<<1 != v)  
        {  
            // v is odd  
            count++;  
        }  
        v = half;  
    }  

    return count==expectedBitCount;  
}  


void printAsBinary(int number, int strLen)  
{  
  for(int i=strLen-1; i>=0; i--)  
  {  
    bool is0 = (number & pow(2,i)) == 0;  
    if (is0)  
    {  
      cout<<'0';  
    }  
    else  
    {  
      cout<<'1';  
    }  
  }   

  cout<<endl;  

}

I am not sure this helps, plus it is just some weird pseudocode, but this should give you the desired ouput.

permutation (prefix, ones, zeros, cur) {
    if (ones + zeros == 0) output(cur);
    else {
        if (cur != -1) prefix = concat(prefix,cur);
        if (ones > 0) permutation(prefix, ones - 1, zeros, 1);
        if (zeros > 0) permutation(prefix, ones, zeros - 1, 0);
    }        
}

permutation(empty, 3, 2, -1);

greetz
back2dos