Рубрики

Создайте все двоичные перестановки так, чтобы перед каждой точкой во всех перестановках было больше или равно 1, чем 0

Генерация всех перестановок заданной длины, так что каждая перестановка имеет больше или равно 1, чем 0 во всех префиксах перестановки.

Примеры:

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 

Как и задачи генерации перестановок, рекурсия — самый простой подход для решения этой проблемы. Мы начинаем с пустой строки, присоединяем к ней 1 и повторяем. При повторении, если мы найдем больше 1 в любой точке, мы добавим 0 и сделаем еще один рекурсивный вызов.

Ниже приведена реализация:

C ++

// C ++ программа для генерации всех перестановок единиц и единиц, таких, что
// каждая перестановка имеет больше 1, чем 0 во всех индексах.
#include <iostream>
#include <cstring>

using namespace std;

  
// единицы и нули -> количество единиц и 0 в текущей строке 'str'
// len ---> желаемая длина каждой перестановки

void generate(int ones, int zeroes, string str, int len)

{

    // Если длина текущей строки становится такой же, как желаемая длина

    if (len == str.length())

    {

        cout << str << "  ";

        return;

    }

  

    // Добавить 1 и повторить

    generate(ones+1, zeroes, str+"1", len);

  

    // Если есть еще 1, добавляем также 0 и повторяем

    if (ones > zeroes)

        generate(ones, zeroes+1, str+"0", len);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    string str = "";

    generate(0, 0, str, 4);

    return 0;

}

Джава

// Java-программа для генерации всех перестановок единиц и единиц, таких что
// каждая перестановка имеет больше 1, чем 0 во всех индексах.

  

class GFG {

  
// единицы и нули -> количество единиц и 0 в текущей строке 'str'
// len ---> желаемая длина каждой перестановки

    static void generate(int ones, int zeroes, String str, int len) {

        // Если длина текущей строки становится такой же, как желаемая длина

        if (len == str.length()) {

            System.out.print(str + " ");

            return;

        }

  

        // Добавить 1 и повторить

        generate(ones + 1, zeroes, str + "1", len);

  

        // Если есть еще 1, добавляем также 0 и повторяем

        if (ones > zeroes) {

            generate(ones, zeroes + 1, str + "0", len);

        }

    }

  
// Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) {

        String str = "";

        generate(0, 0, str, 4);

    }

}

  
/ * Этот код Java предоставлен PrinciRaj1992 * /

python3

# Программа Python 3 для генерации всех перестановок единиц и единиц, таких, что
# каждая перестановка имеет больше 1, чем 0 во всех индексах.

  
# one & zeroes -> количество единиц и 0 в текущей строке 'str'
# len ---> желаемая длина каждой перестановки

def generate(ones, zeroes, str, len1):

    # Если длина текущей строки становится такой же, как желаемая длина

    if (len1 == len(str)):

        print(str,end =" ")

        return

      

    # Добавить 1 и повторить

    generate(ones+1, zeroes, str+"1", len1)

  

    # Если есть еще 1, добавьте также 0 и повторите

    if (ones > zeroes):

        generate(ones, zeroes+1, str+"0", len1)

  
# Программа драйвера для проверки вышеуказанной функции

if __name__ == '__main__':

    str = ""

    generate(0, 0, str, 4)

  
# Этот код предоставлен
# Surendra_Gangwar

  

C #

// C # программа для генерации всех перестановок 1 и 0 так, чтобы
// каждая перестановка имеет больше 1, чем 0 во всех индексах.

   

using System;

                      

  

public class GFG {

   
// единицы и нули -> количество единиц и 0 в текущей строке 'str'
// len ---> желаемая длина каждой перестановки

    static void generate(int ones, int zeroes, String str, int len) {

        // Если длина текущей строки становится такой же, как желаемая длина

        if (len == str.Length) {

            Console.Write(str + " ");

            return;

        }

   

        // Добавить 1 и повторить

        generate(ones + 1, zeroes, str + "1", len);

   

        // Если есть еще 1, добавляем также 0 и повторяем

        if (ones > zeroes) {

            generate(ones, zeroes + 1, str + "0", len);

        }

    }

   
// Программа драйвера для проверки вышеуказанной функции

    public static void Main() {

        String str = "";

        generate(0, 0, str, 4);

    }

}

   
/ * Этот Java-код предоставлен 29AjayKumar * /


Выход:

1111  1110  1101  1100  1011  1010

Эта статья предоставлена Sachin . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Создайте все двоичные перестановки так, чтобы перед каждой точкой во всех перестановках было больше или равно 1, чем 0

0.00 (0%) 0 votes