# jumbling a word without recursion

This topic is 3739 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.

##### Share on other sites
1. Generate permutation vector:
The first permutation vector you have is [1 2 3] // no permutation
The second will be [1 3 2] ...
the algorithm is basically have the first vector and swap the last two members
generate a new vector and generate a new swap order.

I did this with recursion, but it is possible to do without it.

2. apply the permutation vector to your word vector
V[:, p];

search for permutation vector in Mathworks or other MatLab document

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

Correct, and that is exactly what Collections.shuffle does. Now if you replace that randomness with a deterministic parameter, you can produce all possible permutations. This is what I came up with:

public class Jumbling{	public static void main(String[] args)	{		jumble("abcd");	}	public static void jumble(String word)	{		final int len = word.length();		if (len > 12) throw new IllegalArgumentException(word);		final char[] src = word.toCharArray();		final char[] dst = new char[len];		int factorial = 1;		for (int i = 2; i <= len; ++i)			factorial *= i;		for (int i = 0; i < factorial; ++i)		{			jumble(src, dst, i);			System.out.println(dst);		}	}	private static void jumble(char[] src, char[] dst, int permutation)	{		System.arraycopy(src, 0, dst, 0, src.length);		for (int i = 0, n = src.length; n > 1; ++i, --n)		{			final int k = permutation % n + i;			permutation /= n;			final char c = dst;			dst = dst[k];			dst[k] = c;		}	}}

This program generates the desired output (albeit in a different order):

abcdbacdcbaddbcaacbdbcadcabddcbaadcbbdcacdabdacbabdcbadccbdadbacacdbbcdacadbdcabadbcbdaccdbadabc

##### Share on other sites
What do you need this for? You may be able to write your algorithm so you give it a string and an input value of the variation you want of the string and it will give you the scrambled string corresponding to the number you give it by only calculating the one you requested.