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

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.