Sign in to follow this  
LilithAnn

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by LilithAnn
Specific 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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this