Generar lista de todas las posibles permutaciones de una cadena
-
08-06-2019 - |
Pregunta
¿Cómo haría para generar una lista de todas las permutaciones posibles de una cadena entre caracteres x e y de longitud, que contenga una lista variable de caracteres?
Cualquier idioma funcionaría, pero debería ser portátil.
Solución
Hay varias formas de hacer esto.Los métodos comunes utilizan recursividad, memorización o programación dinámica.La idea básica es producir una lista de todas las cadenas de longitud 1, luego, en cada iteración, para todas las cadenas producidas en la última iteración, agregar esa cadena concatenada con cada carácter de la cadena individualmente.(el índice de variable en el código siguiente realiza un seguimiento del inicio de la última y la siguiente iteración)
Algún pseudocódigo:
list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
index = (index[1], len(list))
for string s in list.subset(index[0] to end):
for character c in originalString:
list.add(s + c)
Luego deberá eliminar todas las cadenas de longitud inferior a x; serán las primeras entradas (x-1) * len(originalString) de la lista.
Otros consejos
Es mejor usar el retroceso
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void print(char *a, int i, int n) {
int j;
if(i == n) {
printf("%s\n", a);
} else {
for(j = i; j <= n; j++) {
swap(a + i, a + j);
print(a, i + 1, n);
swap(a + i, a + j);
}
}
}
int main(void) {
char a[100];
gets(a);
print(a, 0, strlen(a) - 1);
return 0;
}
Te van a salir muchos hilos, eso es seguro...
\sum_{i=x}^y{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D
Donde, x e y es cómo los defines y r es el número de caracteres que seleccionamos, si te entiendo correctamente.Definitivamente deberías generarlos según sea necesario y no descuidarte y decir, generar un conjunto de potencia y luego filtrar la longitud de las cadenas.
La siguiente definitivamente no es la mejor manera de generarlos, pero de todos modos es un comentario interesante.
Knuth (volumen 4, fascículo 2, 7.2.1.3) nos dice que la combinación (s,t) es equivalente a s+1 cosas tomadas t a la vez con repetición; una combinación (s,t) es la notación utilizada por Knuth que es igual a {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.Podemos resolver esto generando primero cada combinación (s,t) en forma binaria (es decir, de longitud (s+t)) y contando el número de ceros a la izquierda de cada 1.
10001000011101 --> se convierte en la permutación:{0, 3, 4, 4, 4, 1}
Solución no recursiva según Knuth, ejemplo de Python:
def nextPermutation(perm):
k0 = None
for i in range(len(perm)-1):
if perm[i]<perm[i+1]:
k0=i
if k0 == None:
return None
l0 = k0+1
for i in range(k0+1, len(perm)):
if perm[k0] < perm[i]:
l0 = i
perm[k0], perm[l0] = perm[l0], perm[k0]
perm[k0+1:] = reversed(perm[k0+1:])
return perm
perm=list("12345")
while perm:
print perm
perm = nextPermutation(perm)
Podrías mirar "Enumerar eficientemente los subconjuntos de un conjunto", que describe un algoritmo para hacer parte de lo que desea: generar rápidamente todos los subconjuntos de N caracteres desde la longitud x hasta la y.Contiene una implementación en C.
Para cada subconjunto, aún tendrías que generar todas las permutaciones.Por ejemplo, si quisieras 3 caracteres de "abcde", este algoritmo te daría "abc", "abd", "abe"...pero habría que permutar cada uno para obtener "acb", "bac", "bca", etc.
Algún código Java funcional basado en la respuesta de sarp:
public class permute {
static void permute(int level, String permuted,
boolean used[], String original) {
int length = original.length();
if (level == length) {
System.out.println(permuted);
} else {
for (int i = 0; i < length; i++) {
if (!used[i]) {
used[i] = true;
permute(level + 1, permuted + original.charAt(i),
used, original);
used[i] = false;
}
}
}
}
public static void main(String[] args) {
String s = "hello";
boolean used[] = {false, false, false, false, false};
permute(0, "", used, s);
}
}
Aquí hay una solución simple en C#.
Genera sólo las distintas permutaciones de una cadena determinada.
static public IEnumerable<string> permute(string word)
{
if (word.Length > 1)
{
char character = word[0];
foreach (string subPermute in permute(word.Substring(1)))
{
for (int index = 0; index <= subPermute.Length; index++)
{
string pre = subPermute.Substring(0, index);
string post = subPermute.Substring(index);
if (post.Contains(character))
continue;
yield return pre + character + post;
}
}
}
else
{
yield return word;
}
}
Hay muchas buenas respuestas aquí.También sugiero una solución recursiva muy simple en C++.
#include <string>
#include <iostream>
template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
if (start == s.length()) consume(s);
for (std::size_t i = start; i < s.length(); i++) {
std::swap(s[start], s[i]);
permutations(s, consume, start + 1);
}
}
int main(void) {
std::string s = "abcd";
permutations(s, [](std::string s) {
std::cout << s << std::endl;
});
}
Nota:Las cadenas con caracteres repetidos no producirán permutaciones únicas.
Simplemente preparé esto rápidamente en Ruby:
def perms(x, y, possible_characters)
all = [""]
current_array = all.clone
1.upto(y) { |iteration|
next_array = []
current_array.each { |string|
possible_characters.each { |c|
value = string + c
next_array.insert next_array.length, value
all.insert all.length, value
}
}
current_array = next_array
}
all.delete_if { |string| string.length < x }
end
Podrías buscar en la API del lenguaje funciones de tipo de permutación integradas y podrías escribir código más optimizado, pero si los números son tan altos, no estoy seguro de que haya muchas maneras de evitar obtener muchos resultados. .
De todos modos, la idea detrás del código es comenzar con una cadena de longitud 0 y luego realizar un seguimiento de todas las cadenas de longitud Z, donde Z es el tamaño actual en la iteración.Luego, revise cada cadena y agregue cada carácter a cada cadena.Finalmente, al final, elimine los que estén por debajo del umbral x y devuelva el resultado.
No lo probé con entradas potencialmente sin sentido (lista de caracteres nulos, valores extraños de xey, etc.).
Esta es una traducción de la versión Ruby de Mike, a Common Lisp:
(defun perms (x y original-string)
(loop with all = (list "")
with current-array = (list "")
for iteration from 1 to y
do (loop with next-array = nil
for string in current-array
do (loop for c across original-string
for value = (concatenate 'string string (string c))
do (push value next-array)
(push value all))
(setf current-array (reverse next-array)))
finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))
Y otra versión, un poco más corta y que utiliza más funciones de función de bucle:
(defun perms (x y original-string)
(loop repeat y
collect (loop for string in (or (car (last sets)) (list ""))
append (loop for c across original-string
collect (concatenate 'string string (string c)))) into sets
finally (return (loop for set in sets
append (loop for el in set when (>= (length el) x) collect el)))))
Aquí hay una solución recursiva simple de palabra C#:
Método:
public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
{
bool finished = true;
ArrayList newWords = new ArrayList();
if (words.Count == 0)
{
foreach (string letter in letters)
{
words.Add(letter);
}
}
for(int j=index; j<words.Count; j++)
{
string word = (string)words[j];
for(int i =0; i<letters.Length; i++)
{
if(!word.Contains(letters[i]))
{
finished = false;
string newWord = (string)word.Clone();
newWord += letters[i];
newWords.Add(newWord);
}
}
}
foreach (string newWord in newWords)
{
words.Add(newWord);
}
if(finished == false)
{
CalculateWordPermutations(letters, words, words.Count - newWords.Count);
}
return words;
}
Vocación:
string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
En Perl, si desea limitarse al alfabeto en minúsculas, puede hacer esto:
my @result = ("a" .. "zzzz");
Esto proporciona todas las cadenas posibles entre 1 y 4 caracteres utilizando caracteres en minúscula.Para mayúsculas, cambiar "a"
a "A"
y "zzzz"
a "ZZZZ"
.
Para casos mixtos se vuelve mucho más difícil, y probablemente no sea factible con uno de los operadores integrados de Perl como ese.
...y aquí está la versión C:
void permute(const char *s, char *out, int *used, int len, int lev)
{
if (len == lev) {
out[lev] = '\0';
puts(out);
return;
}
int i;
for (i = 0; i < len; ++i) {
if (! used[i])
continue;
used[i] = 1;
out[lev] = s[i];
permute(s, out, used, len, lev + 1);
used[i] = 0;
}
return;
}
permutar (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*Aantes de Cristo), (BAC), (antes de CristoA*), (*ACB), (CAB), (CBA*)] Para eliminar los duplicados al insertar cada verificación del alfabeto para ver si la cadena anterior termina con el mismo alfabeto (¿por qué?-ejercicio)
public static void main(String[] args) {
for (String str : permStr("ABBB")){
System.out.println(str);
}
}
static Vector<String> permStr(String str){
if (str.length() == 1){
Vector<String> ret = new Vector<String>();
ret.add(str);
return ret;
}
char start = str.charAt(0);
Vector<String> endStrs = permStr(str.substring(1));
Vector<String> newEndStrs = new Vector<String>();
for (String endStr : endStrs){
for (int j = 0; j <= endStr.length(); j++){
if (endStr.substring(0, j).endsWith(String.valueOf(start)))
break;
newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
}
}
return newEndStrs;
}
Imprime todas las permutaciones sin duplicados.
Respuesta de Ruby que funciona:
class String
def each_char_with_index
0.upto(size - 1) do |index|
yield(self[index..index], index)
end
end
def remove_char_at(index)
return self[1..-1] if index == 0
self[0..(index-1)] + self[(index+1)..-1]
end
end
def permute(str, prefix = '')
if str.size == 0
puts prefix
return
end
str.each_char_with_index do |char, index|
permute(str.remove_char_at(index), prefix + char)
end
end
# example
# permute("abc")
Solución recursiva en C++
int main (int argc, char * const argv[]) {
string s = "sarp";
bool used [4];
permute(0, "", used, s);
}
void permute(int level, string permuted, bool used [], string &original) {
int length = original.length();
if(level == length) { // permutation complete, display
cout << permuted << endl;
} else {
for(int i=0; i<length; i++) { // try to add an unused character
if(!used[i]) {
used[i] = true;
permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
used[i] = false;
}
}
}
La siguiente recursividad de Java imprime todas las permutaciones de una cadena determinada:
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() != 0){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
System.out.println(str1);
}
}
A continuación se muestra la versión actualizada del método "permut" anterior que hace que n!(n factorial) llamadas menos recursivas en comparación con el método anterior
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() > 1){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
System.out.println(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}
}
import java.util.*;
public class all_subsets {
public static void main(String[] args) {
String a = "abcd";
for(String s: all_perm(a)) {
System.out.println(s);
}
}
public static Set<String> concat(String c, Set<String> lst) {
HashSet<String> ret_set = new HashSet<String>();
for(String s: lst) {
ret_set.add(c+s);
}
return ret_set;
}
public static HashSet<String> all_perm(String a) {
HashSet<String> set = new HashSet<String>();
if(a.length() == 1) {
set.add(a);
} else {
for(int i=0; i<a.length(); i++) {
set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
}
}
return set;
}
}
Aquí hay una versión no recursiva que se me ocurrió, en javascript.No se basa en el no recursivo de Knuth anterior, aunque tiene algunas similitudes en el intercambio de elementos.He verificado su corrección para matrices de entrada de hasta 8 elementos.
Una optimización rápida sería realizar una prueba previa del out
matriz y evitando push()
.
La idea básica es:
Dada una única matriz de origen, genere un primer conjunto nuevo de matrices que intercambien el primer elemento con cada elemento posterior por turno, dejando cada vez los demás elementos imperturbables.p.ej:dado 1234, genera 1234, 2134, 3214, 4231.
Use cada matriz desde el pase anterior como semilla para un nuevo pase, pero en lugar de cambiar el primer elemento, cambie el segundo elemento con cada elemento posterior.Además, esta vez, no incluya la matriz original en la salida.
Repita el paso 2 hasta terminar.
Aquí está el ejemplo de código:
function oxe_perm(src, depth, index)
{
var perm = src.slice(); // duplicates src.
perm = perm.split("");
perm[depth] = src[index];
perm[index] = src[depth];
perm = perm.join("");
return perm;
}
function oxe_permutations(src)
{
out = new Array();
out.push(src);
for (depth = 0; depth < src.length; depth++) {
var numInPreviousPass = out.length;
for (var m = 0; m < numInPreviousPass; ++m) {
for (var n = depth + 1; n < src.length; ++n) {
out.push(oxe_perm(out[m], depth, n));
}
}
}
return out;
}
No estoy seguro de por qué querrías hacer esto en primer lugar.El conjunto resultante para cualquier valor moderadamente grande de x e y será enorme y crecerá exponencialmente a medida que x y/o y crezcan.
Digamos que su conjunto de caracteres posibles son las 26 letras minúsculas del alfabeto y le pide a su aplicación que genere todas las permutaciones donde longitud = 5.Suponiendo que no se quede sin memoria, obtendrá 11.881.376 (es decir,26 elevado a 5) cuerdas hacia atrás.Aumente esa longitud a 6 y recuperará 308,915,776 cuerdas.Estas cifras aumentan dolorosamente y muy rápidamente.
Aquí hay una solución que preparé en Java.Deberá proporcionar dos argumentos de tiempo de ejecución (correspondientes a xey).Divertirse.
public class GeneratePermutations {
public static void main(String[] args) {
int lower = Integer.parseInt(args[0]);
int upper = Integer.parseInt(args[1]);
if (upper < lower || upper == 0 || lower == 0) {
System.exit(0);
}
for (int length = lower; length <= upper; length++) {
generate(length, "");
}
}
private static void generate(int length, String partial) {
if (length <= 0) {
System.out.println(partial);
} else {
for (char c = 'a'; c <= 'z'; c++) {
generate(length - 1, partial + c);
}
}
}
}
Necesitaba esto hoy y, aunque las respuestas ya dadas me indicaron la dirección correcta, no eran exactamente lo que quería.
Aquí hay una implementación que utiliza el método de Heap.La longitud de la matriz debe ser de al menos 3 y, por consideraciones prácticas, no debe ser mayor de 10 aproximadamente, dependiendo de lo que quieras hacer, la paciencia y la velocidad del reloj.
Antes de ingresar a su bucle, inicialice Perm(1 To N)
con la primera permutación, Stack(3 To N)
con ceros*, y Level
con 2
**.Al final de la llamada del bucle NextPerm
, que devolverá falso cuando hayamos terminado.
* VB lo hará por usted.
** Puedes cambiar un poco NextPerm para que esto sea innecesario, pero queda más claro así.
Option Explicit
Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
Swap Perm(1), Perm(2)
Level = 3
Else
While Stack(Level) = Level - 1
Stack(Level) = 0
If Level = UBound(Stack) Then Exit Function
Level = Level + 1
Wend
Stack(Level) = Stack(Level) + 1
If Level And 1 Then N = 1 Else N = Stack(Level)
Swap Perm(N), Perm(Level)
Level = 2
End If
NextPerm = True
End Function
Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub
'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
If CurrentY + TextHeight("0") > ScaleHeight Then
ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
CurrentY = 0
CurrentX = 0
End If
T = vbNullString
For I = 1 To UBound(A)
Print A(I);
T = T & Hex(A(I))
Next
Print
Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
J = J * I
Next
If J <> Test.Count Then Stop
End Sub
Otros métodos son descritos por varios autores.Knuth describe dos, uno da orden léxico, pero es complejo y lento, el otro se conoce como método de cambios simples.Jie Gao y Dianjun Wang también escribieron un artículo interesante.
En rubí:
str = "a"
100_000_000.times {puts str.next!}
Es bastante rápido, pero llevará algo de tiempo =).Por supuesto, puedes empezar con "aaaaaaaa" si las cadenas cortas no te resultan interesantes.
Sin embargo, es posible que haya malinterpretado la pregunta real: en una de las publicaciones sonaba como si solo necesitaras una biblioteca de cadenas de fuerza bruta, pero en la pregunta principal parece que necesitas permutar una cadena en particular.
Tu problema es algo similar a este: http://beust.com/weblog/archives/000491.html (enumere todos los números enteros en los que ninguno de los dígitos se repite, lo que resultó en que muchos lenguajes lo resolvieran, con el tipo ocaml usando permutaciones y algún tipo java usando otra solución más).
Este código en Python, cuando se llama con allowed_characters
ajustado a [0,1]
y 4 caracteres como máximo, generaría 2^4 resultados:
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
def generate_permutations(chars = 4) :
#modify if in need!
allowed_chars = [
'0',
'1',
]
status = []
for tmp in range(chars) :
status.append(0)
last_char = len(allowed_chars)
rows = []
for x in xrange(last_char ** chars) :
rows.append("")
for y in range(chars - 1 , -1, -1) :
key = status[y]
rows[x] = allowed_chars[key] + rows[x]
for pos in range(chars - 1, -1, -1) :
if(status[pos] == last_char - 1) :
status[pos] = 0
else :
status[pos] += 1
break;
return rows
import sys
print generate_permutations()
Espero que esto te sea de utilidad.Funciona con cualquier carácter, no solo con números.
Aquí hay un enlace que describe cómo imprimir permutaciones de una cadena.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
Aunque esto no responde exactamente a su pregunta, aquí hay una forma de generar cada permutación de letras a partir de varias cadenas de la misma longitud:por ejemplo, si sus palabras fueran "café", "joomla" y "moodle", puede esperar resultados como "coodle", "joodee", "joffle", etc.
Básicamente, el número de combinaciones es (número de palabras) elevado a (número de letras por palabra).Entonces, elija un número aleatorio entre 0 y el número de combinaciones: 1, convierta ese número a base (número de palabras), luego use cada dígito de ese número como indicador de de qué palabra tomar la siguiente letra.
p.ej:en el ejemplo anterior.3 palabras, 6 letras = 729 combinaciones.Elige un número aleatorio:465.Convertir a base 3:122020.Tome la primera letra de la palabra 1, la segunda de la palabra 2, la tercera de la palabra 2, la cuarta de la palabra 0...y obtienes..."joofle".
Si desea todas las permutaciones, simplemente haga un bucle de 0 a 728.Por supuesto, si sólo eliges un valor aleatorio, mucho más simple Una forma menos confusa sería recorrer las letras.Este método te permite evitar la recursividad, en caso de que quieras todas las permutaciones, y además hace que parezca que sabes matemáticas.(tm)!
Si el número de combinaciones es excesivo, puedes dividirlo en una serie de palabras más pequeñas y concatenarlas al final.
c# iterativo:
public List<string> Permutations(char[] chars)
{
List<string> words = new List<string>();
words.Add(chars[0].ToString());
for (int i = 1; i < chars.Length; ++i)
{
int currLen = words.Count;
for (int j = 0; j < currLen; ++j)
{
var w = words[j];
for (int k = 0; k <= w.Length; ++k)
{
var nstr = w.Insert(k, chars[i].ToString());
if (k == 0)
words[j] = nstr;
else
words.Add(nstr);
}
}
}
return words;
}
Hay una implementación Java iterativa en Poco comunesMatemáticas (funciona para una lista de objetos):
/**
* Generate the indices into the elements array for the next permutation. The
* algorithm is from Kenneth H. Rosen, Discrete Mathematics and its
* Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284)
*/
private void generateNextPermutationIndices()
{
if (remainingPermutations == 0)
{
throw new IllegalStateException("There are no permutations " +
"remaining. Generator must be reset to continue using.");
}
else if (remainingPermutations < totalPermutations)
{
// Find largest index j with
// permutationIndices[j] < permutationIndices[j + 1]
int j = permutationIndices.length - 2;
while (permutationIndices[j] > permutationIndices[j + 1])
{
j--;
}
// Find index k such that permutationIndices[k] is smallest integer
// greater than permutationIndices[j] to the right
// of permutationIndices[j].
int k = permutationIndices.length - 1;
while (permutationIndices[j] > permutationIndices[k])
{
k--;
}
// Interchange permutation indices.
int temp = permutationIndices[k];
permutationIndices[k] = permutationIndices[j];
permutationIndices[j] = temp;
// Put tail end of permutation after jth position in increasing order.
int r = permutationIndices.length - 1;
int s = j + 1;
while (r > s)
{
temp = permutationIndices[s];
permutationIndices[s] = permutationIndices[r];
permutationIndices[r] = temp;
r--;
s++;
}
}
--remainingPermutations;
}
/**
* Generate the next permutation and return a list containing
* the elements in the appropriate order. This overloaded method
* allows the caller to provide a list that will be used and returned.
* The purpose of this is to improve performance when iterating over
* permutations. If the {@link #nextPermutationAsList()} method is
* used it will create a new list every time. When iterating over
* permutations this will result in lots of short-lived objects that
* have to be garbage collected. This method allows a single list
* instance to be reused in such circumstances.
* @param destination Provides a list to use to create the
* permutation. This is the list that will be returned, once
* it has been filled with the elements in the appropriate order.
* @return The next permutation as a list.
*/
public List<T> nextPermutationAsList(List<T> destination)
{
generateNextPermutationIndices();
// Generate actual permutation.
destination.clear();
for (int i : permutationIndices)
{
destination.add(elements[i]);
}
return destination;
}
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list
def func( x,i,j ): #returns x[i..j]
z = ''
for i in range(i,j+1):
z = z+x[i]
return z
def perm( x , length , list ): #perm function
if length == 1 : # base case
list.append( x[len(x)-1] )
return list
else:
lists = perm( x , length-1 ,list )
lists_temp = lists #temporarily storing the list
lists = []
for i in range( len(lists_temp) ) :
list_temp = gen(lists_temp[i],x[length-2],lists)
lists += list_temp
return lists
def permutation(str)
posibilities = []
str.split('').each do |char|
if posibilities.size == 0
posibilities[0] = char.downcase
posibilities[1] = char.upcase
else
posibilities_count = posibilities.length
posibilities = posibilities + posibilities
posibilities_count.times do |i|
posibilities[i] += char.downcase
posibilities[i+posibilities_count] += char.upcase
end
end
end
posibilities
end
Aquí está mi opinión sobre una versión no recursiva.
La solución pitónica:
from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]