c - 试图了解Knuth的置换算法

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
我最近在我的一个算法类中被指示使用knuth的算法来创建存储在malloc d数组中的置换。
设置如下：
array是指向包含排列的malloced数组的指针它最初存储n个值，每个位置保存索引+1。
所以如果n是10，那么数组最初是：
[1，2，3，4，5，6，7，8，9，10]
“rand”变量包含从1到n的一些变量（在本例中为1-10）。
swap应该是一个执行位异或swap（xor）的函数。
最终的结果应该是一些1-n的置换。
因此[5，6，2，8，7，4，1，3，10，9]作为一个可能的置换是有效的。
然而，[1，1，5，7，8，2，3，5，5，6]是无效的，因为它不是排列它有副本。
但我不能对我们被告知要使用的代码做正面或反面的解释：

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

我们从数组的第二个元素开始。（i=1）
然后尝试将两个参数进行异或运算：
第一个：&array[i]
这是指向malloced数组的指针的地址。（一个双指针，对吧？）
第二个参数是完全相同的。指向malloced数组的指针的地址。
我该怎么做，为什么要对地址做异或运算？
我不明白什么？
谢谢你的帮助！

最佳答案

首先，swap不应该执行逐位异或。应该是交换的。
通常是这样写的：

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

但是有一个使用XOR的技巧不需要额外的变量您可以这样实现交换：

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

这可能就是有人所说的在交换中执行异或的意思。
其次，rand必须在0到i的范围内，而不是1到n的范围内，你需要一个无偏的随机排列。
给定rand（x）返回[0，x]中的一个数字，您需要如下内容：

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

它的工作方式很简单：对于每个数组[i]，它从尚未被选择的元素中随机选择一个元素。

关于c - 试图了解Knuth的置换算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35819601/