più grande rettangolo possibile di lettere

Question

Scrivere un programma per trovare il più grande rettangolo di lettere possibile in modo che ogni riga formi una parola (da sinistra a destra) e ogni colonna formi una parola (dall'alto verso il basso).

Ho trovato questa interessante domanda. Non è compito a casa, anche se può sembrare come tale. (Non sono a scuola). Lo sto facendo per divertimento

Esempio

Da gatto, auto, ape, api, rep, punta otteniamo la seguente rettangolo (che è un quadrato):

c a r 
a p e 
t i p 

La mia idea iniziale è di costruire una sorta di albero di prefisso in modo da poter recuperare tutte le parole che iniziano con una stringa specifica. Questo sarebbe utile quando abbiamo già 2 o più parole (sia in lettura dall'alto verso il basso o da sinistra a destra) e abbiamo bisogno di trovare la parola successiva da aggiungere.

Altre idee?

Modifica

Questo potrebbe essere fatto con un cuboide (rettangolo 3D)?

Cosa fare se è necessario disporre di parole valide sulle diagonali (credito idea: utente645466); come sarebbe ottimizzato il algo per questo?

Answer 1

Sia D il dizionario. Risolve m e n. Possiamo formulare il problema di trovare un rettangolo m × come constraint satisfaction problem (CSP).

x _{i, 1} & hellip; x _{i, n} ∈ D         & forall; i ∈ {1, & hellip ;, m}
x _{1, j} & hellip; x _{m, j} ∈ D         & forall; j ∈ {1, & hellip ;, n}
x _{i, j} ∈ {A, & hellip ;, Z}         & forall; i ∈ {1, & hellip ;, m}, e forall; j ∈ {1, & hellip ;, n}

Un approccio comune per risolvere i CSP è quello di combinare il backtracking con la propagazione dei vincoli. In parole povere, backtracking significa che selezioniamo una variabile, indoviniamo il suo valore e risolviamo ricorsivamente il sottoproblema con una variabile in meno e la propagazione dei vincoli significa provare a ridurre il numero di possibilità per ogni variabile (possibilmente a zero, il che significa che non c'è soluzione).

Come esempio, si potrebbe iniziare una griglia 3 × 3 scegliendo x _1,1 = Q.

Q?? 
??? 
??? 

con un dizionario inglese, l'unica possibilità per x _1,2 e x _2,1 è U (in prima Scrabble “ parole ”).

L'arte di risolvere i CSP è il bilanciamento tra il backtracking e la propagazione dei vincoli. Se non propagiamo affatto i vincoli, useremo solo la forza bruta. Se propagiamo perfettamente i vincoli, non è necessario tornare indietro, ma un algoritmo di propagazione che risolva un problema NP-hard di per sé è probabilmente piuttosto costoso da eseguire.

In questo problema, lavorare con un dizionario di grandi dimensioni su ciascun nodo di backtracking diventerà costoso a meno che non si abbia un buon supporto della struttura dati. Delineerò un approccio che utilizza uno trie o un DAWG rapidamente per calcolare il set di lettere tramite il quale un prefisso si estende a una parola completa.

A ciascun nodo di backtracking, l'insieme di variabili che abbiamo assegnato è un tableau Young. In altre parole, nessuna variabile viene assegnata fino a quando non sono state assegnate le variabili sopra di esso e a sinistra. Nello schema seguente, . indica una variabile assegnata e * e ? indicano le variabili non assegnate.

.....* 
...*?? 
...*?? 
..*??? 
*????? 

Le variabili contrassegnate * sono candidati per la prossima ad essere assegnato un valore. Il vantaggio di avere più scelte piuttosto di scegliere una variabile fissa ogni volta è che alcuni ordini variabili possono essere molto migliori di altri.

Per ogni *, effettuare due ricerche nel trie/DAWG, uno per l'orizzontale e uno per la verticale, e calcolare l'intersezione delle serie di lettere che possono venire dopo. Una strategia classica è scegliere la variabile con il minor numero di possibilità nella speranza di raggiungere più rapidamente una contraddizione. Mi piace questa strategia perché si libera naturalmente quando c'è una variabile con zero possibilità e si propaga naturalmente quando c'è una variabile con una. Memorizzando i risultati, possiamo valutare molto rapidamente ciascun nodo.

Answer 2

Dato il dizionario di parole di una determinata lunghezza, creare due nuovi dizionari: Il primo contiene tutti i prefissi di singole lettere delle parole (tutte le lettere che possono essere la prima lettera di una parola della lunghezza specificata) e la seconda contiene tutti i prefissi a doppia lettera delle parole (tutte le sequenze di due lettere che possono essere le prime due lettere di una parola della lunghezza specificata). Puoi anche fare tripli prefissi, ma probabilmente non dovrai andare oltre.

1. Scegliere una parola dal dizionario, chiamarla X. Questa sarà la prima riga della matrice.

2. Verificare che X[1], X[2], ..., X[N] siano tutti prefissi di singola lettera validi utilizzando quella pratica lista che hai creato. Se lo sono, andare al passaggio 3; altrimenti tornare al passaggio 1.

3. Scegliere una parola dal dizionario, chiamarla Y. Questa sarà la seconda riga della matrice.

4. Controllare che X[1] Y[1], X[2] Y[2], ..., X[N] Y[N] sono tutti validi prefissi doppia lettera con quella lista a portata di mano hai fatto. Se lo sono, andare al passaggio 5; altrimenti tornare al passo 3. Se questa era l'ultima parola nel dizionario, poi tutta la strada fino al punto 1.

   ...

   2 (N-1). Scegli una parola dal dizionario, chiamala Z.Questa sarà l'ennesima riga della matrice.

   2N. Verifica che X[1] Y[1] ... Z[1], X[2] Y[2] ... Z[2], ..., X[N] Y[N] ... Z[N] siano tutte parole nel dizionario. Se lo sono, congratulazioni, ce l'hai fatta! Altrimenti, tornare al passaggio 2 (N-1). Se questa era l'ultima parola nel dizionario, quindi tornare al passaggio 2 (n-3).

La logica è quella di costruire il rettangolo di parole una riga alla volta, selezionando le parole per le righe e quindi verifica che la colonna potrebbe essere completato alle parole. Questo progredirà molto più velocemente rispetto all'aggiunta di una lettera alla volta.

Answer 3

Creare una Borsa [] per parola della stessa lunghezza = indice quindi creare una serie di tentativi, un trie per listaParole di ogni lunghezza

Rectangle makeRectangle(length, height, rectangle) 
    { 
     if (length == rectangle.length()) check if complete and return; 
     checkIfPartialComplete - check columns for valid prefixes 
     for (i from 1 to grouplist[i-1]) 
     { 
      newRectangle = append word[i] to rectangle 
      return makeRectangle(l,h, rectangle with appended word) if not equal to null 
     } 
    } 


boolean checkPartial(int l, Trie trie) 
{ 
    for (int i =0 ; i < l; i++) 
    { 
     String col = getColumn(i); 
     if (!trie.contains(col)) 
     { 
      return false; 
     } 
    } 
    return true; 
} 
boolean checkComplete(int l, Bag<String> lengthGroup) 
{ 
    for (int i=0; i < l ; i++) 
    { 
     String col = getColumn(i); 
     if (!lengthGroup.contains(col)) 
     { 
      return false; 
     } 
    } 
    return true; 
}