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