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

Question

Encontrar todas las permutaciones de una cadena es por un conocido algoritmo Steinhaus-Johnson-Trotter. Pero si la cadena contiene los caracteres repetidos como
AABB,
continuación, las posibles combinaciones únicas habrá 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 manera más simple de modificar el algoritmo de Johnson, de modo que nunca generemos las permutaciones duplicadas? (De la manera más eficiente)

Answer 1

En mi solución, genero recursivamente las opciones, intento cada vez agregar todas las letras que no utilicé tantas veces como sea necesario.

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

utilización ejemplo:

#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; 
} 

Answer 2

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 se puede ver, es muy fácil

Answer 3

Creo que este problema es esencialmente el problema de generar permutaciones multiset. este trabajo parece ser relevante: J. F. Korsh P. S. LaFollette. Generación de matriz Loopless de permutaciones multiservicio. The Computer Journal, 47 (5): 612-621, 2004.

Del resumen: Este artículo presenta un algoritmo sin bucle para generar todas las permutaciones de un multiset. Cada uno se obtiene de su predecesor haciendo una transposición. Se diferencia de los algoritmos anteriores por usar una matriz para las permutaciones, pero requiere almacenamiento solo lineal en su longitud.

Answer 4

Primero convierta la cadena en un conjunto de caracteres únicos y números de aparición, p. BANANO -> (3, A), (1, B), (2, N). (Esto se puede hacer clasificando la cadena y agrupando letras). Luego, para cada letra del conjunto, anteceda esa letra a todas las permutaciones del conjunto con una letra menos de esa (tenga en cuenta la recursión). Continuando con el ejemplo "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í es una aplicación de trabajo 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)) 

Answer 5

Esta es una pregunta difícil y tenemos que utilizar la recursividad para encontrar todas las permutaciones de una cadena, por ejemplo "AAB" permutaciones serán "AAB", " ABA "y" BAA ". También necesitamos usar Establecer 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)); 
      } 
     } 

    } 

}