C# implementation of Heap's algorithm doesn't work

Question

I've attempted to write an implementation of Heap's Algorithm in C# which isn't working correctly. I'm trying to create a general-purpose implementation that will find all permutations of a string, and add them to a list.

I'm starting out like this:

List<string> permutations = new List<string>();
GenerateHeapPermutations(3, "ABC", permutations);

foreach (var p in permutations)
{
    Console.WriteLine(p);
}

Console.ReadKey();

And here's my implementation:

public static void GenerateHeapPermutations(int n, string s, List<string> sList)
{
    if (n == 1)
    {
        sList.Add(s);
    }
    else
    {
        for (int i = 0; i < n - 1; i++)
        {
            GenerateHeapPermutations(n - 1, s, sList);

            if (n % 2 == 0)
            {
                // swap the positions of two characters
                var charArray = s.ToCharArray();
                var temp = charArray[i];
                charArray[i] = charArray[n - 1];
                charArray[n - 1] = temp;
                s = new String(charArray);
            }
            else
            {
                var charArray = s.ToCharArray();
                var temp = charArray[0];
                charArray[0] = charArray[n - 1];
                charArray[n - 1] = temp;
                s = new String(charArray);
            }
        }

        GenerateHeapPermutations(n - 1, s, sList);
    }
}

The algorithm does yield the correct number of permutations (in this case, six), but the permutations themselves are incorrect:

ABC       BAC       CBA               
BCA       ABC       BAC

I don't think I'm deviating from the pseudocode example of Heap's algorithm on Wikipedia, and I'm having a hard time debugging this due the recursive nature of this algorithm (pretty tricky to conceptualize).

Could anyone offer any insight as to what the problem could be?

^{P.S. Not homework, just for fun.}

Answer 1

First things first: debugging. When dealing with recursion, the easiest way to debug your code is to set break points in your IDE and step through it bit by bit, taking notes that the code is behaving how you expect it to. This allows you to look at the values of your variables at every step.

You'll find that passing your string in everywhere is not yielding what you expect it to because you're passing a copy of it instead of the actual value. If you pass by reference instead (not sure if C# allows that), you'll do what you're expecting.