Dado un conjunto de caracteres, genera todas las contraseñas posibles a partir de ellos. Esto significa que debemos generar todas las permutaciones posibles de palabras usando los caracteres dados, con repeticiones y también hasta una longitud determinada.
Ejemplos:
Input : arr[] = {a, b},
len = 2.
Output :
a b aa ab ba bb
La solución es usar la recursión en la array de caracteres dada. La idea es pasar todas las longitudes posibles y una string vacía inicialmente a una función auxiliar. En la función auxiliar, seguimos agregando todos los caracteres uno por uno a la string actual y recurrimos para llenar la string restante hasta alcanzar la longitud deseada.
Se puede visualizar mejor utilizando el siguiente árbol de recursión:
(a, b)
/ \
a b
/ \ / \
aa ab ba bb
A continuación se muestra la implementación del método anterior.
C++
// C++ program to generate all passwords for given characters
#include <bits/stdc++.h>
using namespace std;
// int cnt;
// Recursive helper function, adds/removes characters
// until len is reached
void generate(char* arr, int i, string s, int len)
{
// base case
if (i == 0) // when len has been reached
{
// print it out
cout << s << "\n";
// cnt++;
return;
}
// iterate through the array
for (int j = 0; j < len; j++) {
// Create new string with next character
// Call generate again until string has
// reached its len
string appended = s + arr[j];
generate(arr, i - 1, appended, len);
}
return;
}
// function to generate all possible passwords
void crack(char* arr, int len)
{
// call for all required lengths
for (int i = 1; i <= len; i++) {
generate(arr, i, "", len);
}
}
// driver function
int main()
{
char arr[] = { 'a', 'b', 'c' };
int len = sizeof(arr) / sizeof(arr[0]);
crack(arr, len);
//cout << cnt << endl;
return 0;
}
// This code is contributed by Satish Srinivas.
Java
// Java program to generate all passwords for given characters
import java.util.*;
class GFG
{
// int cnt;
// Recursive helper function, adds/removes characters
// until len is reached
static void generate(char[] arr, int i, String s, int len)
{
// base case
if (i == 0) // when len has been reached
{
// print it out
System.out.println(s);
// cnt++;
return;
}
// iterate through the array
for (int j = 0; j < len; j++)
{
// Create new string with next character
// Call generate again until string has
// reached its len
String appended = s + arr[j];
generate(arr, i - 1, appended, len);
}
return;
}
// function to generate all possible passwords
static void crack(char[] arr, int len)
{
// call for all required lengths
for (int i = 1; i <= len; i++)
{
generate(arr, i, "", len);
}
}
// Driver code
public static void main(String[] args)
{
char arr[] = {'a', 'b', 'c'};
int len = arr.length;
crack(arr, len);
}
}
// This code has been contributed by 29AjayKumar
Python 3
# Python3 program to # generate all passwords # for given characters # Recursive helper function, # adds/removes characters # until len is reached def generate(arr, i, s, len): # base case if (i == 0): # when len has # been reached # print it out print(s) return # iterate through the array for j in range(0, len): # Create new string with # next character Call # generate again until # string has reached its len appended = s + arr[j] generate(arr, i - 1, appended, len) return # function to generate # all possible passwords def crack(arr, len): # call for all required lengths for i in range(1 , len + 1): generate(arr, i, "", len) # Driver Code arr = ['a', 'b', 'c' ] len = len(arr) crack(arr, len) # This code is contributed by Smita.
C#
// C# program to generate all passwords for given characters
using System;
class GFG
{
// int cnt;
// Recursive helper function, adds/removes characters
// until len is reached
static void generate(char[] arr, int i, String s, int len)
{
// base case
if (i == 0) // when len has been reached
{
// print it out
Console.WriteLine(s);
// cnt++;
return;
}
// iterate through the array
for (int j = 0; j < len; j++)
{
// Create new string with next character
// Call generate again until string has
// reached its len
String appended = s + arr[j];
generate(arr, i - 1, appended, len);
}
return;
}
// function to generate all possible passwords
static void crack(char[] arr, int len)
{
// call for all required lengths
for (int i = 1; i <= len; i++)
{
generate(arr, i, "", len);
}
}
// Driver code
public static void Main(String[] args)
{
char []arr = {'a', 'b', 'c'};
int len = arr.Length;
crack(arr, len);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to generate all passwords for given characters
// let cnt;
// Recursive helper function, adds/removes characters
// until len is reached
function generate(arr, i, s, len)
{
// base case
if (i == 0) // when len has been reached
{
// print it out
document.write(s + "<br/>");
// cnt++;
return;
}
// iterate through the array
for (let j = 0; j < len; j++)
{
// Create new string with next character
// Call generate again until string has
// reached its len
let appended = s + arr[j];
generate(arr, i - 1, appended, len);
}
return;
}
// function to generate all possible passwords
function crack(arr, len)
{
// call for all required lengths
for (let i = 1; i <= len; i++)
{
generate(arr, i, "", len);
}
}
// Driver Code
let arr = ['a', 'b', 'c'];
let len = arr.length;
crack(arr, len);
</script>
Producción:
a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc
Si queremos ver el recuento de palabras, podemos descomentar las líneas que tienen la variable cnt en el código. Podemos observar que resulta ser 
, donde n = len. Por lo tanto, la complejidad temporal del programa también es 
, por lo tanto, exponencial. También podemos verificar una contraseña en particular
mientras se genera y romper el ciclo y regresar si se encuentra. También podemos incluir otros símbolos para que se generen y, si es necesario, eliminar los duplicados al preprocesar la entrada usando una HashTable.
Este artículo es una contribución de Satish Srinivas . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.orgo envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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