Java recursion phone number letters

Question

How do you write a java program using a recursive method that takes in an int like "234" and converts this into the corresponding letters on a phone pad (2 = ABC, 3 = DEF, etc), and prints out the permutations of this? e.g.:

input = 234

output = ADG ADH ADI AEG AEH AEI AFG AFH AFI BDG BDH BDI BEG BEH BEI BFG BFH BFI CDG CDH CDI CEG CEH CEI CFG CFH CFI

---

input = 89

output = TW TX TY TZ UW UX UY UZ VW VX VY VZ

Answer 1

1. Take input, convert to string

2. Call function generate(String prefix, String suffix) with empty prefix and converted input as suffix

3. Inside generate(), remove the first digit from suffix, map it to an array of corresponding letters and recursively call generate() for each letter from the array, appending it to the prefix.

Answer 2

import java.util.ArrayList;

class PhoneNumbers
{
    public static void main(String[] args)
    {
     for (String result: convert(args[0]))
      System.out.println(result);
    }

    public static ArrayList<String> convert(String phoneNumber)
    {   
     int digit = Integer.parseInt(phoneNumber.substring(0, 1));
     String letters = new String[] {
      "0",
      "1",
      "ABC",
      "DEF",
      "GHI",
      "JKL",
      // etc...
     }[digit];

     ArrayList<String> result = new ArrayList<String>();

     for (int i = 0; i < letters.length(); ++i) {
      char letter = letters.charAt(i);
      if (phoneNumber.length() > 1) {
       for (String rest: convert(phoneNumber.substring(1)))
        result.add(letter + rest);
      } else {
       result.add("" + letter);
      }
     }

     return result;
    }
}

java PhoneNumbers 234

ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
...

Answer 3

Generating permutations alone would constitute a good homework assignment, let alone the forced recursion and phone number distraction.

Small numbers of permutations can be generated efficiently through a method analogous to sorting networks. A sequence of n elements has n! permutations (assuming a full draw, with each permutation consisting of n elements as well). Observe that for a two-element sequence, there are two permutations:

• the original sequence, and
• the two elements swapped.

For a three-element sequence, there are six permutations:

• the permutations of the bottom two elements, then
• rotate the sequence one cell right (or left), and
• the permutations of the bottom two elements, then
• rotate the sequence one cell left (or right, opposite of above), and
• the permutations of the bottom two elements.

That is, it's the two-element version performed three times, with two intervening transformations. Now, a four-element sequence has twenty-four permutations:

• the permutations of the bottom three elements, then
• save position 1, assign 0 to 1, 3 to 0, and the saved value to 3, and
• the permutations of the bottom three elements, then
• swap positions 0 and 2, swap positions 1 and 3 (or rotate right by 2), and
• the permutations of the bottom three elements, then
• save position 3, assign 2 to 3, 0 to 2, and the saved value to 0, and
• the permutations of the bottom three elements.

Are you starting to see a pattern? Notice the recursive nature of the solution?

Above four elements, the patterns are harder to spot. You can iterate down the sequence, swapping the chosen element with the last element, reversing the sequence, expanding the bottom 24 permutations each time.

Try writing it out on paper, recording the steps you take to shuffle the elements, and you'll find you've written the program you need.

---

Note too that most of the solutions posted here use type String and keep chopping it up and reassembling it. String is a poor choice, given that it's immutable, when generating permutations is best done by swapping and rotating elements in a vector (really, a ring).

It's the rare case that you actually have to write the letters out to the destination stream, so bias your solution against that operation. Use an array of characters and write the characters to the stream one-by-one when it's time to emit a particular permutation. Forming a string just to dump the entry to a stream involves unnecessary allocation and copying.

Answer 4

Here's a version without either array or arraylist. Results are printed to stdout as you requested.

String allLetters = new String[] {
                "0",
                "1",
                "ABC",
                "DEF",
                "GHI",
                "JKL",
                // etc...
        };

public static void convert(String phoneNumber)
{
  convertSubstring(phoneNumber,"");
}

private static void convertSubstring(String phoneNumber, String convertedLetters)
{                   
  int digit = Integer.parseInt(phoneNumber.substring(0, 1));
  string letters=allLetters[digit];
  string remainingString=phoneNumber.substring(1);

  for (int i = 0; i < letters.length(); ++i) 
  {
     char letter = letters.charAt(i);
     String result=convertedLetters+letter;
     if (remainingString.length()==0)
        System.out.println(result);
     else
        convertSubstring(remainingString, result);
  }
}