# Help with string permutations

## Recommended Posts

I'm thinking of writing a game based on Jumble, the one where you unscramble the letters to form the right word. But I need to be able to generate jumbles from a given word in order to build a list for the game. Although I know that the number of results can be large depending on the number of letters in the word, I still would prefer to scan a list of all jumbled permutations of the letters to find some something that is sufficiently different in appearance from the original to make it somewhat difficult. I've approached it through nested loops but those typically require a specific number of characters. I've tried recursion but my head just about exploded trying to keep track of what was happening with local copies of the mutated strings. Does anyone have a viable algorithm for something like this? Specific code? TIA, Lilith

##### Share on other sites
Recursive solution, pseudocode:

// Recursively  // if no elements left: use the permutation  // else for each element left    // append to string    // perform recursive call

Practical version, C++ (untested, but the algorithm is there).

template<typename Callback, typename It> all_permutations(It first, It last, Callback c) {  // if no elements left: use the permutation  if (first == last) c();   // else for each element left  else for( It i = first; i < last; ++i ) {      // append to string    swap(*i,*first);    // perform recursive call    all_permutations(first + 1, last, c);    // clean up    swap(*i,*first);  }}

Replace the for-loop by a random choice, and you can then apply tail-recursion if modifying the string isn't a problem.

##### Share on other sites
I don't have any code, but here's my suggestion:

Using an algorithm where each letter is radomly chosen from a stack of available letters (reducing the size of the stack each time), generate the new scrambled word. Then compare the new position of each letter to the old position, giving you a difference value.

After the stack has been exhausted, if the sum of the differences is greater than a certain threshold (based on the size of the word), use it. If not, repeat the process. The higher the threshold, the more scrambled the resulting word is likely to be, but it will take longer to find one that meets the threshold.

To prevent any chance of an infinate loop, keep track of the word with the largest difference that did not pass the threshold, and if after x number of iterations nothing better has surfaced, use that variation.

This is certainly not the best possible way of doing this, but it's pretty simple and if all you need is to jumble words for a word game, it will probably suffice.

##### Share on other sites
Quote:
 Original post by LilithAnnSpecific code?

If you are using C++, <algorithm> includes a std::next_permutation function that will directly work on a std::string object (and char* arrays as well). Together with std::sort, it does all the work for you.

#include <algorithm>#include <string>#include <iostream>int main(){    std::string jumble = "jumble";    std::sort(jumble.begin(), jumble.end());    bool not_done = true;    while(not_done)    {        std::cout << jumble << std::endl;        not_done = std::next_permutation(jumble.begin(), jumble.end());    }}

Of course, a much simpler approach to generating a jumbled word would be to simply use std::random_shuffle(jumble.begin(), jumble.end());, which will randomize the contents of jumble.

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627655
• Total Posts
2978460

• 10
• 12
• 22
• 13
• 33