algorithm - number - java permutations of array
Problema de Algoritmo: combinaciones de letras (9)
Intento escribir un fragmento de código que haga lo siguiente:
Tome los números del 0 al 9 y asigne una o más letras a este número. Por ejemplo:
0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G
Cuando tengo un código como 0123, es un trabajo fácil codificarlo. Obviamente formará el código NLTD. Cuando se introduce un número como 5,6 u 8, las cosas cambian. Un número como 051 daría lugar a más de una posibilidad:
NVL y NFL
Debería ser obvio que esto se pone incluso "peor" con números más largos que incluyen varios dígitos como 5,6 u 8.
Siendo muy malo con las matemáticas, todavía no he podido encontrar una solución decente que me permita alimentar el programa con un montón de números y escupir todas las posibles combinaciones de letras. Así que me gustaría algo de ayuda, porque parece que no puedo resolverlo. Descubierto algo de información sobre permutaciones y combinaciones, pero sin suerte.
Gracias por cualquier sugerencia / pista. El lenguaje en el que necesito escribir el código es PHP, pero cualquier sugerencia general sería muy apreciada.
Actualizar:
Algunos antecedentes más: (¡y muchas gracias por las respuestas rápidas!)
La idea detrás de mi pregunta es construir una secuencia de comandos que ayude a las personas a convertir fácilmente los números que desean recordar en palabras que son mucho más fáciles de recordar. Esto a veces se denomina "pseudo-numerología".
Quiero que la secuencia de comandos me dé todas las combinaciones posibles que luego se mantienen contra una base de datos de palabras despojadas. Estas palabras despojadas vienen de un diccionario y tienen todas las letras que mencioné en mi pregunta despojadas de ellas. De esta forma, el número que se va a codificar generalmente puede relacionarse fácilmente con uno o más registros de la base de datos. Y cuando eso sucede, terminas con una lista de palabras que puedes usar para recordar el número que querías recordar.
Aquí hay una solución recursiva en Python.
#!/usr/bin/env/python
import sys
ENCODING = {''0'':[''N''],
''1'':[''L''],
''2'':[''T''],
''3'':[''D''],
''4'':[''R''],
''5'':[''V'', ''F''],
''6'':[''B'', ''P''],
''7'':[''Z''],
''8'':[''H'', ''CH'', ''J''],
''9'':[''G'']
}
def decode(str):
if len(str) == 0:
return ''''
elif len(str) == 1:
return ENCODING[str]
else:
result = []
for prefix in ENCODING[str[0]]:
result.extend([prefix + suffix for suffix in decode(str[1:])])
return result
if __name__ == ''__main__'':
print decode(sys.argv[1])
Ejemplo de salida:
$ ./demo 1
[''L'']
$ ./demo 051
[''NVL'', ''NFL'']
$ ./demo 0518
[''NVLH'', ''NVLCH'', ''NVLJ'', ''NFLH'', ''NFLCH'', ''NFLJ'']
Deje p n ser una lista de todas las posibles combinaciones de letras de una cadena de números dada s hasta el n th dígito.
Entonces, el siguiente algoritmo generará p n+1 :
digit = s[n+1];
foreach(letter l that digit maps to)
{
foreach(entry e in p(n))
{
newEntry = append l to e;
add newEntry to p(n+1);
}
}
La primera iteración es algo así como un caso especial, ya que p -1 no está definido. Simplemente puede inicializar p 0 como la lista de todos los caracteres posibles para el primer personaje.
Entonces, tu ejemplo 051:
Iteración 0:
p(0) = {N}
Iteración 1:
digit = 5
foreach({V, F})
{
foreach(p(0) = {N})
{
newEntry = N + V or N + F
p(1) = {NV, NF}
}
}
Iteración 2:
digit = 1
foreach({L})
{
foreach(p(1) = {NV, NF})
{
newEntry = NV + L or NF + L
p(2) = {NVL, NFL}
}
}
El truco no es solo generar todas las posibles combinaciones de letras que coincidan con un número dado, sino seleccionar la secuencia de letras que sea más fácil de recordar. Una sugerencia sería ejecutar el algoritmo soundex en cada una de las secuencias e intentar hacer coincidir un diccionario de idioma inglés, como Wordnet, para encontrar las secuencias más "reales".
Este tipo de problema generalmente se resuelve con recursividad. En ruby, una solución (rápida y sucia) sería
@values = Hash.new([])
@values["0"] = ["N"]
@values["1"] = ["L"]
@values["2"] = ["T"]
@values["3"] = ["D"]
@values["4"] = ["R"]
@values["5"] = ["V","F"]
@values["6"] = ["B","P"]
@values["7"] = ["Z"]
@values["8"] = ["H","CH","J"]
@values["9"] = ["G"]
def find_valid_combinations(buffer,number)
first_char = number.shift
@values[first_char].each do |key|
if(number.length == 0) then
puts buffer + key
else
find_valid_combinations(buffer + key,number.dup)
end
end
end
find_valid_combinations("",ARGV[0].split(""))
Y si ejecuta esto desde la línea de comando, obtendrá:
$ ruby r.rb 051
NVL
NFL
Esto está relacionado con la búsqueda de fuerza bruta y retroceso
La estructura general en la que desea guardar su número -> asignaciones de letras es una matriz o matrices, similar a:
// 0 = N, 1 = L, 2 = T, 3 = D, 4 = R, 5 = V or F, 6 = B or P, 7 = Z,
// 8 = H or CH or J, 9 = G
$numberMap = new Array (
0 => new Array("N"),
1 => new Array("L"),
2 => new Array("T"),
3 => new Array("D"),
4 => new Array("R"),
5 => new Array("V", "F"),
6 => new Array("B", "P"),
7 => new Array("Z"),
8 => new Array("H", "CH", "J"),
9 => new Array("G"),
);
Entonces, un poco de lógica recursiva nos da una función similar a:
function GetEncoding($number) {
$ret = new Array();
for ($i = 0; $i < strlen($number); $i++) {
// We''re just translating here, nothing special.
// $var + 0 is a cheap way of forcing a variable to be numeric
$ret[] = $numberMap[$number[$i]+0];
}
}
function PrintEncoding($enc, $string = "") {
// If we''re at the end of the line, then print!
if (count($enc) === 0) {
print $string."/n";
return;
}
// Otherwise, soldier on through the possible values.
// Grab the next ''letter'' and cycle through the possibilities for it.
foreach ($enc[0] as $letter) {
// And call this function again with it!
PrintEncoding(array_slice($enc, 1), $string.$letter);
}
}
¡Tres hurras para la recursión! Esto se usaría a través de:
PrintEncoding(GetEncoding("052384"));
Y si realmente lo quiere como una matriz, juegue con buffering de salida y explote usando "/ n" como su cadena dividida.
La forma que desea es probablemente algo así como:
function combinations( $str ){
$l = len( $str );
$results = array( );
if ($l == 0) { return $results; }
if ($l == 1)
{
foreach( $codes[ $str[0] ] as $code )
{
$results[] = $code;
}
return $results;
}
$cur = $str[0];
$combs = combinations( substr( $str, 1, $l ) );
foreach ($codes[ $cur ] as $code)
{
foreach ($combs as $comb)
{
$results[] = $code.$comb;
}
}
return $results;}
Esto es feo, pidgin-php así que por favor verifícalo primero. La idea básica es generar cada combinación de la cadena de [1..n] y luego anteponer al frente de todas esas combinaciones cada código posible para str [0]. Tenga en cuenta que, en el peor de los casos, esto tendrá un rendimiento exponencial en la longitud de su cadena, porque esa gran ambigüedad está realmente presente en su esquema de codificación.
Podría hacer lo siguiente: Crear una matriz de resultados. Crea un elemento en la matriz con el valor ""
Pasa por los números, digamos 051, analizando cada uno individualmente.
Cada vez que se encuentra una coincidencia de 1 a 1 entre un número, agregue el valor correcto a todos los elementos en la matriz de resultados. Entonces "" se convierte en N.
Cada vez que se encuentra una coincidencia de 1 a muchos, agregue nuevas filas a la matriz de resultados con una opción y actualice los resultados existentes con la otra opción. Entonces N se convierte en NV y se crea un nuevo elemento NF
Luego, el último número es una coincidencia de 1 a 1, por lo que los elementos en la matriz de resultados se convierten en NVL y NFL.
Para producir el bucle de resultados a través de la matriz de resultados, imprimirlos, o lo que sea.
Se puede hacer fácilmente de forma recursiva.
La idea es que para manejar todo el código de tamaño n, primero debe manejar los n - 1 dígitos. Una vez que tenga todas las respuestas para n-1 dígitos, las respuestas para el todo se deducen al agregarles el (los) carácter (es) correcto (s) para el último.
En realidad, hay una solución mucho mejor que enumerar todas las traducciones posibles de un número y buscarlas: simplemente haga el cálculo inverso de cada palabra en su diccionario, y almacene la secuencia de dígitos en otro campo. Entonces, si su mapeo es:
0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G
su mapeo inverso es:
N = 0,
L = 1,
T = 2,
D = 3,
R = 4,
V = 5,
F = 5,
B = 6,
P = 6,
Z = 7,
H = 8,
J = 8,
G = 9
Tenga en cuenta que no hay mapeo para ''ch'', porque la ''c'' se eliminará y la ''h'' se convertirá a 8 de todos modos.
Entonces, todo lo que tiene que hacer es repetir cada letra en la palabra del diccionario, sacar el dígito apropiado si hay una coincidencia, y no hacer nada si no lo está.
Almacene todas las cadenas de dígitos generadas como otro campo en la base de datos. Cuando quiera buscar algo, simplemente realice una consulta simple para el número ingresado, en lugar de tener que hacer decenas (o cientos, o miles) de búsquedas de palabras potenciales.