c********l
发帖数: 8138 | 1 数组shuffle，经典的Fisher and Yates的算法是
public static void shuffle(List list, Random rnd) {
int size = list.size();
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
}
}
如果将
swap(list, i-1, rnd.nextInt(i));
改成
swap(list, i-1, rnd.nextInt(N));
会出错。
具体出错的原因是什么？怎么描述这种现象？ | l*****a
发帖数: 14598 | 2 shuffle的目标是每次确定当前位置上的元素，然后处理下一个
你用Random.nextInt(N)显然不满足这个
【在 c********l 的大作中提到】
: 数组shuffle，经典的Fisher and Yates的算法是
: public static void shuffle(List list, Random rnd) {
: int size = list.size();
: for (int i=size; i>1; i--)
: swap(list, i-1, rnd.nextInt(i));
: }
: }
: 如果将
: swap(list, i-1, rnd.nextInt(i));
: 改成
| c********l
发帖数: 8138 | 3 为什么不满足“每次确定当前位置上的元素，然后处理下一个”这一个条件，
会导致出错？
换句话，每次在当前位置上元素时，瞎抓一气，岂不是更random吗？
【在 l*****a 的大作中提到】
: shuffle的目标是每次确定当前位置上的元素，然后处理下一个
: 你用Random.nextInt(N)显然不满足这个
| j*****y
发帖数: 1071 | 4 可以使试试 {1, 2, 3} ，用第二种方法我好像得出 出现 1 2 3 这种排列的概率是
4 /27. 等概率的话应该是 1 / 6
【在 c********l 的大作中提到】
: 数组shuffle，经典的Fisher and Yates的算法是
: public static void shuffle(List list, Random rnd) {
: int size = list.size();
: for (int i=size; i>1; i--)
: swap(list, i-1, rnd.nextInt(i));
: }
: }
: 如果将
: swap(list, i-1, rnd.nextInt(i));
: 改成
| c********l
发帖数: 8138 | 5 我是用统计的方法证明了模拟xxxxxx遍之后，得出的shuffle结果是biased
但是有没有用数学理论能解释现象的？
而且大数模拟之后，每个初始element的分布也不一样
【在 j*****y 的大作中提到】
: 可以使试试 {1, 2, 3} ，用第二种方法我好像得出 出现 1 2 3 这种排列的概率是
: 4 /27. 等概率的话应该是 1 / 6
| d*******3
发帖数: 58 | 6 总共有n!种排列，第二种算法产生的排列数是n^n的，必然有重复，要保证等概率的至
少要有保证n^n 能整除 n!,但这个反例就很多了。。。 | j*****y
发帖数: 1071 | 7 不错.
【在 d*******3 的大作中提到】
: 总共有n!种排列，第二种算法产生的排列数是n^n的，必然有重复，要保证等概率的至
: 少要有保证n^n 能整除 n!,但这个反例就很多了。。。
| r**h
发帖数: 1288 | 8 言简意赅，赞
【在 d*******3 的大作中提到】
: 总共有n!种排列，第二种算法产生的排列数是n^n的，必然有重复，要保证等概率的至
: 少要有保证n^n 能整除 n!,但这个反例就很多了。。。
| c********l
发帖数: 8138 | 9 thanks
【在 d*******3 的大作中提到】
: 总共有n!种排列，第二种算法产生的排列数是n^n的，必然有重复，要保证等概率的至
: 少要有保证n^n 能整除 n!,但这个反例就很多了。。。
|
|
