Saturday, November 18, 2006

A simple algorithm

After Lipis's comment on my previous post about the words with shuffled letters, I thought it might be nice to post a simple algorithm for that.

The C# method below takes as argument a string and returns a string that contains the same letters but only the first and the last are guaranteed to be at the right position.

private string shuffle(string word)
Random rnd = new Random();
int index;
string temp = "";

int loop = word.Length - 1;

//loop the word without the first and last letters.
for (int i = 1; i < loop; i++)
//get an int from 1..word.Length-1.
index = rnd.Next(1,word.Length-1);

//add the char at this index to the temp.
temp = temp + word[index];

//delete the char at this index from word.
word = word.Remove(index, 1);

return word[0] + temp + word[word.Length-1];

With the definition I gave, this method is almost correct.
There are some known bugs but I didn't want to make the code difficult to grasp.
Now that the code is easy to understand, I can talk about the bugs and the solutions.

1. If the word is only a letter (such as 'a'), the method returns this letter twice.
The solution is to check the length of the word given. So after initializing loop variable, write:
if (loop == 0) return word;

2. There is a possibility that the word returned is the same with the one given.
As the length of the word increases, this possibility becomes smaller. But for 4-letter words, it's 50%. What one could do, is to check if the word about to return, is the same with the one provided, and loop until they are different.


vpapanik said...


if Length(word) < 4 then
Result := word;

(afti tin C pote mou den tin xwnepsa...) ;) ;)

Stavros said...

Nai.. Kai etsi ginetai..

Gia tis glwsses, it's a matter of taste :)
Eidika gia programmatakia autou tou styl..