Creazione di permutazioni selezionando dagli array

Question

Ho una matrice 2D che memorizza diverse lettere che corrispondono a ciò che vedresti sul tastierino del telefono.

char [][] convert = 
    { {}, 
     {'A','B','C'}, 
     {'D','E','F'},  
     {'G','H','I'}, 
     {'J','K','L'}, 
     {'M','N','O'}, 
     {'P','R','S'}, 
     {'T','U','V'}, 
     {'W','X','Y'} 
    }; 

Se voglio trovare tutte le possibili permutazioni di una 5 lettera parola che prende 1 lettera ciascuna dalle prime 5 righe della matrice 2D, come avrei fatto? Sto pensando alla ricorsione, ma mi sta solo confondendo.

Per rendere il problema più facile capire, qui è un esempio:

Una parola 3 lettera prende prima lettera di fila 1, {'A','B','C'}, la seconda lettera di fila 3, {'G','H','I'}, e la sua terza lettera fila 6 , {'P','R','S'}. Ci sarebbero in totale 27 possibili risultati: AGP AGR AGS AHP AHR AHS AIP AIR AIS BGP BGR BGS BHP BHR BHS BIP BIR BIS CGP CGR CGS CHP CHR CHS CIP CIR CIS.

Answer 1

Questo può essere risolto utilizzando un approccio di programmazione dinamico.

Prendere le prime due righe e combinare tutte le stringhe negli array. Questo ti darà una serie risultante di dimensioni m * n. Dove m è la dimensione del primo array e n è la dimensione del secondo array. Nel tuo caso è 9. Quindi assegna l'array risultante al primo array e assegna il terzo array al secondo array. Ripeti fino al quinto array. Questo ti darà tutte le possibili stringhe dai primi cinque array.

public static String[] getAllCombinations(String array[][], int l) { 
    String a[] = array[0]; 

    String temp[]=null; 
    for(int i=1;i<l;i++) { 
     int z=0; 
     String b[] = array[i]; 
     temp = new String[a.length*b.length]; 
     for(String x:a) { 
      for(String y:b) { 
       temp[z] = ""+x+y; 
       z++; 
      } 
     } 
     a = temp; 
    } 
    System.out.println(temp.length); 
    return temp; 
} 

Questa funzione dovrebbe farlo.

Answer 2

La prima cosa da osservare è che se si stanno facendo le parole selezionando uno dei 3 caratteri da ciascuna delle 5 righe, si termina con 3 = 243 parole in totale. Indipendentemente da come si implementa il programma, deve finire per costruire ognuna di quelle 243 parole.

La ricorsione è una buona strategia di implementazione perché rende chiaro che si sta selezionando uno dei tre caratteri nella prima riga e per ciascuna di queste opzioni si seleziona uno dei tre caratteri nella seconda riga , e così via.

Nel programma Java seguente, la prima versione di makeWord è una funzione ricorsiva che seleziona un carattere nella riga indicizzata da currentRowIndex e aggiunge tale carattere a wordBuffer. Se questa è l'ultima riga, la parola è completa e viene aggiunta ad un elenco di parole. In caso contrario, la funzione si chiama per funzionare sulla riga currentRowIndex + 1.

Si noti che lo stato corrente di wordBuffer viene trasferito alla chiamata ricorsiva. Solo dopo il ritorno dalla chiamata ricorsiva eliminiamo l'ultimo carattere da wordBuffer.

La seconda versione di makeWord consente di passare una matrice di indici di riga che specifica da quali righe si desidera selezionare i caratteri.Ad esempio, per selezionare i caratteri da righe 1, 3 e 6, si potrebbe chiamare:

permuter.makeWord(new int[]{ 1, 3, 6 }, 0); 

è possibile sostituire quella chiamata nel metodo al posto della riga corrente main, che provoca una parola da costruire con i personaggi da righe da 1 a 5:

permuter.makeWord(1, 5); 

Se si dà un'occhiata da vicino i metodi makeWord, vedrete che il primo non recurse quando la stringa è completa, mentre il secondo recurses una volta e poi ritorna presto perché position == indices.length. Quest'ultimo approccio è leggermente meno efficiente perché costa un altro richiamo ricorsivo, ma potreste scoprire che esprime più chiaramente il concetto di ricorsione. È una questione di gusti.

import java.util.*; 

public class PermuteCharacters { 
    char[][] rows = { 
    {}, 
    {'A','B','C'}, 
    {'D','E','F'},  
    {'G','H','I'}, 
    {'J','K','L'}, 
    {'M','N','O'}, 
    {'P','R','S'}, 
    {'T','U','V'}, 
    {'W','X','Y'} 
    }; 

    StringBuffer wordBuffer = new StringBuffer(); 
    ArrayList<String> words = new ArrayList<String>(); 

    void makeWord(int currentRowIndex, int endRowIndex) { 
    char[] row = rows[currentRowIndex]; 
    for (int i = 0; i < row.length; ++i) { 
     wordBuffer.append(row[i]); 
     if (currentRowIndex == endRowIndex) { 
     words.add(wordBuffer.toString()); 
     } else { 
     makeWord(currentRowIndex + 1, endRowIndex); 
     } 
     wordBuffer.deleteCharAt(wordBuffer.length() - 1); 
    } 
    } 

    void makeWord(int[] indices, int position) { 
    if (position == indices.length) { 
     words.add(wordBuffer.toString()); 
     return; 
    } 
    char[] row = rows[indices[position]]; 
    for (int i = 0; i < row.length; ++i) { 
     wordBuffer.append(row[i]); 
     makeWord(indices, position + 1); 
     wordBuffer.deleteCharAt(wordBuffer.length() - 1); 
    } 
    } 

    void displayWords() { 
    if (words.size() != 0) { 
     System.out.print(words.get(0)); 
     for (int i = 1; i < words.size(); ++i) { 
     System.out.print(" " + words.get(i)); 
     } 
     System.out.println(); 
    } 
    System.out.println(words.size() + " words"); 
    } 

    public static void main(String[] args) { 
    PermuteCharacters permuter = new PermuteCharacters(); 
    permuter.makeWord(1, 5); 
    permuter.displayWords(); 
    } 
} 

Answer 3

Ecco una possibile soluzione.

Prima si definisce la sequenza di tasti da premere. Ad esempio, se si desidera prendere una lettera ciascuna dalle prime cinque righe dell'array, la sequenza sarà (1, 2, 3, 4, 5) (poiché la prima riga è vuota). Se vuoi scrivere lo "stack", la sequenza sarà (6, 7, 1, 1, 4).

Quindi si scorre la sequenza. In ogni passaggio, ottieni la matrice di caratteri che corrisponde a questa posizione della sequenza. Quindi generate tutte le parole risultanti da tutte le combinazioni finora, che sono tutte le parole del passaggio precedente combinate con tutti i caratteri del passaggio corrente.

Infine, il risultato dell'ultimo passaggio è il risultato finale che contiene tutte le parole possibili.

char [][] convert = { 
    {},    // 0 
    {'A','B','C'}, // 1 
    {'D','E','F'}, // 2 
    {'G','H','I'}, // 3 
    {'J','K','L'}, // 4 
    {'M','N','O'}, // 5 
    {'P','R','S'}, // 6 
    {'T','U','V'}, // 7 
    {'W','X','Y'} // 8 
}; 

// Sequence of keys to be pressed. In this case the pressed keys are 
// [ABC], [DEF], [GHI] 
int[] sequence = new int[] {1, 2, 3}; 

// List for storing the results of each level. 
List<List<String>> results = new ArrayList<>(); 

for(int i=0; i<sequence.length; i++){ 

    // Results of this level 
    List<String> words = new ArrayList<>(); 
    results.add(words); 

    List<String> prevLevelWords; 
    if(i==0){ 
    prevLevelWords = Collections.singletonList(""); 
    } else { 
    prevLevelWords = results.get(i-1); 
    } 

    char[] thisLevelChars = convert[sequence[i]]; 

    if(thisLevelChars.length == 0){ 
    words.addAll(prevLevelWords); 
    } else { 
    for(String word : prevLevelWords){ 
     for(char ch : convert[sequence[i]]){ 
     words.add(word + ch); 
     } 
    } 
    } 
} 

List<String> finalResult = results.get(sequence.length-1); 

for(String word : finalResult) { 
    System.out.println(word); 
} 

Run it

Answer 4

Prova questa, se è possibile utilizzare Java8

static Stream<String> stream(char[] chars) { 
    return new String(chars).chars().mapToObj(c -> Character.toString((char)c)); 
} 

public static void main(String[] args) { 
    char [][] convert = 
     { {}, 
      {'A','B','C'}, 
      {'D','E','F'},  
      {'G','H','I'}, 
      {'J','K','L'}, 
      {'M','N','O'}, 
      {'P','R','S'}, 
      {'T','U','V'}, 
      {'W','X','Y'} 
     }; 
    stream(convert[1]) 
     .flatMap(s -> stream(convert[2]).map(t -> s + t)) 
     .flatMap(s -> stream(convert[3]).map(t -> s + t)) 
     .flatMap(s -> stream(convert[4]).map(t -> s + t)) 
     .flatMap(s -> stream(convert[5]).map(t -> s + t)) 
     .forEach(x -> System.out.println(x)); 
} 

Si può anche scrivere versione ricorsiva.

static Stream<String> permutation(char[][] convert, int row) { 
    return row == 1 
     ? stream(convert[1]) 
     : permutation(convert, row - 1) 
      .flatMap(s -> stream(convert[row]).map(t -> s + t)); 
} 

E chiamare questo.

Answer 5

Ecco una soluzione alternativa utilizzando Java 8 flussi per il vostro interesse.

public class Combiner { 
    private List<String> combos = new ArrayList<>(); 

    public Stream<String> stream() { 
     return combos.stream(); 
    } 

    public void accept(char[] values) { 
     if (combos.isEmpty()) { 
      for (char value : values) { 
       combos.add(String.valueOf(value)); 
      } 
     } else { 
      Combiner other = new Combiner(); 
      other.accept(values); 
      combine(other); 
     } 
    } 

    public Combiner combine(Combiner other) { 
     combos = stream() 
       .flatMap(v1 -> other.stream().map(v2 -> v1 + v2)) 
       .collect(Collectors.toList()); 
     return this; 
    } 
} 

Essenzialmente questo è un collettore che prende ogni elemento nel flusso e aggiunge una nuova combinazione per ogni concatenazione degli elementi nell'elemento e le combinazioni esistenti.

Ed ecco alcuni esempi di codice che mostra come usarlo:

public static void main(String[] args) { 
    char[][] vals = {{'a', 'b'}, {'c'}, {'d', 'e'}, {'f', 'g', 'h'}}; 

    Arrays.stream(vals).parallel() 
      .collect(Combiner::new, Combiner::accept, Combiner::combine) 
      .stream().forEach(System.out::println); 
} 

Il parallel non è strettamente necessario: è solo per dimostrare che per un massiccio numero di combinazioni del flusso possono essere divisi tra i processori e poi combinati .

Il codice è molto più semplice per altri tipi di dati che possono essere trasmessi in modo naturale. Purtroppo non c'è lo Arrays.stream(char[]) quindi l'iterazione tradizionale rende il codice un po 'più chiaro.Puoi usare qualcosa di brutto come convertire in stringa poi un IntStream e poi in Stream<Character> ma francamente è un sacco di lavoro per evitare di scorrere l'array :-)