0

我最近在我的一个算法类中被指示使用 Knuth 的算法来创建存储在 malloc 数组中的排列。

这是设置：

array 是指向包含排列的 malloced 数组的指针。它最初存储 n 个值，每个位置都保存索引 + 1。

因此，如果 n 为 10，则数组最初为：

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

“rand”变量包含一些从 1 到 n 的变量。（在本例中为 1-10）。

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 数组的指针的地址。

我应该如何以及为什么要对地址进行 XOR？

我不明白什么？

感谢您的任何帮助！

4

1 回答 1

4

首先，交换不应该进行按位异或。应该换了吧

通常是这样写的：

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;
}

这可能是某人在交换中进行 XOR 的意思。

其次，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]，它从尚未被选中的元素中随机选择一个元素。

于 2016-03-05T20:43:34.220 回答