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.
Below is the implementation:
C++
// 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; } |
Java
// Java 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. class GFG { // ones & zeroes --> counts of 1's and 0's in current string 'str' // len ---> desired length of every permutation static void generate(int ones, int zeroes, String str, int len) { // If length of current string becomes same as desired length if (len == str.length()) { System.out.print(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 public static void main(String[] args) { String str = ""; generate(0, 0, str, 4); } } /* This Java code is contributed by PrinciRaj1992*/ |
Python3
# Python 3 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. # ones & zeroes --> counts of 1's and 0's in current string 'str' # len ---> desired length of every permutation def generate(ones, zeroes, str, len1): # If length of current string becomes same as desired length if (len1 == len(str)): print(str,end =" ") return # Append a 1 and recur generate(ones+1, zeroes, str+"1", len1) # If there are more 1's, append a 0 as well, and recur if (ones > zeroes): generate(ones, zeroes+1, str+"0", len1) # Driver program to test above function if __name__ == '__main__': str = "" generate(0, 0, str, 4) # This code is contributed by # Surendra_Gangwar |
C#
// 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. using System; public class GFG { // ones & zeroes --> counts of 1's and 0's in current string 'str' // len ---> desired length of every permutation static void generate(int ones, int zeroes, String str, int len) { // If length of current string becomes same as desired length if (len == str.Length) { Console.Write(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 public static void Main() { String str = ""; generate(0, 0, str, 4); } } /* This Java code is contributed by 29AjayKumar*/ |
Output:
1111 1110 1101 1100 1011 1010
leave a comment
0 Comments