-----------------------------------

Tubs

Mon Nov 28, 2005 8:40 pm


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}


-----------------------------------

1of42

Mon Nov 28, 2005 10:18 pm



-----------------------------------

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!)

:P

And then, define ! (factorial) recursively, and loop thru all the letters of the string, making the necessary combinations :D

And there you are, you've determined them all (and the number of them), and used a bit of recursion :D:D


-----------------------------------

bugzpodder

Mon Nov 28, 2005 10:30 pm



-----------------------------------

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


-----------------------------------

1of42

Mon Nov 28, 2005 10:32 pm



-----------------------------------

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 :D


-----------------------------------

Hikaru79

Mon Nov 28, 2005 10:38 pm



-----------------------------------

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 :D
Why would you go out of your way to sneak past a requirement that is in there to help you in the first place? :P


-----------------------------------

Tubs

Tue Nov 29, 2005 10:09 am



-----------------------------------

I'm doing this in C btw, sorry about that.


-----------------------------------

MysticVegeta

Wed Nov 30, 2005 3:05 pm



-----------------------------------

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..  :)


-----------------------------------

Tubs

Wed Nov 30, 2005 3:41 pm



-----------------------------------

Ya, I figured it out. Thanks  :)