Generar lista de todas las posibles permutaciones de una cadena

StackOverflow https://stackoverflow.com/questions/361

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.

¿Fue ú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:

  1. 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.

  2. 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.

  3. 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;
}

fuente completa

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)]
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top