求问一道数组shuffle的问题 (转载) - Programming版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Programming版 - 求问一道数组shuffle的问题 (转载)

相关主题
● Shuffle performance (C#)	● 今天电面又被老印黑了。。。。 (转载)
● 请教算法题	● 关于链表（Linked list）
● C里面的数组拷贝	● help understanding code (random number)
● [合集] 面试问题	● Randomization of an array
● 问个很基础的问题	● Random Switch Between Two Different URLs
● C++debug遇到的问题	● C++ Q87: What is wrong with this swap function? (转载)
● 大家帮我看看这个C程序为什么出错了	● 如何sort and merge n 个sorted linked list
● 如何编程实现以下简单的组合问题	● 一个debug的问题

相关话题的讨论汇总
话题: list话题: shuffle话题: swap话题: 数组话题: 出错

进入Programming版参与讨论

(共1页)

c********l
发帖数: 8138

【以下文字转载自 JobHunting 讨论区】
发信人: coupondeal (Coupon Deal), 信区: JobHunting
标题: 求问一道数组shuffle的问题
发信站: BBS 未名空间站 (Sun Mar 17 21:46:36 2013, 美东)
数组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));
会出错。
具体出错的原因是什么？怎么描述这种现象？

k**********g
发帖数: 989

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
There's a big section discussing the source of biases from incorrect
implementation.

(共1页)

进入Programming版参与讨论

相关主题
● 一个debug的问题	● 问个很基础的问题
● 【求助】一篇2011年论文中的算法实现代码	● C++debug遇到的问题
● 几年前一个科学预言python的崛起	● 大家帮我看看这个C程序为什么出错了
● 问一个随机排列的问题.	● 如何编程实现以下简单的组合问题
● Shuffle performance (C#)	● 今天电面又被老印黑了。。。。 (转载)
● 请教算法题	● 关于链表（Linked list）
● C里面的数组拷贝	● help understanding code (random number)
● [合集] 面试问题	● Randomization of an array

相关话题的讨论汇总
话题: list话题: shuffle话题: swap话题: 数组话题: 出错

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天