Jump to content
  • Advertisement
Sign in to follow this  
rameshch45

jumbling a word without recursion

This topic is 3916 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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


Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!