Generar una lista de todas las permutaciones posibles de una cadena

votos
143

¿Cómo podría generar una lista de todas las permutaciones posibles de una cadena entre caracteres xey de largo, que contiene una lista variable de caracteres?

Cualquier idioma funcionaría, pero debería ser portátil.

Publicado el 02/08/2008 a las 07:57
fuente por usuario
En otros idiomas...                            


35 respuestas

votos
67

Hay varias formas de hacer esto. Los métodos comunes usan recursividad, memorización o programación dinámica. La idea básica es que usted produzca una lista de todas las cadenas de longitud 1, luego en cada iteración, para todas las cadenas producidas en la última iteración, agregue esa cadena concatenada con cada carácter en 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)

Algunos 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)

entonces necesitarás eliminar todas las cadenas de menos de x de longitud, serán las primeras (x-1) * len (originalString) entradas en la lista.

Respondida el 02/08/2008 a las 08:48
fuente por usuario

votos
35

Es mejor utilizar 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;
}
Respondida el 10/01/2012 a las 19:00
fuente por usuario

votos
24

Vas a obtener un montón de cuerdas, eso es seguro ...

\ sum_ {i = x} ^ y {\ frac {r!} {{(ri)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7B% 20% 5Cfrac% 7Br!% 7D% 7B% 7B (ri)% 7D!% 7D% 20% 7D
Donde, xey es cómo los defines yr es el número de caracteres que estamos seleccionando - -si te estoy entendiendo correctamente Definitivamente deberías generarlos según sea necesario y no descuidarse y decir, generar un powerset y luego filtrar la longitud de las cadenas.

Definitivamente, la siguiente no es la mejor manera de generar estos, pero es un lado interesante, no obstante.

Knuth (volumen 4, fascículo 2, 7.2.1.3) nos dice que (s, t) -combinación es equivalente a s + 1 cosas tomadas t a la vez con repetición - una (s, t) -combinación es la notación utilizada por Knuth 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 (s, t) -combinación en forma binaria (por lo tanto, de longitud (s + t)) y contando el número de 0 a la izquierda de cada uno.

10001000011101 -> se convierte en la permutación: {0, 3, 4, 4, 4, 1}

Respondida el 05/08/2008 a las 05:57
fuente por usuario

votos
14

solución no recursivo según el ejemplo Knuth, 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)
Respondida el 09/11/2010 a las 14:58
fuente por usuario

votos
12

Hay un montón de buenas respuestas aquí. También se sugiere 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.

Respondida el 08/01/2014 a las 12:00
fuente por usuario

votos
12

Aquí es una solución simple en C #.

Genera sólo las permutaciones distintas de una cadena dada.

    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;
        }
    }
Respondida el 05/07/2010 a las 10:06
fuente por usuario

votos
12

Algunos código Java de trabajo 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);
    }
}
Respondida el 04/04/2010 a las 19:18
fuente por usuario

votos
12

Puede consultar " Enumeración eficiente de 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 de la longitud xa y. Contiene una implementación en C.

Para cada subconjunto, igual deberías generar todas las permutaciones. Por ejemplo, si quisieras 3 caracteres de "abcde", este algoritmo te daría "abc", "abd", "abe" ... pero tendrías que permutar cada uno para obtener "acb", "bac", "bca", etc.

Respondida el 14/11/2008 a las 20:36
fuente por usuario

votos
8

Acabo de azotar esto rápido 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

Puede buscar API de idioma para las funciones de tipo de permutación incorporadas, y puede escribir código más optimizado, pero si los números son tan altos, no estoy seguro de que haya mucho camino para tener muchos resultados .

De todos modos, la idea detrás del código es comenzar con una cadena de longitud 0, luego realizar un seguimiento de todas las cadenas de longitud Z, donde Z es el tamaño actual en la iteración. Luego, revisa cada cadena y agrega cada carácter a cada cuerda. Finalmente, al final, elimine cualquiera que esté por debajo del umbral xy devuelva el resultado.

No lo probé con una entrada potencialmente sin sentido (lista de caracteres nulos, valores raros de xey, etc.).

Respondida el 02/08/2008 a las 08:56
fuente por usuario

votos
7

respuesta 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")
Respondida el 20/04/2012 a las 01:21
fuente por usuario

votos
7

permute (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [( * B C), (C B * )] -> [( * A BC ), (B a C), (BC a * ), ( * a CB), (C a B), (CB a * )] para eliminar duplicados al insertar cada cheque alfabeto para ver si la cadena anterior termina con el mismo alfabeto (¿por qué? -El 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 sans duplicados

Respondida el 22/02/2011 a las 19:45
fuente por usuario

votos
7

... 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;
}
Respondida el 07/02/2011 a las 22:56
fuente por usuario

votos
7

En Perl, si quiere restringirse al alfabeto en minúscula, puede hacer esto:

my @result = ("a" .. "zzzz");

Esto da todas las cadenas posibles entre 1 y 4 caracteres usando caracteres en minúsculas. Para mayúsculas, cambie "a"a "A"y "zzzz"a "ZZZZ".

Para el caso mixto se vuelve mucho más difícil, y probablemente no factible con uno de los operadores integrados de Perl como ese.

Respondida el 15/02/2009 a las 11:02
fuente por usuario

votos
7

Aquí hay una palabra simple C # solución recursiva:

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);
Respondida el 20/10/2008 a las 01:17
fuente por usuario

votos
7

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;
            }
        }
}
Respondida el 29/09/2008 a las 02:34
fuente por usuario

votos
7

Esta es una traducción de la versión de Ruby de Mike, en 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 usa más características de instalació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)))))
Respondida el 16/09/2008 a las 06:15
fuente por usuario

votos
6

Las siguientes impresiones de recursividad Java todas las permutaciones de una cadena dada:

//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);
    }
}

Lo que sigue es la versión actualizada del método anterior "PERMUTACIONES" 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()));
   }
}
Respondida el 19/06/2013 a las 05:23
fuente por usuario

votos
5

Aquí hay una versión no recursiva que se me ocurrió, en javascript. No se basa en un no-recursivo de Knuth anterior, aunque tiene algunas similitudes en el elemento de intercambio. He verificado su corrección para las matrices de entrada de hasta 8 elementos.

Una optimización rápida sería la verificación previa de la outmatriz y evitando push().

La idea básica es:

  1. Dada una única matriz de origen, generar una primera nuevo conjunto de matrices que intercambian el primer elemento con cada elemento posterior a su vez, cada vez dejando a los otros elementos no perturbado. por ejemplo: dada 1234, generan 1.234, 2.134, 3.214, 4.231.

  2. Use cada matriz a partir de la pasada anterior como la semilla de un nuevo pase, pero en vez de intercambiar el primer elemento, intercambiar el segundo elemento con cada elemento posterior. También, en esta ocasión, no incluyen la matriz original en la salida.

  3. Repita el paso 2 hasta que esté hecho.

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;
}
Respondida el 03/08/2011 a las 08:11
fuente por usuario

votos
5
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;
    }
}
Respondida el 24/10/2010 a las 23:01
fuente por usuario

votos
4

No estoy seguro de por qué querrías hacer esto en primer lugar. El conjunto resultante para cualquier valor moderadamente grande de xey será enorme, y crecerá exponencialmente a medida que x y / o sean más grandes.

Digamos que tu conjunto de caracteres posibles son las 26 letras minúsculas del alfabeto, y pides a tu aplicación que genere todas las permutaciones donde length = 5. Suponiendo que no te quedes sin memoria obtendrás 11,881,376 (es decir, 26 a la potencia de 5) cuerdas atrás. Mejora esa longitud hasta 6, y obtendrás 308,915,776 cuerdas. Estos números se vuelven dolorosamente grandes, muy rápidamente.

Aquí hay una solución que armé en Java. Deberá proporcionar dos argumentos de tiempo de ejecución (correspondientes a xey). Que te diviertas.

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);
            }
        }
    }
}
Respondida el 02/08/2008 a las 10:40
fuente por usuario

votos
3

Necesitaba esto hoy, y aunque las respuestas ya dadas me señaló en la dirección correcta, no eran exactamente lo que quería.

He aquí una aplicación utilizando el método de Montón. La longitud de la matriz debe ser de al menos 3 y por consideraciones prácticas, no sea mayor que 10 más o menos, dependiendo de lo que quiere hacer, la paciencia y la velocidad de reloj.

Antes de entrar en el bucle, inicializar Perm(1 To N)con la primera permutación, Stack(3 To N)con ceros *, y Levelcon 2**. Al final de la llamada bucle NextPerm, que devolverá falso cuando hayamos terminado.

* VB lo hará por ti.

** Se puede cambiar NextPerm un poco para hacer esto innecesario, pero es más claro de esta manera.

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 se describen por varios autores. Knuth describe dos, uno da orden léxico, pero es complejo y lento, el otro es conocido como el método de los cambios de fricción. Jie Gao y Dianjun Wang también escribió un interesante artículo.

Respondida el 02/10/2011 a las 10:13
fuente por usuario

votos
2

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

Respondida el 13/02/2014 a las 22:08
fuente por usuario

votos
2

Este código en Python, cuando se le llama con allowed_charactersconjunto a [0,1]y 4 caracteres 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 sea de utilidad para usted. Funciona con cualquier carácter, no sólo números

Respondida el 26/05/2011 a las 15:22
fuente por usuario

votos
2

En ruby:

str = "a"
100_000_000.times {puts str.next!}

Es bastante rápido, pero tomará un tiempo =). Por supuesto, puedes comenzar en "aaaaaaaa" si las cuerdas cortas no te interesan.

Sin embargo, podría haber malinterpretado la pregunta real: en una de las publicaciones sonaba como si solo necesitaras una biblioteca de cuerdas de fuerza bruta, pero en la pregunta principal parece que necesitas permutar una cuerda en particular.

Su problema es similar a este: http://beust.com/weblog/archives/000491.html (enumere todos los enteros en los que ninguno de los dígitos se repite, lo que dio lugar a que un montón de idiomas lo resolvieran, con el chico ocaml usando permutaciones, y algún chico java usando otra solución).

Respondida el 15/09/2008 a las 18:32
fuente por usuario

votos
0

Los posibles permutaciones de cadenas se pueden calcular usando la función recursiva. A continuación se muestra una de las soluciones posibles.

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList<String> getPerm(String s, int index) {
        ArrayList<String> perm = new ArrayList<String>();

        if (index == s.length()-1) {
            perm.add(String.valueOf(s.charAt(index)));
            return perm;
        }

        ArrayList<String> p = getPerm(s, index+1);
        char c = s.charAt(index);

        for(String pp : p) {
            for (int idx=0; idx<pp.length()+1; idx++) {
                String ss = insertCharAt(pp, idx, c);
                perm.add(ss);
            }
        }

        return perm;    
}

public static void testGetPerm(String s) {
        ArrayList<String> perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}
Respondida el 06/02/2017 a las 03:00
fuente por usuario

votos
0

código escrito para el lenguaje Java:

namo.algorithms paquete;

java.util.Scanner importación;

Permuations clase pública {

public static int totalPermutationsCount = 0;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("input string : ");
        String inputString = sc.nextLine();
        System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
        findPermuationsOfString(-1, inputString);
        System.out.println("**************************************");
        System.out.println("total permutation strings ==> "+totalPermutationsCount);
    }


    public  static void findPermuationsOfString(int fixedIndex, String inputString) {
        int currentIndex = fixedIndex +1;

        for (int i = currentIndex; i < inputString.length(); i++) {
            //swap elements and call the findPermuationsOfString()

            char[] carr = inputString.toCharArray();
            char tmp = carr[currentIndex];
            carr[currentIndex] = carr[i];
            carr[i] = tmp;
            inputString =  new String(carr);

            //System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
            if(currentIndex == inputString.length()-1) {
                totalPermutationsCount++;
                System.out.println("permuation string ==> "+inputString);
            } else {
                //System.out.println("in else block>>>>");
                findPermuationsOfString(currentIndex, inputString);
                 char[] rarr = inputString.toCharArray();
                    char rtmp = carr[i];
                    carr[i] = carr[currentIndex];
                    carr[currentIndex] = rtmp;
                    inputString =  new String(carr);
            }
        }
    }

}

Respondida el 05/06/2016 a las 05:42
fuente por usuario

votos
0

Bueno, aquí es un elegante, no recursivo, O (n!) Solución:

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }
Respondida el 27/06/2015 a las 08:44
fuente por usuario

votos
0

La solución Pythonic:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Respondida el 13/07/2014 a las 08:51
fuente por usuario

votos
0
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

Respondida el 23/01/2014 a las 04:28
fuente por usuario

votos
0

Solución recursiva con conductor main()método.

public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
    if(remaining.length()==0)
        System.out.println(newstring);

    for(int i=0; i<remaining.length(); i++) {
        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
        stringPermutations(newstring+remaining.charAt(i), newRemaining);
    }
}

public static void main(String[] args) {
    String string = "abc";
    AllPermutationsOfString.stringPermutations("", string); 
}

}

Respondida el 19/10/2013 a las 02:34
fuente por usuario

votos
0
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
Respondida el 22/08/2013 a las 18:51
fuente por usuario

votos
0

Una solución recursiva en Python. Lo bueno de este código es que se exporta un diccionario, con claves como cadenas y todas las permutaciones posibles como valores. Todas las posibles longitudes de cadena se incluyen, lo que en efecto, se está creando un superconjunto.

Si sólo necesita las permutaciones finales, puede eliminar otras claves del diccionario.

En este código, el diccionario de permutaciones es global.

En el caso base, almaceno el valor ya que ambas posibilidades en una lista. perms['ab'] = ['ab','ba'].

Para longitudes de cadena mayores, la función se refiere a disminuir longitudes de cadena e incorpora las permutaciones previamente calculados.

La función hace dos cosas:

  • llama a sí misma con una cadena más pequeña
  • devuelve una lista de permutaciones de una cadena en particular si ya se conocen. Si es devuelto a sí mismo, estos serán utilizados para anexar el carácter y crear nuevas permutaciones.

Caro para la memoria.

perms = {}
def perm(input_string):
    global perms
    if input_string in perms:
        return perms[input_string] # This will send a list of all permutations
    elif len(input_string) == 2:
        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
        return perms[input_string]
    else:
        perms[input_string] = []
        for index in range(0, len(input_string)):
            new_string = input_string[0:index] + input_string[index +1:]
            perm(new_string)
            for entries in perms[new_string]:
                perms[input_string].append(input_string[index] + entries)
    return perms[input_string]
Respondida el 05/07/2013 a las 05:15
fuente por usuario

votos
0

Hay una aplicación Java iterativo en el UncommonsMaths (que 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 completo

Respondida el 07/05/2013 a las 02:18
fuente por usuario

votos
0

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;
    }
Respondida el 26/07/2012 a las 16:20
fuente por usuario

votos
0

Aunque esto no responde exactamente a su pregunta, aquí hay una forma de generar cada permutación de las letras de un número de cadenas de la misma longitud: por ejemplo, si sus palabras fueron "café", "joomla" y "moodle", puede esperar salidas como "coodle", "joodee", "joffle", etc.

Básicamente, el número de combinaciones es el (número de palabras) a la potencia de (número de letras por palabra). Por lo tanto, 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 el indicador de la palabra de la que tomará la siguiente letra.

por ejemplo: en el ejemplo anterior. 3 palabras, 6 letras = 729 combinaciones. Elige un número aleatorio: 465. Convierte a base 3: 122020. Toma la primera letra de la palabra 1, la segunda de la palabra 2, la tercera de la palabra 2, la 4 de la palabra 0 ... y obtienes ... "joofle".

Si querías todas las permutaciones, simplemente haz un bucle de 0 a 728. Por supuesto, si solo eliges un valor aleatorio, una forma mucho más simple y menos confusa sería recorrer las letras. Este método te permite evitar la recursión, si quieres todas las permutaciones, además te hace ver como si conocieras Maths (tm) .

Si el número de combinaciones es excesivo, puede dividirlo en una serie de palabras más pequeñas y concatenarlas al final.

Respondida el 16/09/2008 a las 06:33
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more