Computer Science Canada

Word scrambler
Author:  Insectoid [ Tue Oct 13, 2009 5:50 pm ]
Post subject:  Word scrambler
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 ( Cool ).

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?
Author:  Tony [ Tue Oct 13, 2009 6:02 pm ]
Post subject:  RE:Word scrambler
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.
Author:  Insectoid [ Tue Oct 13, 2009 6:28 pm ]
Post subject:  RE:Word scrambler
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.
Author:  Tony [ Tue Oct 13, 2009 6:45 pm ]
Post subject:  RE:Word scrambler
but you can easily implement a for-loop with recursion
Author:  andrew. [ Tue Oct 13, 2009 8:09 pm ]
Post subject:  RE:Word scrambler
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.
Author:  Tony [ Tue Oct 13, 2009 8:31 pm ]
Post subject:  Re: RE:Word scrambler
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.
Author:  Insectoid [ Tue Oct 13, 2009 9:01 pm ]
Post subject:  RE:Word scrambler
I don't know, logically, how to do this with recursion. I know how to do recursion, I just can't apply it here.
Author:  Tony [ Tue Oct 13, 2009 9:27 pm ]
Post subject:  RE:Word scrambler
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?
Author:  Prabhakar Ragde [ Wed Oct 14, 2009 7:34 am ]
Post subject:  RE:Word scrambler
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.
Author:  Insectoid [ Wed Oct 14, 2009 9:13 am ]
Post subject:  RE:Word scrambler
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)
   }
}
Author:  Tony [ Wed Oct 14, 2009 11:44 am ]
Post subject:  Re: RE:Word scrambler
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(''))
Author:  Insectoid [ Wed Oct 14, 2009 12:21 pm ]
Post subject:  RE:Word scrambler
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 Smile.


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
Author:  Prabhakar Ragde [ Wed Oct 14, 2009 1:24 pm ]
Post subject:  Re: RE:Word scrambler
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
Author:  Prabhakar Ragde [ Wed Oct 14, 2009 1:27 pm ]
Post subject:  Re: RE:Word scrambler
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]
Author:  Insectoid [ Wed Oct 14, 2009 2:49 pm ]
Post subject:  RE:Word scrambler
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.
Author:  Prabhakar Ragde [ Wed Oct 14, 2009 4:47 pm ]
Post subject:  RE:Word scrambler
A loop is just an optimized version of a very restricted form of recursion (which doesn't need to be optimized if the language properly supports recursion, hence the reason that loops are nonexistent or a minor add-on to modern functional languages).

More to the point, if you keep thinking in terms of loops, you will never get an elegant solution. You need to, first of all, forget about loops, and second of all, stop trying to visualize the whole process and then somehow make it recursive. It's as if, in writing a recursive factorial, you were to think, well, 5! is 1*2*3*4*5, so how can I get that pattern with a recursion? Forget it, your mind is just going to wander back towards loops. You'll end up with a bit of gratuitous recursion plastered onto a loopy solution.

Instead: 5! is 5 times 4!. (n-1)! is only a slightly smaller problem than n! but you can assume your recursion computes that, and then you just have to figure out how to get n! from it. That gives you n! = n*(n-1)! and 0! = 1, which, in fact, is the best definition of factorial there is (no need for saying 1*2*3...*n or anything vague like that).

Which is why I gave you the hint I did.
Author:  Insectoid [ Mon Oct 19, 2009 1:41 pm ]
Post subject:  Re: Word scrambler
I've thought this out a bit, and came up with a function. However, it doesn't work. I tried tracing it, but it branches out so far that I keep getting lost. Any pointers in the right direction would be nice.

code:

public function scramble (word:String):String{

                        if (word.length == 1){
                                //trace (1)
                                return word;
                        }
                        else {
                                for (var x = 0; x < word.length; x++){
                                        //trace (word.slice (x, x+1))
                                        var firstPart = word.substr (x, 1)
                                        //trace (firstPart);
                                        var middlePart =  (word.substring (0, x-1))
                                        var lastPart = word.substring (x+1, word.length)
                                        var final = firstPart.concat (scramble (middlePart.concat (lastPart)));
                                        //var bleh = word.substr(x, 1)+scramble (word.substring (0,x-1).concat(word.substring (x+1,word.length)))+"\n";
                                       
                                        output.appendText (final+"\n");
                                }
                                return final;
                        }
                }
Author:  Insectoid [ Mon Oct 19, 2009 5:22 pm ]
Post subject:  Re: Word scrambler
I have converted Tony's code to Actionscript and now have this:

code:

public function scramble (to_scramble:String, scrambled:String):array{
    if (to_scramble.length == 0) {
        return scrambled;
   }
   var scrambledArray = scrambled.split;
   var to_scrambleArray = to_scramble.split;
   for each (var i:String in to_scrambleArray){
             scrambledArray.push(i);
             scramble (String (to_scrambleArray - [i]), String (scrambledArray))
             scrambledArray.pop
        }
}

Yes, this is a copy of Tony's code. However, I am using it only to review and decipher how it works. If worst comes to worse, I will use (parts of) this code, though I'd rather use my own. As I don't have a copy of Flash, I don't know if all my syntax is correct. But whatever. I think this would be much more elegant if I just had arrays as parameters...

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy