Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dificult recurtion question

  1. Mar 20, 2008 #1
    i have tried the medium part
    but i couldnt 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
    Code (Text):


    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);
               
                   
               
            }
        }
     
    }
     
     
  2. jcsd
  3. Mar 21, 2008 #2

    -Job-

    User Avatar
    Science Advisor

    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:
    Code (Text):

    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", "");
     
     
  4. Mar 21, 2008 #3
    there is no binary tree here

    i am realy having a hard time to understand what are you doing
    can make an example please
     
    Last edited: Mar 21, 2008
  5. Mar 21, 2008 #4

    -Job-

    User Avatar
    Science Advisor

    That is an example, i'm afraid i can't make it any simpler. What are you having trouble understanding specifically?
     
  6. Mar 21, 2008 #5
    i am having trouble to understand
    where is the termins of a binary tree
    left right data node
    i cant see any code related to it
    where are you using it?
     
  7. Mar 21, 2008 #6

    -Job-

    User Avatar
    Science Advisor

    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.
     
  8. Mar 22, 2008 #7
    what "mnem" string represents??
    i cant see here the dictionery where
    for example for 1 we have a, b, c
    2 d e f
    . . . .
     
  9. Mar 22, 2008 #8
    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
     
  10. Mar 23, 2008 #9
    i am speach less using a tailor series in a solution O(n^3)+Recurssion(n)

    thats heavy
     
  11. Mar 24, 2008 #10
    i tried to build the method you told me to implement in the code
    but i get out of bounds exception
    i cant understant why
    ???

    Code (Text):


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

     
     
  12. Mar 24, 2008 #11

    -Job-

    User Avatar
    Science Advisor

    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.
     
  13. Mar 25, 2008 #12
    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
    ??
     
  14. Mar 25, 2008 #13

    Eus

    User Avatar

    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.

    Best regards,
    Eus
     

    Attached Files:

  15. Mar 26, 2008 #14

    -Job-

    User Avatar
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Dificult recurtion question
  1. Fortran Question (Replies: 32)

  2. Randomization Question (Replies: 4)

Loading...