How can I generate word combinations for phone numbers using recursion?

[transgalactic]

i have tried the medium part
but i couldn't get it solved
so i am asking if you have some people that can solve this recursive question

here is a question and i have a very similar code but i need to convert it
some how in order to fit this question

question:
In order to make their phone numbers more memorable, service providers like to find numbers that spell out some word (called a mnemonic) appropriate to their business that makes that phone number easier to remember. For example, the phone number for a recorded time-of-day message in some localities is 637-8687 (NERVOUS). Imagine that you have just been hired by a local telephone company to write a method listMnemonics that will generate all possible letter combinations that correspond to a given number, represented as a string of digits. For example, if you call
recursiveObject.listMnemonics("723")
your method shall generate and print out (using recursion) the following 27 possible letter combinations that correspond to that prefix:
PAD PBD PCD RAD RBD RCD SAD SBD SCD
PAE PBE PCE RAE RBE RCE SAE SBE SCE
PAF PBF PCF RAF RBF RCF SAF SBF SCF

notice that always every char come from a different group
for each uniq group of letters we have its reprasentative number
my efforts in solving it:
i know that in order to solve this question is need to use a recursive methos that
prints out all the subsets of a given string letters with a given resolt string size

i have built this code

public class subsets {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String word="abcd";
		
		
subsets(word.length(),3,"",word);
	}
	public static void phone(String phone){
		
	}
	public static void subsets(int n,int k,String also,String word){
		if (n==0){
			if (also.length()==k){
			System.out.println(also);
			}
		}
		else{
			subsets(n-1,k,also+word.charAt(n-1),word);
			subsets(n-1,k,also,word);
			
				
			
		}
	}
 
}

 

[-Job-]

You can implement a recursive algorithm that recursively generates a "tree" of function calls, the "leaves" of which correspond to a mnemonic.

For example see the code below which I've not tested but depicts the strategy:

public void ListMnemonics(String phoneNum, String mnem){
    if(mnem.length == phoneNum.length){
        //if we get here then we're on a leaf, just print the mnemonic and exit
        System.out.println(mnem);
        return;
    }
    /* implement GetLettersCorrespondingToNumber to return a string of letters that
        correspond to a given telephone key */
    String letters = GetLettersCorrespondingToNumber(phoneNum[mnem.length]);
    for(int i=0; i<letters.length; i++){

        ListMnemonics(phoneNum, mnem + letters.charAt(i));
    }
}

ListMnemonics("4443220", "");

 

[transgalactic]

there is no binary tree here

i am really having a hard time to understand what are you doing
can make an example please

 

[-Job-]

That is an example, I'm afraid i can't make it any simpler. What are you having trouble understanding specifically?

 

[transgalactic]

i am having trouble to understand
where is the termins of a binary tree
left right data node
i can't see any code related to it
where are you using it?

 

[-Job-]

I'm not using a tree, i just mentioned that the recursive function generates a "tree of function calls". For example, if each telephone digit corresponds to 3 letters, then the first time you call ListMnemonics("1234567", "") it calls itself 3 times, each one of those calls will call itself 3 times, which will call itself 3 times again and so on 7 times (seven being the length of the telephone number 1234567).

Each of the function calls checks to see if the mnemonic it received is of length 7, if it is that mnemonic is complete, if it's not then it calls itself 3 times appending a new character to the mnemonic.

 

[transgalactic]

what "mnem" string represents??
i can't see here the dictionery where
for example for 1 we have a, b, c
2 d e f
. . . .

 

[khdani]

create 3 hashtables, and iterate through them all...if you must use recursion, make some simple stop condition like n<=(length of string)^ 3.
though this algorithm is not effective, O(n^3)+Recurssion(n), but it will work

 

[transgalactic]

i am speach less using a tailor series in a solution O(n^3)+Recurssion(n)

thats heavy

 

[transgalactic]

i tried to build the method you told me to implement in the code
but i get out of bounds exception
i can't understant why
?

public class phone_book {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListMnemonics("4443220", "");
	}
	public static void ListMnemonics(String phoneNum, String mnem){
	    if(mnem.length() == phoneNum.length()){
	        //if we get here then we're on a leaf, just print the mnemonic and exit
	        System.out.println(mnem);
	        return;
	    }
	    /* implement GetLettersCorrespondingToNumber to return a string of letters that
	        correspond to a given telephone key */
	    String letters = GetLettersCorrespondingToNumber(phoneNum.charAt(mnem.length()));
	    for(int i=0; i<letters.length(); i++){
	 
	        ListMnemonics(phoneNum, mnem + letters.charAt(i));
	    }
	}
	 
	
	public static String GetLettersCorrespondingToNumber (int num){
		char [][]arr=new char[10][3];

		arr[0][0]='a';
		arr[0][1]='b';
		arr[0][2]='c';
		arr[1][0]='d';
		arr[1][1]='e';
		arr[1][2]='f';
		arr[2][0]='g';
		arr[2][1]='h';
		arr[2][2]='i';
		arr[3][0]='g';
		arr[3][1]='h';
		arr[3][2]='i';
		arr[4][0]='j';
		arr[4][1]='k';
		arr[4][2]='l';
		arr[5][0]='m';
		arr[5][1]='n';
		arr[5][2]='o';
		arr[6][0]='p';
		arr[6][1]='q';
		arr[6][2]='r';
		arr[7][0]='s';
		arr[7][1]='t';
		arr[7][2]='u';
		arr[8][0]='v';
		arr[8][1]='w';
		arr[8][2]='x';
		arr[9][0]='y';
		arr[9][1]='z';
		arr[9][2]='+';
		String str=new String(""+arr[num][0]+arr[num][1]+arr[num][2]);
		return str;
	}
	
}

 

[-Job-]

You're passing in a char to your implementation of GetLettersCorrespondingToNumber which expects an int. The result is that the char is being cast to int and you get the ASCII encoding value of the char (which will not be the same as its numeric value).

Use Character.digit(MyChar, 10) to convert a char to it's corresponding digit value.

 

[transgalactic]

about your code..

i got the idea that the mnem increases with the digits of the phone number
till its identical to it

the problem is that each recursive loop you put 3 letters in a variable "letters"

and in the end you pring the "mnem" which in fact id the original phone number

can you show me how this posibilty stuff works?

because as i see it
it just prints the original phone number
??

 

[Eus]

Hi Ho!

I think you can easily solve your problem if you imagine you have the following objects:
1. MarkedWheel
2. MarkedWheelsPermutationMachine

A marked wheel is a wheel that can be turned in only one direction.
Each turn will display one mark on its surface.

A permutation machine of marked wheels consists of one or more wheels.
The machine can be turned. In each turn of the machine, the wheel with index 0 will be turned once.
Once the wheel with index 0 has undergone a roll over, the wheel with the next higher index (i.e., 1) will turn once. And so on.

This way, you can easily generate the mnemonics.

I have attached the source code based on the above explanation in this post.


Eus

 

[-Job-]

Transgalactic, the code i posted works, I've tested it and it couldn't be simpler- there must be a problem with your implementation. If you don't understand how the code works then you must not be placing enough effort into trying to understand it because it's very explicit.