Fisher-Yates shuffle on a single string vs. using an equal length permutation?

Question

Right now I am working on a suite of word games as a means of teaching myself (and recreating some of my favorite word games!) With the help of an 'actual' studied programming friend, we have implemented a nice permutation method in one of my classes. It is finding all permutations from 3 letters and up and comparing them to Lists of strings I have containing what is essentially the Scrabble tournament word list.

That's the background, here is my current issue: I now have all of the permutations and have compared them to existing words and created a new List with all possible words combinations in a given string. However, when I present this string to the user, I need it to be scrambled. I found a few C# implementations of the Fisher-Yates shuffle but I was unsuccessful in adapting them to accept a single string (EDIT: Fisher-Yates issue solved with a char[] array). Then I had an idea for a little bit of a hack - why not use one of the permutations that is of the same length but is != the original word.

Unfortunately, every time my conditional statement returns the word backwards. Not that hard for the end user to figure out :) Here is my code for scrambling:

// permWords is a Dictionary<int, List<string>>
String strScrambled= "";

        foreach (List<string> listWords in permWords.Values)
        {
            foreach (string word in listWords)
            {
                if (word.Length == strWord.Length && word != strWord)
                {
                    strScrambled = word;
                }

            }
        }

I have tried strScrambled = word + 1 assuming that the first permutation inequal to the original was the word backwards. However, I don't think that really "works" in this context; especially considering it still returns the same backwards word.

There has been a very useful answer given for how to fix my issue with Fisher-Yates using a char array, but I'm still quite curious to know how it might be best to use something like what I've posted, only finding a way to ensure that the answer is not simply the word spelled backwards. I'm intrigued by this method because the list of permutations already exists; I would like to tap into it as my solution.

possible duplicate of [Shuffle string c#](http://stackoverflow.com/questions/4739903/shuffle-string-c-sharp) — mbeckish, Nov 28 '12 at 14:09
Why don't you convert the string to char[] using st.ToCharArray(), shuffle it anyway you like, and then convert back to string using arr.ToString()? — Ali Ferhat, Nov 28 '12 at 14:13
`Random r = new Random(); var shuffled = String.Join("","abcdefgh".OrderBy(_=>r.Next()));` — L.B, Nov 28 '12 at 14:26
Ahh, a character array! That's a great idea. Write that out as an answer and I can give you credit, @AliFerhat. — armadadrive, Nov 28 '12 at 14:30
@mbeckish Possibly, if that post contains information on working with a List of permutations of a string. I'm not trying to be flippant, but I have clearly outlined two scenarios I'm investigating to try and solve my problem and I would like to solicit the best advice I can to learn and move forward. — armadadrive, Nov 28 '12 at 14:32
@armadadrive - Only one of your outlined scenarios requires working with a list of permutations. The first solution just requires you to shuffle one string at a time, right? — mbeckish, Nov 28 '12 at 15:41
@mbeckish One of two ways to do it, that I've outlined, is to shuffle a string. I'm not interested in arguing about the merit of the question though; I am now interested in finding out how to best solve my issue with the permutations List because some helpful advice has also been given with the issue I was having regarding a String shuffle. — armadadrive, Nov 28 '12 at 15:58

score 3 · Accepted Answer · answered Nov 28 '12 at 14:50

3

I suppose you already have a method that does the shuffling :

void FisherYatesShuffle(char[] elements)
{
    int N = elements.Count;
    for(int i = 0; i<N-1; i++)
    {
        // exchange elements[i] with a random element in i+1 .. N
    }   
}

All you need to do it convert your string to CharArray and than convert the result back to string:

string shuffle(string input)
{
    var arr = input.ToCharArray();
    FisherYatesShuffle(arr);
    return new String(arr);
}

answered Nov 28 '12 at 14:50

Ali Ferhat

2,511
17
24

Thanks. Let me know if you have any thoughts on the best way to grab one of my random permutations as an alternative solution. As I mentioned in the post, the first condition that always seems to evaluate true is the permutation where the string is backwards. I feel like this could also be a useful way to 'scramble' because all the permutations already exist in a `List`. – armadadrive Nov 28 '12 at 15:51

score 1 · Answer 2 · answered Nov 28 '12 at 14:33

1

See if this will work for you...

string str = "hello";

// The random number sequence
Random num = new Random();

string rand = str;
while (rand == str)
    rand = new string(str.OrderBy(s => (num.Next())).ToArray());

If you want to make sure the shuffled value is not the exact reverse you could change the while condition to be ...

while (rand == str || rand == str.Reverse())

answered Nov 28 '12 at 14:33

Gene S

2,735
3
25
35

Thank you, this works perfectly. All I have to do is assign the rand value to strScrambled. – armadadrive Nov 28 '12 at 14:48
The OP starts out attempting to use an efficient and effective shuffling algorithm, and you instead use a less effective and less efficient alternative? – Servy Nov 28 '12 at 15:11
Sorting is usually less efficient than generating a random permutation. – Ali Ferhat Nov 28 '12 at 15:29
@Servy While what you say is true he did indicate in his question that "Any suggestion would be a help". I was just trying to suggest an alternative that will do what he asked. I did not get from his question that using Fisher-Yates was a requirement, just that that was the approach he was trying. – Gene S Nov 28 '12 at 16:14
@GeneS It's taking a step backwards. It's using a less effective higher level approach rather than addressing whatever problem he had in the correct approach. Incidentally the problem with his approach is likely that he needed to convert the string to a char array, shuffle it, and then convert it back to a string. You did all that, you just didn't explain that *that's* what you fixed. You could have done that without reverting to a poorer shuffling method and it would be a great answer. – Servy Nov 28 '12 at 16:22
1

While the answer isn't as good as the other one, I don't think it deserves a negative score. – redtuna Apr 09 '13 at 17:59

Fisher-Yates shuffle on a single string vs. using an equal length permutation?

2 Answers2

Linked