- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我的任务是通过将长度为“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 也不是随机的。
最佳答案
你必须使用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
}
那可能测试所有排列。它可能不会。但我觉得你的类型不太可能被打破并通过。
关于C++ - 是否可以使用 random_shuffle 一次且仅一次生成数组的每个排列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26854448/
我是一名优秀的程序员,十分优秀!