Trying to understand Knuth's algorithm for permutations

I was recently instructed in one of my algorithm classes to use Knuth's algorithm to create permutations stored in a malloc'd array.

Here is the setup:

array is a pointer to a malloced array holding the permutation. It is intially storing n values, each position holding the index + 1.

So if n was 10, the array would initially be:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

The "rand" variable holds some variable from 1 to n. (In this example, 1-10).

Swap is supposed to be a function that does a bit-exclusive OR swap (XOR).

The end result is supposed to be some permutation of 1-n.

So [5, 6, 2, 8, 7, 4, 1, 3, 10, 9] would be valid as one possible permutation.

However, [1, 1, 5, 7, 8, 2, 3, 5, 5, 6] would not be valid, since it's not a permutation. It has duplicates.

But I can't make heads or tails of this code we were told to use:

for(i = 1; i < n; i++) {
    swap(&array[i], &a[rand]);
}

So we start off on the second element of the array. (i = 1)

We then attempt to XOR two paramenters:

First: &array[i]

That is the address of a pointer to the malloced array. (A double pointer, right?)

And the second parameter is the exact same thing. An address of a pointer to the malloced array.

How and why the heck am I supposed to do XOR on addresses?

What am I not understanding?

Thanks for any and all help!

Solution

Firstly, swap is not supposed to do a bitwise exclusive or. It's supposed to swap.

Usually, that's written:

void swap(int *a, int *b)
{
    int t=*a;
    *a=*b;
    *b=t;
}

But there's a trick using XOR that doesn't require an extra variable. You can implement swap like this:

void swap(int *a, int *b)
{
    *a^=*b;
    *b^=*a;
    *a^=*b;
}

Which is probably what someone meant by doing an XOR in swap.

Secondly, rand has to range from 0 to i, not 1 to n, of you want an unbiased random permutation.

Given rand(x) returns a number in [0,x], you want something like this:

for (int i=n-1; i>0; --i)
{
    j = rand(i);
    if (i!=j)
    {
        swap(&array[i],&array[j]);
    }
}

The way it works is simple: for each array[i], it chooses an element randomly from the ones that haven't already been picked.