algorithm - 生成从 1 到 n 的随机数字列表的算法的正确性

Question

给定一个函数 Random(x, y)，它返回一个介于 x 和 y(含)之间的随机数。设计一个算法来打印从 1 到 n 的 unique_random_numbers 列表。 列表中必须有 n 个数字，每个数字只能出现一次。

例如

PrintRandomList(1, 5) can print -> 2, 5, 1, 4, 3    
PrintRandomList(1, 6) can print -> 4, 1, 6, 3, 2, 5

我已经能够想出一个算法，但无法证明它会生成一个真正的随机列表(假设 Random(x, y) 会生成真正的随机数) .

void PrintRandomList(int a, int b) {
    if(a<=b) {
        int pivot = Random(a, b);
        printf("%d ", pivot);
        PrintRandomList(a, pivot-1);
        PrintRandomList(pivot+1, b);    
    }
}

我的问题:算法是否正确？如果是，那么我们可以证明算法的正确性吗？

如果这个算法是正确的，那么我们也可以用它来打乱数组而不是使用 Knuth 打乱算法。

Answer 1

证明此算法是否有效的根本问题的诀窍是，您必须证明每个结果同样可能。正如其他人指出的那样，这里不是这种情况。

如果您能找到任何无法到达或不太可能到达的序列，那么您就知道该算法不“公平”。这个论证的反面证明是的。