Sebbene possa esserci una soluzione più ideale là fuori, penso che ti avvicinerà. In questo momento il tuo algoritmo classifica le parole che hanno lettere "rare" più importanti della copertura generale per la lista di lettere. Probabilmente il modo migliore per ridurre il numero di parole che utilizzi sarà quello di scegliere parole che contengono la maggior parte delle lettere che ti servono ancora.
Ad esempio, supponi di cercare il minor numero di parole che, insieme, contenga le seguenti lettere:
Letters
--------
a
b
c
d
e
f
Words
--------
ace
bread
fork
whistle
crab
monkey
car
fork
dog
diamond
Un modo semplice per capire quanto sia utile ogni parola sarebbe guardare ogni parola e calcolare quale delle lettere desiderate contiene. Possiamo farlo usando una serie di flag booleani per ogni parola.
Words | a | b | c | d | e | f
---------------------------------
ace | T | F | T | F | T | F
bread | T | T | F | T | T | F
fear | T | F | F | F | T | T
whistle | F | F | F | F | T | F
crab | T | T | T | F | F | F
monkey | F | F | F | F | T | F
car | T | F | T | F | F | F
fork | F | F | F | F | F | T
dog | F | F | F | T | F | F
diamond | T | F | F | T | F | F
coffee | F | F | T | F | T | T
---------------------------------
Total | 6 | 2 | 4 | 3 | 6 | 3
Da quando abbiamo appena iniziato, abbiamo bisogno di tutto. Quindi lascia solo dare ad ogni parola un punteggio in base a quante lettere ha che abbiamo ancora bisogno.
Used Words:
Letters Remaining: a, b, c, d, e, f
Words | a | b | c | d | e | f | Score
-----------------------------------------
ace | T | F | T | F | T | F | 3
bread | T | T | F | T | T | F | 4
fear | T | F | F | F | T | T | 3
whistle | F | F | F | F | T | F | 1
crab | T | T | T | F | F | F | 3
monkey | F | F | F | F | T | F | 1
car | T | F | T | F | F | F | 2
fork | F | F | F | F | F | T | 1
dog | F | F | F | T | F | F | 1
diamond | T | F | F | T | F | F | 2
coffee | F | F | T | F | T | T | 3
Quindi prendiamo quello che mette fuori più lettere. In questo caso "pane". Il che significa che le uniche lettere che abbiamo lasciato da usare sono "c, f". Diamo ad ogni parola un nuovo punteggio basato sulle lettere che ci servono.
Used Words: bread
Letters Remaining: c, f
Words | a | b | c | d | e | f | Score | Score 2
--------------------------------------------------
ace | T | F | T | F | T | F | 3 | 1
bread | T | T | F | T | T | F | 4 | -
fear | T | F | F | F | T | T | 1 | 1
whistle | F | F | F | F | T | F | 1 | 1
crab | T | T | T | F | F | F | 3 | 0
monkey | F | F | F | F | T | F | 1 | 1
car | T | F | T | F | F | F | 2 | 1
fork | F | F | F | F | F | T | 1 | 1
dog | F | F | F | T | F | F | 1 | 0
diamond | T | F | F | T | F | F | 2 | 0
coffee | F | F | T | F | T | T | 3 | 2
Ora possiamo prendere "caffè" che ha un punteggio di 2 e che utilizza tutte le lettere che volevamo usare. Ovviamente questo ha alcuni difetti. In primo luogo, le tue scelte successive dipendono da quale sia stata la tua prima scelta. Se hai scelto una parola che ha ottenuto molte lettere comuni ma non ha colpito quelle più rare, probabilmente finirai con una parola che colpisce molte lettere e un gruppo che ne riceve solo una o due. Questo potrebbe essere risolto pesando i punteggi in modo che le lettere più rare valgano di più (un po 'come giocare a Scrabble).
Una cosa che potresti aver notato è dover ricalcolare il punteggio su ogni passaggio. E sarà un dolore. Ma cosa succede se abbiamo usato alcuni trucchi intelligenti per renderlo più facile? E se invece di una serie di booleani per ogni parola, l'abbiamo trasformata in una sequenza di bit? (La stessa cosa, ma è più facile lavorare con questo.)
Quindi, se abbiamo riscritto la tabella dove come bit, potrebbe apparire come questa:
Words | Bits (a|b|c|d|e|f)
---------------------------------
ace | 101010
bread | 110110
fear | 100011
whistle | 000010
crab | 111000
monkey | 000010
car | 101000
fork | 000001
dog | 000100
diamond | 100100
coffee | 001011
Il calcolo del punteggio diventa ora un semplice XOR con una maschera per le lettere che ti servono (all'inizio, 111111 poi successivamente 001001 ), quindi contati solo i bit reali. Ricalcolo piuttosto semplice.
Se vuoi pesare l'algoritmo, diventa un po 'più facile da eseguire ma più difficile da configurare. Se hai preso il conteggio di ogni lettera per trovare quelli più rari (come ho fatto nella prima parte), potresti disporre che la maschera di bit non sia più in ordine alfabetico ma in ordine di rarità (la cosa più rara è la prima). In questo caso la tua maschera di bit sembrerebbe (b|d|f|c|a|e) . Quindi i confronti del punteggio sono solo ordinati dal numero intero più alto dopo l'applicazione della maschera. (Nota: si incontrano alcuni problemi quando due lettere sono legate per rarità. Devi solo essere consapevole che può distorcere i tuoi risultati. Speriamo che non ci siano molti casi di questo in elenchi di parole più grandi.)
Questo non è perfetto, ma è un buon inizio.