Encontrar todas las permutaciones únicas de una cadena sin generar duplicados

5 minutos de lectura

avatar de usuario
titán

Encontrar todas las permutaciones de una cadena se realiza mediante un conocido algoritmo de Steinhaus-Johnson-Trotter. Pero si la cadena contiene los caracteres repetidos como
aabb,
entonces las posibles combinaciones únicas serán 4!/(2! * 2!) = 6

Una forma de lograr esto es que podemos almacenarlo en una matriz más o menos y luego eliminar los duplicados.

¿Hay alguna forma más sencilla de modificar el algoritmo de Johnson, para que nunca generemos las permutaciones duplicadas? (De la manera más eficiente)

  • ¿Cuál es la definición de permutación? ¿Es BA una permutación válida de AABB?

    – ElKamina

    9 de febrero de 2012 a las 20:06

  • no BA no es una permutación válida de AABB.

    – titán

    9 de febrero de 2012 a las 20:07

  • La permutación es la única secuencia de barajar los caracteres en la cadena. Para una cadena de longitud n y caracteres únicos, ¡tenemos un total de n! posibles permutaciones únicas

    – titán

    9 de febrero de 2012 a las 20:08

  • Puede modificar el algoritmo de Jhonson, poniendo cada aparición de cada letra en un solo paso.

    – asaelr

    9 de febrero de 2012 a las 20:24

  • Si no puede encontrar una manera de evitar la generación de duplicados, puede beneficiarse de eliminar los duplicados a medida que los genera almacenando las permutaciones en un BST autoequilibrado o una estructura ordenada similar.

    –Brian McFarland

    9 de febrero de 2012 a las 20:39

Primero convierta la cadena a un conjunto de caracteres únicos y números de ocurrencia, por ejemplo, BANANA -> (3, A), (1, B), (2, N). (Esto podría hacerse ordenando la cadena y agrupando las letras). Luego, para cada letra del conjunto, anteponga esa letra a todas las permutaciones del conjunto con una letra menos de esa letra (observe la recursividad). Continuando con el ejemplo de “BANANA”, tenemos: permutaciones((3,A),(1,B),(2,N)) = A:(permutaciones((2,A),(1,B),(2 ,N)) ++ B:(permutaciones((3,A),(2,N)) ++ N:(permutaciones((3,A),(1,B),(1,N))

Aquí hay una implementación funcional en Haskell:

circularPermutations::[a]->[[a]]
circularPermutations xs = helper [] xs []
                          where helper acc [] _ = acc
                                helper acc (x:xs) ys =
                                  helper (((x:xs) ++ ys):acc) xs (ys ++ [x])

nrPermutations::[(Int, a)]->[[a]]
nrPermutations x | length x == 1 = [take (fst (head x)) (repeat (snd (head x)))]
nrPermutations xs = concat (map helper (circularPermutations xs))
  where helper ((1,x):xs) = map ((:) x)(nrPermutations xs)
        helper ((n,x):xs) = map ((:) x)(nrPermutations ((n - 1, x):xs))

avatar de usuario
Gangnus

Utilice el siguiente algoritmo recursivo:

PermutList Permute(SymArray fullSymArray){
    PermutList resultList=empty;
    for( each symbol A in fullSymArray, but repeated ones take only once) {
       PermutList lesserPermutList=  Permute(fullSymArray without A)
       for ( each SymArray item in lesserPermutList){
            resultList.add("A"+item);
       }
    }
    return resultList;
}

Como ves es muy fácil

Creo que este problema es esencialmente el problema de generar permutaciones multiconjunto. este documento parece ser relevante: JF Korsh PS LaFollette. Generación de matriz sin bucles de permutaciones de conjuntos múltiples. The Computer Journal, 47(5):612–621, 2004.

Del resumen: este artículo presenta un algoritmo sin bucles para generar todas las permutaciones de un conjunto múltiple. Cada uno se obtiene de su predecesor haciendo una transposición. Se diferencia de los algoritmos anteriores en el uso de una matriz para las permutaciones, pero requiere almacenamiento solo lineal en su longitud.

  • ¿Y qué tal si intentas escribirlo tú mismo?

    – Gangnus

    9 de febrero de 2012 a las 21:57

avatar de usuario
asaelr

En mi solución, genero recursivamente las opciones, trato cada vez de agregar cada letra que no usé tantas veces como necesito todavía.

#include <string.h>

void fill(char ***adr,int *pos,char *pref) {
    int i,z=1;
    //loop on the chars, and check if should use them
    for (i=0;i<256;i++)
        if (pos[i]) {
            int l=strlen(pref);
            //add the char
            pref[l]=i;
            pos[i]--;
            //call the recursion
            fill(adr,pos,pref);
            //delete the char
            pref[l]=0;
            pos[i]++;
            z=0;
        }
    if (z) strcpy(*(*adr)++,pref);
}

void calc(char **arr,const char *str) {
    int p[256]={0};
    int l=strlen(str);
    char temp[l+1];
    for (;l>=0;l--) temp[l]=0;
    while (*str) p[*str++]++;
    fill(&arr,p,temp);
}

ejemplo de uso:

#include <stdio.h>
#include <string.h>

int main() {
    char s[]="AABAF";
    char *arr[20];
    int i;
    for (i=0;i<20;i++) arr[i]=malloc(sizeof(s));
    calc(arr,s);
    for (i=0;i<20;i++) printf("%d: %s\n",i,arr[i]);
    return 0;
}

Esta es una pregunta complicada y necesitamos usar la recursividad para encontrar todas las permutaciones de una Cadena, por ejemplo, las permutaciones “AAB” serán “AAB”, “ABA” y “BAA”. También necesitamos usar Colocar para asegurarse de que no haya valores duplicados.

import java.io.*;
import java.util.HashSet;
import java.util.*;
class Permutation {

    static HashSet<String> set = new HashSet<String>();
    public static void main (String[] args) {
    Scanner in = new Scanner(System.in);
        System.out.println("Enter :");
        StringBuilder  str = new StringBuilder(in.nextLine());
        NONDuplicatePermutation("",str.toString());  //WITHOUT DUPLICATE PERMUTATION OF STRING
        System.out.println(set);
    }


    public static void NONDuplicatePermutation(String prefix,String str){
        //It is nlogn
        if(str.length()==0){
            set.add(prefix);
        }else{
            for(int i=0;i<str.length();i++){

                NONDuplicatePermutation(prefix+ str.charAt(i), str.substring(0,i)+str.substring(i+1));
            }
        }

    }

}

  • Escribí mi código en java. Creo que la lógica dada en mi código se entiende bastante.

    – mukta

    12 de julio de 2017 a las 9:37

  • Todavía está generando todas las permutaciones (incluidos los duplicados). La pregunta menciona que la solución debe evitar hacer eso.

    – Un insecto enigmático

    24 de agosto de 2020 a las 15:08

  • Escribí mi código en java. Creo que la lógica dada en mi código se entiende bastante.

    – mukta

    12 de julio de 2017 a las 9:37

  • Todavía está generando todas las permutaciones (incluidos los duplicados). La pregunta menciona que la solución debe evitar hacer eso.

    – Un insecto enigmático

    24 de agosto de 2020 a las 15:08

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad