Computer Science Canada recursion |
| Author: | Tubs [ Mon Nov 28, 2005 8:40 pm ] |
| Post subject: | recursion |
I don't understand quite how to approach this problem, any tips for getting started? Using recursion, determine all two-letter subsets of a given string of characters. ex. {abcd} would have the subsets of: {ab} {ac} {ad} {bc} {bd} {cd} |
|
| Author: | 1of42 [ Mon Nov 28, 2005 10:18 pm ] |
| Post subject: | |
Well, with recursion, dunno, but here's an answer for the NUMBER of subsets  (this assumes that order of characters doesnt matter):
(length(string)!)/((length(string)-2)!2!) 
And then, define ! (factorial) recursively, and loop thru all the letters of the string, making the necessary combinations 
And there you are, you've determined them all (and the number of them), and used a bit of recursion |
|
| Author: | bugzpodder [ Mon Nov 28, 2005 10:30 pm ] |
| Post subject: | |
i dont see what number of subsets have to do with anything. for recursion: pick the first alphabet, say 'c' call ur recursive function with the smaller alphabet set (make sure you remove all the alphabet before the one you picked as well) so in this case you call ur recursive function with {d} by removing a,b,c |
|
| Author: | 1of42 [ Mon Nov 28, 2005 10:32 pm ] |
| Post subject: | |
bugzpodder wrote: i dont see what number of subsets have to do with anything.
for recursion: pick the first alphabet, say 'c' call ur recursive function with the smaller alphabet set (make sure you remove all the alphabet before the one you picked as well) so in this case you call ur recursive function with {d} by removing a,b,c well, they don't have anything to do with anything, btu you use ! to find them, and therefore can define ! recursively, thereby satisfying the recursive usage requriement, and then solve the rest of the problem iteratively  |
|
| Author: | Hikaru79 [ Mon Nov 28, 2005 10:38 pm ] |
| Post subject: | |
1of42 wrote: bugzpodder wrote: i dont see what number of subsets have to do with anything.
for recursion: pick the first alphabet, say 'c' call ur recursive function with the smaller alphabet set (make sure you remove all the alphabet before the one you picked as well) so in this case you call ur recursive function with {d} by removing a,b,c well, they don't have anything to do with anything, btu you use ! to find them, and therefore can define ! recursively, thereby satisfying the recursive usage requriement, and then solve the rest of the problem iteratively Why would you go out of your way to sneak past a requirement that is in there to help you in the first place? |
|
| Author: | Tubs [ Tue Nov 29, 2005 10:09 am ] |
| Post subject: | |
I'm doing this in C btw, sorry about that. |
|
| Author: | MysticVegeta [ Wed Nov 30, 2005 3:05 pm ] |
| Post subject: | |
Well if you need the concept understanding of the permutations possible. There is an excellent example by zylum in his recursion tutorial post in the turing tutorials. All you have to do is convert the code in C..  |
|
| Author: | Tubs [ Wed Nov 30, 2005 3:41 pm ] |
| Post subject: | |
Ya, I figured it out. Thanks |
|