# jumbling a word without recursion

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

## 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 on other sites
What does "jumbling" mean? Can you give an example?

##### Share on other sites
Oh sorry.... its just about possibilities...

abcd will have the following:

abcd
abdc
acbd
acdb
bacd
bcda
bdac
bdca
cabd
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

##### 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 on other sites
Wait, are you looking for a single jumble or for all possible jumbles?

##### Share on other sites
Quote:
 Original post by jbadamsPick 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 on other sites
Quote:
 Original post by jbadamsPick 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 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 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 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.

1. 1
Rutin
31
2. 2
3. 3
4. 4
5. 5

• 13
• 54
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632967
• Total Posts
3009554
• ### Who's Online (See full list)

There are no registered users currently online

×