Dado un conjunto de caracteres y un entero positivo k, imprime todas las strings posibles de longitud k que se pueden formar a partir del conjunto dado.
Ejemplos:
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
Para un conjunto dado de tamaño n, habrá n^k strings posibles de longitud k. La idea es comenzar desde una string de salida vacía (lo llamamos prefijo en el siguiente código). Uno por uno agregue todos los caracteres al prefijo . Por cada carácter agregado, imprima todas las strings posibles con el prefijo actual llamando recursivamente a k igual a k-1.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to print all
// possible strings of length k
#include <bits/stdc++.h>
using namespace std;
// The main recursive method
// to print all possible
// strings of length k
void printAllKLengthRec(char set[], string prefix,
int n, int k)
{
// Base case: k is 0,
// print prefix
if (k == 0)
{
cout << (prefix) << endl;
return;
}
// One by one add all characters
// from set and recursively
// call for k equals to k-1
for (int i = 0; i < n; i++)
{
string newPrefix;
// Next character of input added
newPrefix = prefix + set[i];
// k is decreased, because
// we have added a new character
printAllKLengthRec(set, newPrefix, n, k - 1);
}
}
void printAllKLength(char set[], int k,int n)
{
printAllKLengthRec(set, "", n, k);
}
// Driver Code
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);
}
// This code is contributed
// by Mohit kumar
Java
// Java program to print all
// possible strings of length k
class GFG {
// The method that prints all
// possible strings of length k.
// It is mainly a wrapper over
// recursive function printAllKLengthRec()
static void printAllKLength(char[] set, int k)
{
int n = set.length;
printAllKLengthRec(set, "", n, k);
}
// The main recursive method
// to print all possible
// strings of length k
static void printAllKLengthRec(char[] set,
String prefix,
int n, int k)
{
// Base case: k is 0,
// print prefix
if (k == 0)
{
System.out.println(prefix);
return;
}
// One by one add all characters
// from set and recursively
// call for k equals to k-1
for (int i = 0; i < n; ++i)
{
// Next character of input added
String newPrefix = prefix + set[i];
// k is decreased, because
// we have added a new character
printAllKLengthRec(set, newPrefix,
n, k - 1);
}
}
// Driver Code
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);
}
}
Python3
# Python 3 program to print all
# possible strings of length k
# The method that prints all
# possible strings of length k.
# It is mainly a wrapper over
# recursive function printAllKLengthRec()
def printAllKLength(set, k):
n = len(set)
printAllKLengthRec(set, "", n, k)
# The main recursive method
# to print all possible
# strings of length k
def printAllKLengthRec(set, prefix, n, k):
# Base case: k is 0,
# print prefix
if (k == 0) :
print(prefix)
return
# One by one add all characters
# from set and recursively
# call for k equals to k-1
for i in range(n):
# Next character of input added
newPrefix = prefix + set[i]
# k is decreased, because
# we have added a new character
printAllKLengthRec(set, newPrefix, n, k - 1)
# Driver Code
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)
# This code is contributed
# by ChitraNayal
C#
// C# program to print all
// possible strings of length k
using System;
class GFG {
// The method that prints all
// possible strings of length k.
// It is mainly a wrapper over
// recursive function printAllKLengthRec()
static void printAllKLength(char[] set, int k)
{
int n = set.Length;
printAllKLengthRec(set, "", n, k);
}
// The main recursive method
// to print all possible
// strings of length k
static void printAllKLengthRec(char[] set,
String prefix,
int n, int k)
{
// Base case: k is 0,
// print prefix
if (k == 0)
{
Console.WriteLine(prefix);
return;
}
// One by one add all characters
// from set and recursively
// call for k equals to k-1
for (int i = 0; i < n; ++i)
{
// Next character of input added
String newPrefix = prefix + set[i];
// k is decreased, because
// we have added a new character
printAllKLengthRec(set, newPrefix,
n, k - 1);
}
}
// Driver Code
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);
}
}
// This code is contributed by Ajit.
Javascript
<script>
// Javascript program to print all
// possible strings of length k
// The method that prints all
// possible strings of length k.
// It is mainly a wrapper over
// recursive function printAllKLengthRec()
function printAllKLength(set,k)
{
let n = set.length;
printAllKLengthRec(set, "", n, k);
}
// The main recursive method
// to print all possible
// strings of length k
function printAllKLengthRec(set,prefix,n,k)
{
// Base case: k is 0,
// print prefix
if (k == 0)
{
document.write(prefix+"<br>");
return;
}
// One by one add all characters
// from set and recursively
// call for k equals to k-1
for (let i = 0; i < n; ++i)
{
// Next character of input added
let newPrefix = prefix + set[i];
// k is decreased, because
// we have added a new character
printAllKLengthRec(set, newPrefix,
n, k - 1);
}
}
// Driver Code
document.write("First Test<br>");
let set1=['a', 'b'];
let k = 3;
printAllKLength(set1, k);
document.write("<br>Second Test<br>");
let set2 = ['a', 'b', 'c', 'd'];
k = 1;
printAllKLength(set2, k);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
First Test aaa aab aba abb baa bab bba bbb Second Test a b c d
Complejidad temporal: O(n k )
Espacio Auxiliar: O(k)
La solución anterior es principalmente una generalización de esta publicación .
Este artículo es una contribución de Abhinav Ramana . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA