j**l
发帖数: 2911 | 1 以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
void KnuthShuffle(int pArr[], int n)
{
int rand;
for (int i = n - 1; i >= 0; i--)
{
rand = GenRand(0, i); // including 0 and i
swap(pArr[i], pArr[rand]);
}
}
void KnuthShuffle(int pArr[], int n)
{
int rand;
for (int i = 0; i < n; i++)
{
rand = GenRand(i, n-1); // including i and n-1
swap(pArr[i], pArr[rand]);
}
} | q*********u
发帖数: 280 | 2 我wikipedia看到一种，说也是他论证过的，给５２个牌随机数，每个数的随机数都不
互相相等，如果有和前面的数重复，则重新产生。
最后来一个排序。
wiki上先说的这个，然后再说比一边产生随机数一边交换。
以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
void KnuthShuffle(int pArr[], int n)
{
int rand;
for (int i = n - 1; i >= 0; i--)
{
rand = GenRand(0, i); // including 0 and i
swap(pArr[i], pArr[rand]);
}
}
void KnuthShuffle(int pArr[], int n)
{
int rand;
for (int i = 0; i < n; i++)
{
rand = GenRand(i, n-1); // including i and n-1
swap(pArr[i], pArr[r
【在 j**l 的大作中提到】
: 以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
: void KnuthShuffle(int pArr[], int n)
: {
: int rand;
: for (int i = n - 1; i >= 0; i--)
: {
: rand = GenRand(0, i); // including 0 and i
: swap(pArr[i], pArr[rand]);
: }
: }
| q*********u
发帖数: 280 | 3 好像说是已经交换过的牌不用再交换了。
以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
void KnuthShuffle(int pArr[], int n)
{
int rand;
for (int i = n - 1; i >= 0; i--)
{
rand = GenRand(0, i); // including 0 and i
swap(pArr[i], pArr[rand]);
}
}
void KnuthShuffle(int pArr[], int n)
{
int rand;
for (int i = 0; i < n; i++)
{
rand = GenRand(i, n-1); // including i and n-1
swap(pArr[i], pArr[rand]);
}
}
【在 j**l 的大作中提到】
: 以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
: void KnuthShuffle(int pArr[], int n)
: {
: int rand;
: for (int i = n - 1; i >= 0; i--)
: {
: rand = GenRand(0, i); // including 0 and i
: swap(pArr[i], pArr[rand]);
: }
: }
| j**l
发帖数: 2911 | 4 两种方法都固定已经交换过的牌，只是一个从后向前走，一个从前向后走
【在 q*********u 的大作中提到】
: 好像说是已经交换过的牌不用再交换了。
:
: 以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
: void KnuthShuffle(int pArr[], int n)
: {
: int rand;
: for (int i = n - 1; i >= 0; i--)
: {
: rand = GenRand(0, i); // including 0 and i
: swap(pArr[i], pArr[rand]);
| r****o
发帖数: 1950 | 5 问问，这两种方法里面，是不是可以判断一下，
如果rand刚好等于i，就不用swap了。
【在 j**l 的大作中提到】
: 以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
: void KnuthShuffle(int pArr[], int n)
: {
: int rand;
: for (int i = n - 1; i >= 0; i--)
: {
: rand = GenRand(0, i); // including 0 and i
: swap(pArr[i], pArr[rand]);
: }
: }
| y**i
发帖数: 1112 | 6 为什么要这么取随机数，要包括自己的下标
我觉得rand = GetRand(0, i-1)就已经很好了啊
【在 j**l 的大作中提到】
: 以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
: void KnuthShuffle(int pArr[], int n)
: {
: int rand;
: for (int i = n - 1; i >= 0; i--)
: {
: rand = GenRand(0, i); // including 0 and i
: swap(pArr[i], pArr[rand]);
: }
: }
| j**l
发帖数: 2911 | 7 以从前向后排为例，之所以是GetRand(i, n-1), 要包括i
因为第i号牌最终就放在i号位置不动是n!种全排列包括的
第0号位置可以放n张牌之一
第1号位置可以放(n-1)张牌之一，因为第0号位置固定了一张牌
第2号位置可以放(n-2)张牌之一, 因为第0号位置和第1号位置固定了两张牌
...
第n-1号位置只能放最后剩下的一张牌
所以有n!种放法，不重不漏
【在 y**i 的大作中提到】
: 为什么要这么取随机数，要包括自己的下标
: 我觉得rand = GetRand(0, i-1)就已经很好了啊
| l******c
发帖数: 2555 | 8 从后往前编程方便。
in C++
index = rand（）% （i + 1） 即可。
从前往后 就复杂些。
【在 j**l 的大作中提到】
: 以下两种都可以么？为什么他老人家给出的是第一种，从后往前排？
: void KnuthShuffle(int pArr[], int n)
: {
: int rand;
: for (int i = n - 1; i >= 0; i--)
: {
: rand = GenRand(0, i); // including 0 and i
: swap(pArr[i], pArr[rand]);
: }
: }
|
|
|
