Creating permutations by choosing from arrays

Question

I have a 2D array that stores different letters corresponding to what you see on the phone keypad.

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

If I want to find all possible permutations of a 5-letter word that takes 1 letter from the first 5 lines of a 2D array, how would I do it? I think of recursion, but it just baffles me.

To simplify this problem, here is an example:

A 3-letter word takes its first letter from line 1, {'A','B','C'} , its second letter from line 3, {'G','H','I'} and its third letter from line 6, {'P','R','S'} . There would be 27 possible results: 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

The first thing to notice is that if you make words by choosing one of 3 characters from each of 5 lines, you will end up with 3 ⁵ = 243 words. No matter how you implement the program, it must create each of these 243 words.

Recursion is a good implementation strategy because it makes it clear that you are choosing one of the three characters in the first line, and for each of these options you are choosing one of the three characters in the second line, etc.

In the Java program below, the first version of makeWord is a recursive function that selects a character in the string indexed by currentRowIndex and adds that character to wordBuffer . If this is the last line, the word is completed and added to the list of words. Otherwise, the function calls itself to work on the currentRowIndex + 1 .

Note that the current state of wordBuffer carried over to the recursive call. Only after returning from the recursive call, we remove the last character from wordBuffer .

The second version of makeWord allows makeWord to pass an array of string indices that determine which strings you want to select characters from. For example, to select characters from lines 1, 3, and 6, you would call:

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

You can replace this call in the main method instead of the current line, which forces the word to build with characters from lines 1 to 5:

 permuter.makeWord(1, 5); 

If you look closely at the makeWord methods, you will see that the first does not recurs when the line is completed, and the second repeats once, and then returns earlier, because position == indices.length . The latter approach is slightly less efficient, as it requires another recursive call, but you may find that it more clearly expresses the concept of recursion. This is a matter of taste.

 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 2

Try this if you can use 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)); } 

You can also write a recursive version.

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

And name it.

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

Answer 3

This can be solved using the dynamic programming approach.

Take the first two lines and concatenate all the lines in arrays. This will give you a resulting array of size m * n. Where m is the size of the first array and n is the size of the second array. In your case, this is 9. Then assign the resulting array to the first array and assign the third array to the second array. Repeat it until the fifth array. This will give you all possible rows from the first five arrays.

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

This function should do it.

Answer 4

Here is one possible solution.

First, you determine the sequence of keys pressed. For example, if you want to take one letter from the first five lines of the array, the sequence will be (1, 2, 3, 4, 5) (since the first line is empty). If you want to write a "stack", the sequence will be (6, 7, 1, 1, 4).

Then you execute the sequence. At each step, you get an array of characters corresponding to this position of the sequence. Then you generate all the words that are the result of all the combinations so far, which are all the words from the previous step in combination with all the characters of the current step.

Finally, the result of the last step is the final result containing all possible words.

 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 5

Here's an alternative solution using Java 8 threads for your interest.

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

Essentially, it is a collector that takes every element in the stream and adds a new combination for each concatenation of elements in the element and existing combinations.

And here is a sample code showing how to use it:

 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 not strictly necessary: ​​just to show that for massive numbers of combinations the stream can be divided into processors and then combined.

The code is much simpler for other types of data that can be naturally transmitted. Unfortunately, there is no Arrays.stream(char[]) , so the traditional iteration makes the code more understandable. You can use something ugly, like converting to a string and then IntStream and then to Stream<Character> , but frankly, a lot of work to avoid iterating over the array :-)