Creating permutations by selecting from arrays

Question

I have a 2D array that stores different letters that correspond to what you would see on a 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 the possible permutations of a 5 letter word that takes 1 letter each from the first 5 rows of the 2D array, how would I do that? I am thinking about recursion but it's just confusing me.

To make this problem easier to understand, here's an example:

A 3 letter word takes its first letter from row 1, {'A','B','C'}, its second letter from row 3, {'G','H','I'}, and its third letter from row 6, {'P','R','S'}. There would be in total 27 possible outcomes: 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 observe is that if you are making words by selecting one of 3 characters from each of 5 rows, you will end with 3⁵ = 243 words in total. Regardless of how you implement the program, it must end up building each of those 243 words.

Recursion is a good implementation strategy because it makes it clear that you're selecting one of the three characters in the first row, and for each of those choices you go on to select one of the three characters in the second row, and so on.

In the Java program below, the first version of makeWord is a recursive function that selects a character in the row indexed by currentRowIndex and appends that character to wordBuffer. If this is the last row, the word is complete and it gets appended to a list of words. Otherwise, the function calls itself to work on row currentRowIndex + 1.

Notice that the current state of wordBuffer carries through to the recursive call. Only after returning from the recursive call do we delete the last character from wordBuffer.

The second version of makeWord lets you pass an array of row indices that specify which rows you want to select characters from. For example, to select characters from rows 1, 3, and 6, you would call:

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

You can substitute that call in the main method instead of the current line, which causes a word to be built with characters from rows 1 through 5:

permuter.makeWord(1, 5);

If you take a close look at the makeWord methods, you'll see that the first one doesn't recurse when the string is complete, while the second one recurses once and then returns early because position == indices.length. The latter approach is slightly less efficient because it costs one more recursive call, but you may find that it expresses the concept of recursion more clearly. It's 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 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 call this.

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

Answer 3

This can be solved using dynamic programming approach.

Take the first two rows and combine all the strings in the arrays. That will give you a resultant 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 it is 9. Then assign the resultant array to the first array and assign the third array to the second array. Repeat it till the fifth array. That will give you all possible strings 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.

You first define the sequence of keys to be pressed. For example, if you want to take one letter each from the first five rows of the array, the sequence would be (1, 2, 3, 4, 5) (since the first row is empty). If you want to spell "stack", the sequence would be (6, 7, 1, 1, 4).

Then you loop through the sequence. In each step, you get the array of chars that correspond to this position of the sequence. Then you generate all the words that result from all the combinations so far, which are all the words from the previous step combined with all the chars of the current step.

Finally, the result of the last step is the final result that contains all the 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 alternate solution using Java 8 streams 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 this is a collector that takes each element in the stream and adds a new combination for every concatenation of the items in the element and the existing combinations.

And here's some 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);
}

The parallel isn't strictly necessary: it's just to show that for massive numbers of combinations the stream can be split across processors and then combined.

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