Problema dell'algoritmo: combinazioni di lettere

https://stackoverflow.com/questions/102468

01-07-2019
|

Domanda

Sto cercando di scrivere un pezzo di codice che farà quanto segue:

Prendi i numeri da 0 a 9 e assegna una o più lettere a questo numero. Ad esempio:

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

Quando ho un codice come 0123, è un lavoro facile codificarlo. Ovviamente costituirà il codice NLTD. Quando viene introdotto un numero come 5,6 o 8, le cose diventano diverse. Un numero come 051 comporterebbe più di una possibilità:

NVL e NFL

Dovrebbe essere ovvio che ciò peggiora "peggio". con numeri più lunghi che includono più cifre come 5,6 o 8.

Essendo piuttosto cattivo in matematica, non sono ancora stato in grado di trovare una soluzione decente che mi permetta di alimentare il programma un mucchio di numeri e sputare tutte le possibili combinazioni di lettere. Quindi mi piacerebbe un po 'di aiuto, perché non riesco a capirlo. Hai raccolto alcune informazioni su permutazioni e combinazioni, ma senza fortuna.

Grazie per eventuali suggerimenti / indizi. La lingua di cui ho bisogno per scrivere il codice è PHP, ma ogni suggerimento generale sarebbe molto apprezzato.

Aggiornamento:

Qualche altra informazione: (e grazie mille per le risposte rapide!)

L'idea alla base della mia domanda è quella di costruire uno script che aiuti le persone a convertire facilmente i numeri che vogliono ricordare in parole che sono molto più facilmente ricordabili. Questo viene talvolta definito "pseudo-numerologia".

Voglio che lo script mi ??dia tutte le possibili combinazioni che vengono poi archiviate in un database di parole spogliate. Queste parole spogliate provengono da un dizionario e tutte le lettere che ho citato nella mia domanda sono state eliminate. In questo modo, il numero da codificare può essere facilmente correlato a uno o più record del database. E quando ciò accade, si finisce con un elenco di parole che è possibile utilizzare per ricordare il numero che si desidera ricordare.

Soluzione

La struttura generale che vuoi contenere il tuo numero - > l'assegnazione delle lettere è un array o array, simile 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"),
);

Quindi, un po 'di logica ricorsiva ci dà una funzione simile 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);
    }
}

Tre saluti per la ricorsione! Questo verrebbe utilizzato tramite:

PrintEncoding(GetEncoding("052384"));

E se lo vuoi davvero come un array, gioca con il buffering dell'output ed esplodi usando " \ n " come stringa divisa.

Altri suggerimenti

Può essere fatto facilmente in modo ricorsivo.

L'idea è che per gestire l'intero codice di dimensione n, devi prima gestire le cifre n - 1. Una volta che hai tutte le risposte per n-1 cifre, le risposte per l'intero sono dedotte aggiungendo loro i caratteri corretti per l'ultimo.

In realtà esiste una soluzione molto migliore rispetto all'enumerazione di tutte le possibili traduzioni di un numero e alla loro ricerca: basta eseguire il calcolo inverso su ogni parola del dizionario e memorizzare la stringa di cifre in un altro campo. Quindi se la tua mappatura è:

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

la tua mappatura inversa è:

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

Nota che non esiste alcuna mappatura per 'ch', perché la 'c' verrà eliminata e la 'h' verrà comunque convertita in 8.

Quindi, tutto ciò che devi fare è scorrere ogni lettera della parola del dizionario, generare la cifra appropriata in caso di corrispondenza e non fare nulla in caso contrario.

Memorizza tutte le stringhe di cifre generate come un altro campo nel database. Quando vuoi cercare qualcosa, esegui una semplice query per il numero inserito, invece di dover fare decine (o centinaia o migliaia) di ricerche di parole potenziali.

Questo tipo di problema viene generalmente risolto con la ricorsione. In ruby, una soluzione (veloce e sporca) sarebbe

@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(""))

E se lo esegui dalla riga di comando otterrai:

$ ruby r.rb 051
NVL
NFL

Questo è correlato a ricerca di forza bruta e backtracking

Ecco una soluzione ricorsiva in 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])

Esempio di output:

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

Potresti fare quanto segue: Crea un array di risultati. Crea un elemento nella matrice con valore " "

Scorri i numeri, diciamo 051 analizzandoli singolarmente.

Ogni volta che viene trovata una corrispondenza 1 a 1 tra un numero, aggiungere il valore corretto a tutti gli elementi nella matrice dei risultati. Quindi " " diventa N.

Ogni volta che viene trovata una corrispondenza da 1 a molte, aggiungi nuove righe all'array dei risultati con un'opzione e aggiorna i risultati esistenti con l'altra opzione. Quindi N diventa NV e viene creato un nuovo elemento NF

Quindi l'ultimo numero è una corrispondenza da 1 a 1 in modo che gli elementi nella matrice dei risultati diventino NVL e NFL

Per produrre il ciclo dei risultati attraverso l'array dei risultati, stampandoli o altro.

Sia p_n un elenco di tutte le possibili combinazioni di lettere di una determinata stringa di numeri s fino a n ^th digit.

Quindi, il seguente algoritmo genererà 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 prima iterazione è in qualche modo un caso speciale, poiché p _-1 non è definito. Puoi semplicemente inizializzare p ₀ come elenco di tutti i possibili caratteri per il primo carattere.

Quindi, il tuo esempio 051:

Iterazione 0:

p(0) = {N}

Iterazione 1:

digit = 5
foreach({V, F})
{
    foreach(p(0) = {N})
    {
        newEntry = N + V  or  N + F
        p(1) = {NV, NF}
    }
}

Iterazione 2:

digit = 1
foreach({L})
{
    foreach(p(1) = {NV, NF})
    {
        newEntry = NV + L  or  NF + L
        p(2) = {NVL, NFL}
    }
}

La forma che desideri è probabilmente qualcosa del tipo:

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

Questo è brutto, pidgin-php, quindi per favore verificalo prima. L'idea di base è generare ogni combinazione della stringa da [1..n] e quindi anteporre a tutte queste combinazioni ogni codice possibile per str [0]. Ricorda che nel peggiore dei casi questo avrà prestazioni esponenziali nella lunghezza della tua stringa, perché molta ambiguità è effettivamente presente nel tuo schema di codifica.

Il trucco non è solo quello di generare tutte le possibili combinazioni di lettere che corrispondono a un determinato numero, ma di selezionare la sequenza di lettere che è più facile da ricordare. Un suggerimento sarebbe quello di eseguire l'algoritmo soundex su ciascuna sequenza e provare a trovare una corrispondenza con un Dizionario in lingua inglese come Wordnet per trovare le sequenze più "realistiche".

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow