Algoritmo de permutaciones sin repetición?

Question

En un programa que estoy haciendo que genera anagramas para un conjunto determinado de letras, mi enfoque actual es:

1. conseguir todas las combinaciones de todas las cartas
2. Recibe las variaciones de cada grupo de tratamiento combinado
3. Ordenar las permutaciones resultantes alfabéticamente
4. eliminar entradas duplicadas

Mi pregunta se refiere a las matemáticas de permutaciones. Me pregunto si es posible calcular a fondo el tamaño de la matriz necesaria para almacenar todas las entradas restantes después de la eliminación de las entradas duplicadas (utilizando, por ejemplo, el número de letras repetidas junto con la fórmula de permutación o algo así).

Me disculpo por la vaguedad de mi pregunta, todavía estoy investigando más sobre combinaciones y permutaciones. Trataré de elaborar mi objetivo a medida que mi comprensión de combinaciones y permutaciones se amplíe, y una vez que me vuelva a familiarizar con mi programa (fue un proyecto mío el tiempo libre el verano pasado).

Answer 1

Si tiene n elementos, y a[0] duplicados de un elemento, a[1] duplicados de otro elemento, y así sucesivamente hasta a[k], entonces el número total de permutaciones distintas (hasta duplicados) es n!/(a[0]! a[1]! ... a[k]!).

su información, si está interesado, con Guava podría escribir

Collection<List<Character>> uniquePermutations = 
    Collections2.orderedPermutations(Lists.charactersOf(string)); 

y el resultado sería el único permutaciones de los personajes, lo que representa duplicados y todo. Incluso puede llamar al método .size(), o simplemente mire su implementación para obtener sugerencias. (Divulgación: Contribuyo a Guava.)

Answer 2

La generación de todas las permutaciones es realmente mala idea. La palabra "desbordamiento" por ejemplo tiene 40320 permutaciones. Entonces, el consumo de memoria aumenta mucho a medida que aumenta la longitud de la palabra.

Creo que el problema que está tratando de resolver puede reducirse a averiguar si una palabra es un anagrama de otra.

Luego puede resolverlo contando cuántas veces se produce cada letra (será una tupla de 26) y comparar estos tupples entre sí.