Implementation of heaps algorithm

Question

Please I don't seem to know what is wrong with this my C# implementation of the heaps permutation algorithm. It does not give the correct permutation of an input array. Can somebody help me out?

Here is the pseudo-code

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
else
    for i := 0; i < n - 1; i += 1 do
        generate(n - 1, A)
        if n is even then
            swap(A[i], A[n-1])
        else
            swap(A[0], A[n-1])
        end if
    end for
    generate(n - 1, A)
end if

this is my c# Implementation

static void Permute(int[] A, int n) {
    if (n == 1) {
        printArray(A);
    } else {
        for (int i = 0; i < n - 1; i++) {
            Permute(A, n - 1);

            if (n % 2 == 0) {
                A = Swap(A, A[i], A[n - 1]);
                printArray(A);
            } else {
                A = Swap(A, A[0], A[n - 1]);
                printArray(A);
            }

        }

        Permute(A, n - 1);
    }
}


static int[] Swap(int[] A, int x, int y) {
    int temp;
    temp = A[x];
    A[x] = A[y];
    A[y] = temp;

    return A;
}

static void printArray(int[] A) {
    foreach(var x in A) {
        Console.Write(x);

    }
    Console.WriteLine();
}

Answer 1

Looks for me, that your meaning about the swap function, as you defined, expects to get the array and indexes of the swapped values.

So instead of:

Swap(A, A[i], A[n - 1]);
Swap(A, A[0], A[n - 1]);

Should be:

Swap(A, i, n - 1);
Swap(A, 0, n - 1);

By the way, if you had this algorithm for array of any other type than int[] you whould get compilation error in the swap call. You haven't have compilation error because of the coincidence that your array elements are of the same type as array index type: int

And another thing, even though its not an issue, it is not necessary to return the array, from Swap function. The first argument of the Swap, the array is passed by reference, so the Swap function works on the same array instance as in the caller function and not on its copy. So after you remove the unnecessary return from Swap, the printArray(A); called right after the Swap will print the same as you have now.