Problema de algoritmo:combinaciones de letras

https://stackoverflow.com/questions/102468

01-07-2019
|

Pregunta

Estoy intentando escribir un fragmento de código que hará 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 fácil codificarlo.Obviamente conformará el código NLTD.Cuando se introduce un número como 5,6 u 8, las cosas se ponen diferentes.Un número como 051 daría lugar a más de una posibilidad:

NVL y NFL

Debería ser obvio que esto empeora aún más con números más largos que incluyen varios dígitos como 5,6 u 8.

Siendo bastante malo en matemáticas, todavía no he podido encontrar una solución decente que me permita alimentar al programa con un montón de números y hacer que escupe todas las combinaciones de letras posibles.Así que me encantaría recibir ayuda, porque parece que no puedo entenderlo.Desenterré información sobre permutaciones y combinaciones, pero no tuve suerte.

Gracias por cualquier sugerencia/pista.El lenguaje en el que necesito escribir el código es PHP, pero agradecería mucho cualquier sugerencia general.

Actualizar:

Algunos antecedentes más:(¡y muchas gracias por las rápidas respuestas!)

La idea detrás de mi pregunta es crear un script que ayude a las personas a convertir fácilmente los números que desean recordar en palabras que se recuerden mucho más fácilmente.Esto a veces se denomina "pseudonumerología".

Quiero que el script me proporcione todas las combinaciones posibles que luego se guardan en una base de datos de palabras eliminadas.Estas palabras eliminadas simplemente provienen de un diccionario y tienen todas las letras que mencioné en mi pregunta eliminadas.De esa manera, el número que se va a codificar generalmente se puede relacionar 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.

Solución

La estructura general que desea mantener en sus asignaciones de números -> 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 por la recursividad!Esto se utilizaría a través de:

PrintEncoding(GetEncoding("052384"));

Y si realmente lo desea como una matriz, juegue con el almacenamiento en búfer de salida y explote usando " " como cadena dividida.

Otros consejos

Se puede hacer fácilmente de forma recursiva.

La idea es que para manejar todo el código de tamaño n, primero debes manejar los n - 1 dígitos.Una vez que tenga todas las respuestas para n-1 dígitos, las respuestas para el total se deducen añadiéndoles los caracteres correctos para el último.

En realidad, existe una solución mucho mejor que enumerar todas las posibles traducciones de un número y buscarlas:Simplemente haga el cálculo inverso en cada palabra de su diccionario y almacene la cadena de dígitos en otro campo.Entonces, si tu 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 asignación para 'ch', porque la 'c' se eliminará y la 'h' se convertirá a 8 de todos modos.

Luego, todo lo que tiene que hacer es recorrer cada letra de la palabra del diccionario, generar el dígito apropiado si hay una coincidencia y no hacer nada si no la hay.

Almacene todas las cadenas de dígitos generadas como otro campo en la base de datos.Cuando desee buscar algo, simplemente realice una consulta simple para el número ingresado, en lugar de tener que realizar decenas (o cientos o miles) de búsquedas de palabras potenciales.

Este tipo de problemas suelen resolverse mediante 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 ejecutas esto desde la línea de comando obtendrás:

$ ruby r.rb 051
NVL
NFL

Esto está relacionado con búsqueda de fuerza bruta y retroceder

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

Salida de ejemplo:

$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']

¿Podrías hacer lo siguiente?Cree una matriz de resultados.Crea un elemento en la matriz con valor ""

Recorra los números, digamos 051, analizando cada uno individualmente.

Cada vez que se encuentre una coincidencia de 1 a 1 entre un número, agregue el valor correcto a todos los elementos de la matriz de resultados.Entonces "" se convierte en N.

Cada vez que se encuentre 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

Entonces 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 los resultados, recorra la matriz de resultados, imprímalos o lo que sea.

Dejar p_norte ser una lista de todas las combinaciones posibles de letras de una cadena numérica determinada 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 un caso algo especial, ya que p_-1 es indefinido.Simplemente puede inicializar p₀ como la lista de todos los caracteres posibles para el primer carácter.

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 formulario que desea probablemente sea algo 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 verifíquelo primero.La idea básica es generar cada combinación de la cadena desde [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 tanta ambigüedad está realmente presente en su esquema de codificación.

El truco no consiste sólo en generar todas las combinaciones posibles de letras que coincidan con un número determinado, sino también en seleccionar la secuencia de letras que sea más fácil de recordar.Una sugerencia sería ejecutar el sonidoex algoritmo en cada una de las secuencias e intentar compararlas con un diccionario del idioma inglés como red de palabras para encontrar las secuencias que suenen más "palabras reales".

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow