Algoritmo per trovare le parole spiegate da un numero

Question

Sto cercando di trovare un modo per determinare tutte le possibili parole che possono essere scritte da un determinato numero, data una mappatura di alfabeti ai valori.

Alla fine voglio trovare una soluzione che funzioni per qualsiasi mappatura di valori a 1 o 2 cifre per una lettera, ma per l'illustrazione, supponiamo che A = 1, B = 2, ... Z = 26.

Esempio: 12322 può essere uguale a abcbb (1,2,3,2,2) , lcbb (12,3,2,2) , awbb (1,23,2,2) , abcv (1,2,3,22) , awv (1,23, 22) o lcv (12,3,22) .

---

Ecco cosa ho pensato finora:

Costruirò un albero di tutte le parole possibili usando il numero.

Per fare ciò, inizierò con un albero con un nodo radice con dati fittizi.

Analizzerò quindi il numero cifra per cifra a partire dalla cifra meno significativa.

Ad ogni passo, prenderò l'ultima cifra della parte rimanente del numero e la inserirò nella sottostruttura sinistra del nodo corrente, e rimuoverò quella cifra dal numero per la sottostruttura sinistra di quel nodo. Per lo stesso nodo, quindi verificherò se le DUE cifre precedenti insieme formano un alfabeto valido e, in tal caso, le inserirò nella sottostruttura corretta (e rimuoverò le 2 cifre dal numero per la sottostruttura destra di quel nodo).

Quindi ripeterò i passaggi precedenti in modo ricorsivo per ciascun nodo, usando la parte del numero che rimane, fino a quando non ci saranno più cifre.

Per illustrare, per 12322 il mio albero sarà simile a questo:

                *
             /     \
            /       \
           2         22
         /         /   \
        2         3     23
      /   \      / \    /
    3      23   2   12 1
   / \    /    /
  2   12 1    1
 /
1 

Quindi, per ottenere le parole, attraverserò tutti i possibili percorsi dalle foglie ai nodi.

---

Questa sembra essere una soluzione troppo complessa per quello che pensavo potesse essere un problema abbastanza semplice, e sto cercando di scoprire se esiste un modo più semplice per risolverlo.

Answer 1

Supponi di avere già tutte le possibili combinazioni di [2, 3, 2, 2] , quale sarebbe la combinazione di [1, 2, 3, 2, 2] (aggiungi [1] alla testa)? Non è difficile dedurre che dovrebbe essere:

  A1: put [1] to the head of all_the_combinations_of[1,2,3,2,2] and 
  A2: put [1*10 + 2] to the head of all_the_combinations_of[2,3,2,2] if [1*10 + 2 <=26]

Una volta ottenuto questo, dovrebbe essere facile quanto segue. Ho implementato una versione di Ruby con la traccia della recusione come riferimento.

def comb a
    c = []
    puts a.inspect
    return [a] if a.length <= 1

    c =  comb(a[1..-1]).map {|e| [a[0]] + e}
    if a[0] * 10 + a[1] <= 26
            c += comb(a[2..-1]).map { |f| [a[0] * 10 + a[1]] + f }
    end
    c
end

h = Hash[*(1..26).to_a.zip(('A'..'Z').to_a).flatten]
#h.keys.sort.each {|k| puts "#{k}=>#{h[k]}"}

comb([1,2,3,2,2]).each do |comb|
    puts comb.map {|k| h[k]}.join
end

[1, 2, 3, 2, 2]
  A1 [2, 3, 2, 2]
      [3, 2, 2]
         [2, 2]
            [2]
             []
      [2, 2]
         [2]
          []
  A2 [3, 2, 2]
      [2, 2]
         [2]
          []
ABCBB
ABCV
AWBB
AWV
LCBB
LCV

Answer 2

In realtà non è necessario costruire un albero - basta ricorrere:

1. Prendi una singola cifra. Vedi se riusciamo a formare una parola considerandola come una lettera in sé e ricorrere.
2. Quando torniamo dalla ricorsione, prova ad aggiungere un'altra cifra (se eravamo 1 o 2 in precedenza) e ricominciare.

Answer 3

Una soluzione a forza bruta sarebbe quella di riempire dinamicamente l'array da 1 a N, dove a [i] contiene un insieme di stringhe che formano a [1] a [2 ] a [3] ... a [i] dopo l'espansione. Puoi inserire un [1] da stratch, quindi riempire a [2] , basato su a [1] e sul secondo carattere nella stringa. Quindi riempi un [3], ecc. Ad ogni puntata devi solo guardare indietro a a [i-1] e a [i-2] (e a s [i-1] e s [i] , dove s è la sequenza numerica).

Alla fine, dopo aver inserito a [n] , conterrà la risposta.

Nell'esempio '12322', la sequenza diventa:

a[1] = { "a" }
a[2] = { a + 'b' | a in a[1] } union { "l" } = { "ab", "l" }
a[3] = { a + 'c' | a in a[2] } union { a + 'w' | a in a[1] } = { "abc", "lc", "aw" }
a[4] = { a + 'b' | a in a[3] } union { } = { "abcb", "lcb", "awb" }
a[5] = { a + 'b' | a in a[4] } union { a + 'v' | a in a[3] } = { "abcbb", "lcbb", "awbb", "abcv", "lcv", "awv" }

Questa è essenzialmente la versione di programmazione dinamica della soluzione ricorsiva sopra.

Answer 4

Un modo alternativo per farlo sarebbe quello di invertire il problema:

• Dato un dizionario di parole, calcola le stringhe numeriche che verrebbero generate e archivia questi dati in una struttura mappa / dizionario, ovvero tabella ['85 '] =' hi '
• Per ciascuna delle prime x cifre del numero che stai cercando, vedi se si trova nella tabella, ad esempio table.ContainsKey ('1'), table.ContainsKey ('12 '), ...
• Se stai cercando di trovare le sequenze di parole, genera le parole che iniziano in ogni posizione nella stringa numerica, quindi esegui una ricerca ricorsiva per trovare tutte le frasi da ciò.