C++ - 是否可以使用 random_shuffle 一次且仅一次生成数组的每个排列？

Question

我的任务是通过将长度为“n”的数组的每个排列“喂入”一次来测试排序算法。我应该用 random_shuffle 来做。

我知道 random_shuffle 服从均匀分布——也就是说，每个排列产生的机会均等——但这并不意味着每个排列在得到重复结果之前都会产生一次，对吧？说，如果第一个结果是 12345，它应该取 5!使用 random_shuffle 得到重复的 12345 结果。但事实并非如此。我经常得到重复的结果。这是我正在使用的代码:

#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
int v[5]={1,2,3,4,5}, w[5], cuenta=1;
memcpy(w,v,sizeof v);
srand(time(0));

do {
    random_shuffle(v,v+5);
    for (int j=0;j<5;j++)
        cout << v[j];
    cout << endl;
    cuenta++;
    cout << cuenta << endl;
    } while (memcmp(w,v,sizeof v));
}

我做错了什么吗？或者这就是 random_shuffle 的运作方式？

编辑:

我知道 next::permutation 会更有意义。我知道这使事情过于复杂。但是我的老师坚持要我这样做，因为 random_shuffle 遵循均匀分布，所以我不应该得到重复的结果；因此与我读过的所有内容相矛盾，包括文档。我必须使用 random_shuffle。我只是在寻找此功能的确认/特定行为。即便如此，next_permutation 也不是随机的。

Answer 1

你必须使用random_shuffle吗？这似乎是此函数的错误算法，因为无法保证实际获得所有 n! 不同排列所需的尝试次数。更合适的算法是 std::next_permutation。如:

 do {
     // test your sort
 } while (std::next_permutation(v, v+5)); 

使用 random_shuffle，您必须实际检查这是否是您之前完成的排列，并执行所有这些额外的工作以确保您没有错过任何一个。我的意思是，如果您必须将它用于作业，您就必须使用它，但我会尽量不使用它:)

[更新] 我只是有一个想法。也许你的老师只是想让你尝试很多不同的排列，而不一定是所有的排列？喜欢:

for (int i = 0; i < 1000; ++i) {
    std::random_shuffle(v, v+5);
    // test your sort
}

那可能测试所有排列。它可能不会。但我觉得你的类型不太可能被打破并通过。