Word scrambler

[Insectoid]

Well, as my CS class turned out to be an online course- in the classroom, I have decided to try to complete the entire grade 12 CS curriculum by the end of November. Then do it again in a different (more useful) language. I hit a snag in the recursion unit though;

I'm supposed to make a program that takes in a word/letters/numbers and scrambles the letters into every possible combination. And it has to be done recursively. I have though of several ways to do this, but all are rather complicated and inefficient.

perhaps it could be done like a reverse-sort...sort of ( ).

Anyone have an idea of the logic involved?

Oh, and is there a way to count recursion stack depth in Actionscript without a manual counter?

[Tony]

read zylum's excellent write up on recursion.

It might be a difficult concept (unless you come from functional languages), but it's something that will get you through a lot of CS at University level. It's worth it to understand the concept well.

[Insectoid]

Oh, I understand recursion, just, not how to use it with this word scrambler. Makes more sense to me to use a for loop. But I have to use recursion.

[Tony]

but you can easily implement a for-loop with recursion

[andrew.]

But then it's not really recursion, it's just going in a loop. Isn't the point of recursion to kind of get the answer by repeating tasks (if you know what I mean)? e.g. return fibonacci (n-1) + fibonacci (n-2) is a recursive function but calling a method in a loop isn't really how a recursive function is supposed to be used, right? It just doesn't make sense to me to do something like this recursively.

[Tony]

andrew. @ Tue Oct 13, 2009 8:09 pm wrote:

It just doesn't make sense to me to do something like this recursively.

Are you talking about using recursion for loops? (functional programming languages don't have loops) or this particular problem?

In the latter case, recursion does make sense. Recursion is not about repeating tasks, it's about continuously solving a little part of the problem to get closer to a really trivial problem that you know how to solve. Kind of like Induction, but in reverse.

In this case, we can scramble 1 letter, and then we'll have only n-1 letters left. Eventually we'll get down to a word of length 1, at which point it's trivial to scramble it -- it's just itself.

[Insectoid]

I don't know, logically, how to do this with recursion. I know how to do recursion, I just can't apply it here.

[Tony]

If you have a string "abcd" and you need to come up with all possible permutations of letters, can you think of a way to come up with all possibilities for just the first letter; and then what string of length (4 - 1) = 3 would be left?

[Prabhakar Ragde]

That's not the way to think of it, Tony. Recursion doesn't solve a small piece of the problem until only a small piece is left. It solves a big piece of the problem recursively, and then you have a small piece left to solve afterwards.

In the case of permuting the string "abcd", the recursive call permutes "bcd". Given the answer to that big piece of the problem, how would you complete the answer to the full problem by adding in the "a"?

The recursive solution is easier to derive and explain than one that does not use recursion.

[Insectoid]

So, I've decided on a way to do this, now I just need to make it recurse. Anyway, here's how it's going to work.

Similar to binary counting, it will swap the last 2 characters, then the 2nd last and 3rd from last, then the last 2 again, and so on.

ie

abcd
abdc
adbc
adcb
acdb
acbd
cadc
cacd
etc

I just need a way to record what letters to swap.

I suppose I need a function that takes in a string and a number x which is initially equal to length of string, and then swap string [x] and string [x-1] and somehow decide what x will be for the next iteration.

code:

function switch (word:String, x:int):string     if x = 1 then         return cancel     else         //swap word[x]and word[x+1]        //do something to x        //return switch (word, x)    } }

[Tony]

Prabhakar Ragde @ Wed Oct 14, 2009 7:34 am wrote:

In the case of permuting the string "abcd", the recursive call permutes "bcd". Given the answer to that big piece of the problem, how would you complete the answer to the full problem by adding in the "a"?

Is this a question addressed to me or insectoid? If "a" is scrambled and "bcd" is scrambled, then you just add the two for full scrambling...

Spoiler:

def scramble(to_scramble = [], scrambled = []) puts scrambled.to_s and return if to_scramble.empty? to_scramble.each do |i| scrambled.push(i) scramble(to_scramble - [i], scrambled) scrambled.pop end end scramble("abcd".split(''))

[Insectoid]

Hmm. Your solution no doubt works, but I have devised my own solution that is far more complicated and ridiculous than yours, however I always try to use my own solution over someone else's such that I may learn.

Anyway, I have discovered a couple new things. The pattern I posted before is very much like a nested for loop! The complicated part is that the number of nests is equal to the length of the string - 2, and the number of times each for loop iterates is relevant to the factorial of the depth of that nest. So for a 4-letter word, there would be 2 nests (three for loops), the higest being 3 iterations, the next 2 iterations, the next just a single iteration. Here is where I have found Recursion not only a viable solution, but almost necessary.

A for loop can be called by a function which recurses. The length of that for loop is equal to the factorial of the depth of the recurse. The recurse ends when the length of the for loop is 1.

I may not have explained that well, but I'm trying. This is all very complicated (for me at least) but the most important number I think will be the depth of the recurse. Of course this means I will have to find or create a factorial function as well (though I already did that for a previous assignment).

I'm writing this as much to organize my conclusions for myself as for you guys to speculate on, criticize and find fault with.

Oh, and Tony, Can you not write the solutions in Ruby? I intend to do every assignment twice; once in Actionscript and once in Ruby. Don't want the answers given to me .


OT, sort of (but it's my thread, so I'm allowed);

This is going to drive me insane. Haven't had a question like this in a while. Excellent that it is a class assignment. I think instead of dozens of mindless 1-trick problems, CS classes should spend a week or so on one really hard one. CS should make the students think. Really think. Those simple questions that most grade 12 students get are suitable for grade 10/11. By grade 12, actually solving a problem perfectly should be astounding. Maybe I'm dreaming (and maybe so many people would do poorly that nobody would sign up for it) but hell, why not dream once in a while. It would definitely reduce the number of easy 95%'s people go home with in this class (which would be bad for me as I rely on my CS mark to keep my average up). Anyway, the point is, every question you get in grade 12 CS should be like a contest question. I don't like wasting semesters doing the same stuff in a different language. And I like this question. Shpeel over.

~Insectoid

[Prabhakar Ragde]

Tony @ Wed Oct 14, 2009 11:44 am wrote:

Is this a question addressed to me or insectoid?

To both of you, and neither of you answered it. Tony, your code still uses a loop, as far as I can tell (I really should read that book on Ruby sitting on my shelf). You can do it entirely without for loops. --PR

[Prabhakar Ragde]

Tony @ Wed Oct 14, 2009 11:44 am wrote:

If "a" is scrambled and "bcd" is scrambled, then you just add the two for full scrambling...

No, "a" is not scrambled, it's just the first character of "abcd". I suppose I should have said 'a'. --PR

[Edit: typo]

[Insectoid]

Prabhakar, Tony's code does use a loop. Nowhere have I said loops for not be used. Recursion however MUST be used. Sure, I have no doubt it can be done without loops at all, but the solution I have devised uses loops. However inefficient it is, it works.

here's a 'static' example that only works with 4-letter words;

code:

var word: String for x: 1..3{     word.swap (0,1);     for y: 1..2{         word.swap (1, 2);         for z: 1..1{              word.swap(2, 3);         }     } }

I think I might have to put the swaps at the bottom of the loop....
I also don't have the resources at the moment to test this, so there may be small flaws.

I need to change this to accept any size of word, hence a for loop called by a function. I could have the function call itself and thus the loop any number of times.