Genere todas las permutaciones binarias de manera que haya más o iguales 1 que 0 antes de cada punto en todas las permutaciones

Genere todas las permutaciones de una longitud determinada de modo que cada permutación tenga más o sea igual a 1 que a 0 en todos los prefijos de la permutación.
 

Ejemplos: 

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 

Al igual que los problemas de generación de permutaciones, la recursividad es el enfoque más simple para resolver esto. Comenzamos con una string vacía, le adjuntamos 1 y recurrimos. Mientras es recurrente, si encontramos más 1 en cualquier punto, agregamos un 0 y hacemos una llamada recursiva más.
A continuación se muestra la implementación: 

// 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 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*/

# 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# 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*/

<script>
      // JavaScript 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
      function generate(ones, zeroes, str, len) {
          // If length of current string becomes same as desired length
        if (len === str.length) {
            document.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
      var str = "";
      generate(0, 0, str, 4);
</script>

Producción: 

1111  1110  1101  1100  1011  1010

Complejidad de tiempo: O(2 ^N ), ya que estamos usando dos llamadas recursivas. Donde N es la longitud dada de la string.

Espacio Auxiliar: O(N)

Este artículo fue aportado por Sachin . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.