Q:

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

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. 

A:

You're algorithm is based on passing string instead of the actual array. 
When passing string a copy of the string is taken, thus changing the copied string won't change the actual string which is passed. 
When changing string to char array the problem is solved. 
public static void Main()
{
    List<string> permutations = new List<string>();
    GenerateHeapPermutations(3, new [] { 'A', 'B', 'C' }, permutations);

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

    Console. ReadKey();
}

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

            int indexToSwapWithLast = (n%2 == 0 ?  i : 0);
            // swap the positions of two characters
            var temp = charArray[indexToSwapWithLast];
            charArray[indexToSwapWithLast] = charArray[n - 1];
            charArray[n - 1] = temp;
        }

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

Note: You can get rid of the redundant number n input, and derive it from the array length, by using charArray. Length but, I didn't wanted to change your code unnecessarily. 

A:

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.