jumbling a word without recursion
Author
I am writing a Java game and looking for how to jumbling a word without recursion. Any hints? The word is of length like 15 characters and recursion is killing... as you know.
Author
Oh sorry.... its just about possibilities...
abcd will have the following:
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
abcd will have the following:
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
There are 1 307 674 368 000 possible permutations of a 15-letter word. Recursion or not, you're in there for a long, long time. May I suggest looking for an algorithmic optimization instead?
Quote:Original post by jbadams
Pick a single letter.
Remove the letter from your word.
Place the letter at a randomly chosen location within the word.
Rinse and repeat. More repetition will generally produce a more "jumbled" looking output.
If you want to produce all the possibilities and not just a random one you'll need a different method.
IIRC, if you go through all letters in order, and swap this letter with a random one of the next letters, you get a scrambled word where the chance to get any random permutation is uniform. And it's O(n).
Quote:Original post by jbadams
Pick a single letter.
Remove the letter from your word.
Place the letter at a randomly chosen location within the word.
I would suggest a variant for obtaining a random permutation:
for i = 0 to l-2 swap string and string[random(i+1,l-1)]Where l is the length of the string and random(a,b) returns a random number between a and b inclusive.
This has the advantage of producing an uniform distribution.
Damnit, accidentally deleted my post whilst making an edit. You can see my entire reply in Lode's quote however. Nice suggestions, hopefully we've given rameshch45 something to work with.
Author
Thanks, these ones point at generating a scrambled word but I was wanting all possibilities. I can see your point. Even 8! runs into some 40320. I will give-up the approach and think of something else. But by the way, if I were to generate all possibilities of say, a 4 letter word without recursion, can someone throw in some pseudo-code or an approach.
In general, recursive algorithms can be implemented using a loop and a data structure (stack or queue, depending on the algorithm) to save the state of each iteration. In fact that's essentially what recursion does under the hood, it uses the call stack to save state for each recursive function call.
The roll-your-own loop/stack approach also has the added benefit of avoiding stack overflows, and you are only limited by the total memory in your machine.
The roll-your-own loop/stack approach also has the added benefit of avoiding stack overflows, and you are only limited by the total memory in your machine.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
