Permuting Lists of Lists – Print all possible words from phone digits

Given a list of arraylists containing elements, write a function that prints out the permutations of of the elements such that, each of the permutation set contains only 1 element from each arraylist and there are no duplicates in the list of permutation sets.

For example: consider the following lists

L1= {a1,b1,c1,d1} 
L2= {a2,b2,c2} 
L3= {a3, b3, c3} 

Valid Permutations are: 
{a1, a2, a3}
{a1, a2, b3}
{a1, a2, c3}
{a1, b2, a3}
{a1, b2, b3}
{a1, b2, c3}
... 
... 
...
{d1, c2, a3}
{d1, c2, b3}
{d1, c2, c3}

Please note that 
{a1,b2,c3} is same set as {b2,a1,c3}

We can solve this problem similar to we did solve the combination problem in a previous post here. This problem can be solved similarly where we consider the the input list as a multidimensional string that contains a list of string at each position. Anytime we will consider one single item. So, for each string in first list we do recurse to all other lists to find the combinations. We print the result whenever we reach the last list and output contains one elements from each of the n lists. Below is the implementation of this idea.

public static void permuteList(String[][] list, int start, ArrayList<String> perms){
	if(start == list.length){
		if(perms.size() == list.length)
			System.out.println(perms.toString());
		return;
	}
	
	for(int i = 0; i < list[start].length; i++){
		perms.add(list[start][i]);
		for(int j = start+1; j <= list.length; j++){
			permuteList(list, j, perms);
		}
		perms.remove(list[start][i]);
	}
}

Print All Words Based On Phone Number
Now let’s consider this problem,

Given a keypad as shown in diagram, and a n digit number, list all words which are possible by pressing these numbers.

For example if input number is 234, possible words which can be formed are (Alphabetical order):
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.

How do we solve this problem? Let’s quickly take our phone and look into the keypad. We will find –

0 --> {}
1 --> {}
2 --> {a,b,c}
3 --> {d,e,f}
4 --> {g,h,i}
5 --> {j,k,l}
6 --> {m,n,o}
7 --> {p,q,r,s} 
8 --> {t,u,v}
9 --> {w,x,y,z}

now if we press 2 there could be 3 possible values {a,b,c}. Then if we press 3 then the possible words would be all combination of 2 letters, one from 2–>{a,b,c} and other from 3->{d,e,f}. If we press down another number then the words formed will have first letter from 2-{a,b,c}, second number from 3->{d,e,f}, and 3rd letter from 4->{g,h,i}. Does this look familiar? Yes, we just solved the problem in the beginning of the article, this is basically permutation of lists of list.

Basically we run the algorithm with a list {L2, L3,L4} where
L2= {a,b,c}
L3= {d,e,f}
L4= {g,h,i}

So, given a sequence of n digits we will generate a list of lists using a precomputed map from digit to list of characters. Then we will call the permuteList.