Tworzenie permutacji przez wybieranie z tablic

Question

Mam tablicę 2D, która przechowuje różne litery odpowiadające tym, co można zobaczyć na klawiaturze telefonu.

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

Jeśli chcę, aby znaleźć wszystkie możliwe permutacje słowem 5 list, który trwa 1 list każdą z pierwszych 5 wierszy tablicy 2D, w jaki sposób to zrobić? Zastanawiam się nad rekurencją, ale to mnie po prostu dezorientuje.

Aby ten problem, łatwiej zrozumieć, oto przykład:

Słowo 3 litera ma swój pierwszy list z rzędu 1 {'A','B','C'}, swój drugi list z rzędu 3 {'G','H','I'}, a jego trzeci list z rzędu 6 , {'P','R','S'}. W sumie byłoby 27 możliwych wyników: 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

Można to rozwiązać za pomocą programowania dynamicznego.

Wykonaj pierwsze dwa wiersze i połącz wszystkie ciągi w tablicach. To da ci wynikową tablicę o rozmiarze m * n. Gdzie m jest rozmiarem pierwszej tablicy, a n jest rozmiarem drugiej tablicy. W twoim przypadku jest to 9. Następnie przypisz wynikową tablicę do pierwszej tablicy i przypisz trzecią tablicę do drugiej tablicy. Powtarzaj to do piątej tablicy. To da ci wszystkie możliwe ciągi z pierwszych pięciu tablic.

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

Ta funkcja powinna to zrobić.

Answer 2

Pierwszą rzeczą, którą należy zauważyć, jest to, że jeśli tworzysz słowa, wybierając jeden z 3 znaków z każdego z 5 wierszy, kończysz z 3 = łącznie 243 słowa. Bez względu na to, jak zaimplementujesz program, musi on zakończyć budowanie każdego z tych 243 słów.

Rekurencja jest to dobra strategia wdrożenia, ponieważ jasno wynika, że ​​jesteś wybierając jeden z trzech znaków w pierwszym rzędzie, a dla każdego z tych wyborów idziesz na, aby wybrać jeden z trzech znaków w drugim rzędzie , i tak dalej.

W poniższym programie Java pierwsza wersja makeWord jest funkcją rekursywną, która wybiera znak w wierszu indeksowanym przez currentRowIndex i dołącza ten znak do wordBuffer. Jeśli jest to ostatni wiersz, słowo jest kompletne i zostaje dodane do listy słów. W przeciwnym razie funkcja wywołuje się do pracy w wierszu currentRowIndex + 1.

Należy zauważyć, że bieżący stan wordBuffer przenosi się do wywołania rekursywnego. Dopiero po powrocie z wywołania rekursywnego usuwamy ostatni znak z wordBuffer.

Druga wersja makeWord pozwala przekazać tablicę indeksów wierszy, które określają wiersze, z których chcesz wybierać znaki.Na przykład, aby wybrać postacie z wierszy 1, 3 i 6, można by nazwać:

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

Można zastąpić to wezwanie w metodzie main zamiast bieżącej linii, co powoduje, słowo być zbudowany z postaciami z wierszy od 1 do 5:

permuter.makeWord(1, 5); 

Jeśli uważnie zapoznać się z metodami makeWord, zobaczysz, że pierwszy z nich nie recurse gdy ciąg jest kompletna, a drugi raz, a potem recurses zwraca wcześniej, ponieważ position == indices.length. To drugie podejście jest nieco mniej wydajne, ponieważ kosztuje jeszcze jedno wywołanie rekurencyjne, ale może się okazać, że wyraźniej wyraża ono pojęcie rekurencji. To kwestia gustu.

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

Oto jedno z możliwych rozwiązań.

Najpierw definiujesz sekwencję klawiszy, które chcesz nacisnąć. Na przykład, jeśli chcesz pobrać jedną literę z pierwszych pięciu wierszy tablicy, sekwencja będzie wynosić (1, 2, 3, 4, 5) (ponieważ pierwszy wiersz jest pusty). Jeśli chcesz przeliterować "stack", sekwencja będzie wynosić (6, 7, 1, 1, 4).

Następnie przeglądasz sekwencję. W każdym kroku dostajesz tablicę znaków odpowiadającą tej pozycji sekwencji. Następnie generujesz wszystkie słowa, które wynikają ze wszystkich kombinacji do tej pory, które są wszystkimi słowami z poprzedniego kroku w połączeniu ze wszystkimi znakami bieżącego kroku.

Ostatecznie wynikiem ostatniego kroku jest końcowy wynik zawierający wszystkie możliwe słowa.

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

Spróbuj tego, jeśli można użyć 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)); 
} 

Można również napisać wersję rekurencyjną.

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

Zadzwoń do tego.

permutation(convert, 5) 
     .forEach(x -> System.out.println(x)); 

Answer 5

Oto alternatywne rozwiązanie wykorzystujące strumienie Java 8 dla Twojego zainteresowania.

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

Zasadniczo jest to, że zajmuje kolektor każdy element w strumieniu i dodaje do każdego konkatenacji przedmiotów w elemencie oraz istniejących kombinacji nową kombinację.

A oto przykładowy kod pokazujący jak używać go:

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

parallel nie jest to bezwzględnie konieczne: to po prostu pokazać, że dla ogromnej liczby kombinacji strumień może być podzielone między procesorami, a następnie połączone .

Kod jest znacznie prostszy w przypadku innych rodzajów danych, które można naturalnie przesyłać strumieniowo. Niestety nie ma żadnego Arrays.stream(char[]), więc tradycyjna iteracja sprawia, że ​​kod jest nieco jaśniejszy.Możesz użyć czegoś brzydkiego, jak konwertowanie na ciąg znaków, a następnie IntStream, a następnie na Stream<Character>, ale szczerze, to dużo pracy, aby uniknąć iterowania po tablicy :-)