Permuting All Possible (0, 1) value arrays

Question

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 obviously 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!

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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;  

}