Algorithm C++ programming Coding

C++ Programming – Generate all binary permutations

Generate all permutations of given length such that every permutation has more or equal 1’s than 0’s in all prefixes of the permutation.

Generate all permutations of given length such that every permutation has more or equal 1’s than 0’s in all prefixes of the permutation.

Examples:

Input: len = 4
Output: 1111 1110 1101 1100 1011 1010
Note that a permutation like 0101 can not be in output because
there are more 0's from index 0 to 2 in this permutation.

Input: len = 3
Output: 111 110 101

Input: len = 2
Output: 11 10

Like permutation generation problems, recursion is the simplest approach to solve this. We start with an empty string, attach 1 to it and recur. While recurring, if we find more 1’s at any point, we append a 0 and make one more recursive call.

C++ Program
// C++ program to generate all permutations of 1's and 0's such that
// every permutation has more 1's than 0's at all indexes.
#include <iostream>
#include <cstring>
using namespace std;
 
// ones & zeroes --> counts of 1's and 0's in current string 'str'
// len ---> desired length of every permutation
void generate(int ones, int zeroes, string str, int len)
{
    // If length of current string becomes same as desired length
    if (len == str.length())
    {
        cout << str << "  ";
        return;
    }
 
    // Append a 1 and recur
    generate(ones+1, zeroes, str+"1", len);
 
    // If there are more 1's, append a 0 as well, and recur
    if (ones > zeroes)
        generate(ones, zeroes+1, str+"0", len);
}
 
// Driver program to test above function
int main()
{
    string str = "";
    generate(0, 0, str, 4);
    return 0;
}

Output:

1111  1110  1101  1100  1011  1010
READ  C++ Programming - Construct an array from its pair-sum array

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment