Рубрики

Выведите все возможные строки длины k, которые могут быть сформированы из набора из n символов

Учитывая набор символов и положительное целое число k, выведите все возможные строки длины k, которые могут быть сформированы из данного набора.

Примеры:

Input: 
set[] = {'a', 'b'}, k = 3

Output:
aaa
aab
aba
abb
baa
bab
bba
bbb


Input: 
set[] = {'a', 'b', 'c', 'd'}, k = 1
Output:
a
b
c
d

Для заданного набора размера n будет n ^ k возможных строк длины k. Идея состоит в том, чтобы начать с пустой выходной строки (мы называем это префиксом в следующем коде). Один за другим добавьте все символы в префикс . Для каждого добавленного символа выведите все возможные строки с текущим префиксом, рекурсивно вызывая k равным k-1.
Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для печати всего
// возможные строки длины k
#include <bits/stdc++.h>

using namespace std;

      

  
// Основной рекурсивный метод
// напечатать все возможное
// строки длиной k

void printAllKLengthRec(char set[], string prefix,

                                    int n, int k)

{

      

    // Базовый случай: k равно 0,

    // распечатать префикс

    if (k == 0)

    {

        cout << (prefix) << endl;

        return;

    }

  

    // один за другим добавить все символы

    // из множества и рекурсивно

    // вызов для k равен k-1

    for (int i = 0; i < n; i++)

    {

        string newPrefix;

          

        // Добавлен следующий символ ввода

        newPrefix = prefix + set[i];

          

        // k уменьшается, потому что

        // мы добавили нового персонажа

        printAllKLengthRec(set, newPrefix, n, k - 1);

    }

  
}

  

void printAllKLength(char set[], int k,int n)

{

    printAllKLengthRec(set, "", n, k);

}

  
// Код драйвера

int main()

{

      

    cout << "First Test" << endl;

    char set1[] = {'a', 'b'};

    int k = 3;

    printAllKLength(set1, k, 2);

      

    cout << "Second Test\n";

    char set2[] = {'a', 'b', 'c', 'd'};

    k = 1;

    printAllKLength(set2, k, 4);

}

  
// Этот код добавлен
// Мохит Кумар

Джава

// Java программа для печати всех
// возможные строки длины k

  

class GFG {

      
// Метод, который печатает все
// возможные строки длины k.
// Это в основном оболочка над
// рекурсивная функция printAllKLengthRec ()

static void printAllKLength(char[] set, int k)

{

    int n = set.length; 

    printAllKLengthRec(set, "", n, k);

}

  
// Основной рекурсивный метод
// напечатать все возможное
// строки длиной k

static void printAllKLengthRec(char[] set, 

                               String prefix, 

                               int n, int k)

{

      

    // Базовый случай: k равно 0,

    // распечатать префикс

    if (k == 0

    {

        System.out.println(prefix);

        return;

    }

  

    // один за другим добавить все символы

    // из множества и рекурсивно

    // вызов для k равен k-1

    for (int i = 0; i < n; ++i)

    {

  

        // Добавлен следующий символ ввода

        String newPrefix = prefix + set[i]; 

          

        // k уменьшается, потому что

        // мы добавили нового персонажа

        printAllKLengthRec(set, newPrefix, 

                                n, k - 1); 

    }

}

  
// Код драйвера

public static void main(String[] args)

{

    System.out.println("First Test");

    char[] set1 = {'a', 'b'};

    int k = 3;

    printAllKLength(set1, k);

      

    System.out.println("\nSecond Test");

    char[] set2 = {'a', 'b', 'c', 'd'};

    k = 1;

    printAllKLength(set2, k); 

}
}

Python 3

# Python 3 программа для печати всех
# возможные строки длины k

      
# Метод, который печатает все
# возможные строки длины k.
# Это в основном оболочка над
# рекурсивная функция printAllKLengthRec ()

def printAllKLength(set, k):

  

    n = len(set

    printAllKLengthRec(set, "", n, k)

  
# Основной рекурсивный метод
# распечатать все возможное
# строки длины k

def printAllKLengthRec(set, prefix, n, k):

      

    # Базовый случай: k равно 0,

    # префикс печати

    if (k == 0) :

        print(prefix)

        return

  

    # Один за другим добавьте всех персонажей

    # из набора и рекурсивно

    # вызов для k равен k-1

    for i in range(n):

  

        # Добавлен следующий символ ввода

        newPrefix = prefix + set[i]

          

        # k уменьшается, потому что

        # мы добавили нового персонажа

        printAllKLengthRec(set, newPrefix, n, k - 1)

  
Код водителя

if __name__ == "__main__":

      

    print("First Test")

    set1 = ['a', 'b']

    k = 3

    printAllKLength(set1, k)

      

    print("\nSecond Test")

    set2 = ['a', 'b', 'c', 'd']

    k = 1

    printAllKLength(set2, k)

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для печати всех
// возможные строки длины k

using System;

  

class GFG {

      
// Метод, который печатает все
// возможные строки длины k.
// Это в основном оболочка над
// рекурсивная функция printAllKLengthRec ()

static void printAllKLength(char[] set, int k)

{

    int n = set.Length; 

    printAllKLengthRec(set, "", n, k);

}

  
// Основной рекурсивный метод
// напечатать все возможное
// строки длиной k

static void printAllKLengthRec(char[] set

                               String prefix, 

                               int n, int k)

{

      

    // Базовый случай: k равно 0,

    // распечатать префикс

    if (k == 0) 

    {

        Console.WriteLine(prefix);

        return;

    }

  

    // один за другим добавить все символы

    // из множества и рекурсивно

    // вызов для k равен k-1

    for (int i = 0; i < n; ++i)

    {

  

        // Добавлен следующий символ ввода

        String newPrefix = prefix + set[i]; 

          

        // k уменьшается, потому что

        // мы добавили нового персонажа

        printAllKLengthRec(set, newPrefix, 

                                n, k - 1); 

    }

}

  
// Код драйвера

static public void Main ()

{

    Console.WriteLine("First Test");

    char[] set1 = {'a', 'b'};

    int k = 3;

    printAllKLength(set1, k);

      

    Console.WriteLine("\nSecond Test");

    char[] set2 = {'a', 'b', 'c', 'd'};

    k = 1;

    printAllKLength(set2, k); 

}
}

  
// Этот код предоставлен Ajit.


Выход:

First Test
aaa
aab
aba
abb
baa
bab
bba
bbb

Second Test
a
b
c
d

Вышеуказанное решение является в основном обобщением этого поста .

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

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

Выведите все возможные строки длины k, которые могут быть сформированы из набора из n символов

0.00 (0%) 0 votes