should I use recursion?
This is a homework assignment for a first semester CS class, so I don't want to be spoon-fed an answer, but at least maybe pointed in the right direction.
The first part of the assignment asked us to write a function or functions that take as input a 4 digit phone number, and then displays all the possible letter combinations of on those buttons on the phone.
so, if you input 2345 you get:
ADGJ ADGK ADGL
ADHJ ADHK ADHL
ADIJ ADIK ADIL
AEGJ AEGK AEGL
etc etc etc.
Here's how I solved this part. I looped through the input string, and sent each individual char to a function that returned a string of those possible letters. So after that I have 4 strings:
word1 = "ABC"
word2 = "DEF"
word3 = "GHI"
word4 = "JKL"
Then I created 4 nested for loops to scroll through and print out all the combinations, like so:
I'm still too new to know if it's an elegant solution or a kludge, but it works.
The 'challenge' part of the assignment is to make this work for any arbitrary number of digits. Now I see that my solution is far to rigid to accomplish this, so I've scoured the text and web looking for a possible solution. It seems that I will need to use a recursive function(I think). All the examples I've looked at are pretty simple like doing factorials, where once the function reaches the base case and starts to return, it simply multiplies the base by the new value and keeps going.Too simple to be of use to me.
I realize I won't be able to use my vars word1,word2, etc, because I won't know at compile time how many digits there will be. I'm guessing I will have to create one string with all the letters like "ABCDEFGHIJKL" and then use some sort of a counter so that the function knows where one "phone button" stops and the next one starts.A problem with that is that the buttons 7 and 9 have 4 chars instead of 3.
Can someone maybe give me a place to start? Sorry if I'm too verbose, this is my first post and I wanted it clear that I've spent hours on this problem by myself before reaching out for some help.
Gary
The first part of the assignment asked us to write a function or functions that take as input a 4 digit phone number, and then displays all the possible letter combinations of on those buttons on the phone.
so, if you input 2345 you get:
ADGJ ADGK ADGL
ADHJ ADHK ADHL
ADIJ ADIK ADIL
AEGJ AEGK AEGL
etc etc etc.
Here's how I solved this part. I looped through the input string, and sent each individual char to a function that returned a string of those possible letters. So after that I have 4 strings:
word1 = "ABC"
word2 = "DEF"
word3 = "GHI"
word4 = "JKL"
Then I created 4 nested for loops to scroll through and print out all the combinations, like so:
|
|
I'm still too new to know if it's an elegant solution or a kludge, but it works.
The 'challenge' part of the assignment is to make this work for any arbitrary number of digits. Now I see that my solution is far to rigid to accomplish this, so I've scoured the text and web looking for a possible solution. It seems that I will need to use a recursive function(I think). All the examples I've looked at are pretty simple like doing factorials, where once the function reaches the base case and starts to return, it simply multiplies the base by the new value and keeps going.Too simple to be of use to me.
I realize I won't be able to use my vars word1,word2, etc, because I won't know at compile time how many digits there will be. I'm guessing I will have to create one string with all the letters like "ABCDEFGHIJKL" and then use some sort of a counter so that the function knows where one "phone button" stops and the next one starts.A problem with that is that the buttons 7 and 9 have 4 chars instead of 3.
Can someone maybe give me a place to start? Sorry if I'm too verbose, this is my first post and I wanted it clear that I've spent hours on this problem by myself before reaching out for some help.
Gary
If you can get the actual number of digits, use a word[][] table.
Instead of word1[count1] use word[num][count1]with num=0,1,2,etc.
You figure the rest.
Hope this helps
Instead of word1[count1] use word[num][count1]with num=0,1,2,etc.
You figure the rest.
Hope this helps
I must say that you have done far more analysis of your homework than most posters do, and you show an inherent understanding of programming.
I think you are on the right track with a recursive solution. Although it is possible to rewrite any recursive algorithm to be non-recursive, probably a recursive solution to this problem is best and simplest.
Let me give you a hint on how I would proceed here. Suppose I have the input "12345".
Suppose I split the input into 2 strings: "ABC" and "2345". Now I call a function three times, once with the parameters "A", "2345", once with "B", "2345", and once with "C", "2345". Now if this function were to output its first parameter (ie, "A", "B", or "C") and then call itself with "DEF", "345" (ie, do the same thing again)...
This should give you a start. Note that you will need more parameters than I mentioned above.
I think you are on the right track with a recursive solution. Although it is possible to rewrite any recursive algorithm to be non-recursive, probably a recursive solution to this problem is best and simplest.
Let me give you a hint on how I would proceed here. Suppose I have the input "12345".
Suppose I split the input into 2 strings: "ABC" and "2345". Now I call a function three times, once with the parameters "A", "2345", once with "B", "2345", and once with "C", "2345". Now if this function were to output its first parameter (ie, "A", "B", or "C") and then call itself with "DEF", "345" (ie, do the same thing again)...
This should give you a start. Note that you will need more parameters than I mentioned above.
an alternative approach is to take a look at STL. There is an algorithm for permutations, that way you would not need a recursive algorithm.
google on "next_permutation"
google on "next_permutation"
I've spent the last couple of hours studying this great description
http://marknelson.us/2002/03/01/next-permutation
of doing permutations both with recursion and with the next_permutation function. I'm starting to understand how those work, but the problem is that I have what is essentially a two dimensional structure of an unknown size to permute, rather than a simple list of numbers or chars.
http://marknelson.us/2002/03/01/next-permutation
of doing permutations both with recursion and with the next_permutation function. I'm starting to understand how those work, but the problem is that I have what is essentially a two dimensional structure of an unknown size to permute, rather than a simple list of numbers or chars.
Last edited on
Yes, which is why next_permutation won't help you. Have you considered the hint I gave you above?
Yes, I have.
What's hardest for me is thinking 'backwards', which recursion seems to require.
Let me see if I'm getting this
my function takes two arguments, the 'converted' string, and the rest of the unconverted part. So the first time I call it, I send it
myfun("",inputstring) //inputstring="12345"
the function then converts the first digit of the inputstring, then removes the digit. //so now I have ("ABC","2345")
then,
for (count = 0 to convertedstring.length())
calls itself with
myfun(convertedstring[count],inputstring)
// convertedstring[count] is "A", inputstring is 2345
what is bothering me is that now, when it calls itself with ("B",2345") for example, the first part of the function, where it converts a digit and then removes it, would run again. I don't really want that, right? I don't want that to happen until "A","B",and"C" are completed.
What's hardest for me is thinking 'backwards', which recursion seems to require.
Let me see if I'm getting this
my function takes two arguments, the 'converted' string, and the rest of the unconverted part. So the first time I call it, I send it
myfun("",inputstring) //inputstring="12345"
the function then converts the first digit of the inputstring, then removes the digit. //so now I have ("ABC","2345")
then,
for (count = 0 to convertedstring.length())
calls itself with
myfun(convertedstring[count],inputstring)
// convertedstring[count] is "A", inputstring is 2345
what is bothering me is that now, when it calls itself with ("B",2345") for example, the first part of the function, where it converts a digit and then removes it, would run again. I don't really want that, right? I don't want that to happen until "A","B",and"C" are completed.
Last edited on
If I understand you correctly, I think you are thinking of a breadth-first approach whereas I am thinking of a depth-first approach. The only difference will be the order in which the permutations are generated.
You might also be concerned about removing a digit before all of its possible letter values have been explored. This won't be a problem because you'll be passing copies of the strings around so that each invocation of the recursive function modifies its local copy only.
Try implementing the algorithm you mentioned above. It won't quite suffice your needs as is, but it is close. Have your function output convertedstring and inputstring on each invocation and observe the output. That might help you visualize it better.
You might also be concerned about removing a digit before all of its possible letter values have been explored. This won't be a problem because you'll be passing copies of the strings around so that each invocation of the recursive function modifies its local copy only.
Try implementing the algorithm you mentioned above. It won't quite suffice your needs as is, but it is close. Have your function output convertedstring and inputstring on each invocation and observe the output. That might help you visualize it better.
Topic archived. No new replies allowed.