※ 引述《sjgau (sjgau)》之铭言： : ※ 引述《mantour (朱子)》之铭言： : : 为什麽要洗这麽多次呀 : 我想，在或然率，机率，统计学里面， : 有所谓的 大数法则。 : 任何事情，一定要 样本空间够大， : 才能够显示出他的 意义。 : : 这样应该就可以了吧 : : ! a(0) ~ a(51) : : for i=0,50 : : 产生一个 i ~ 51 的乱数 : : swap(a(r), a(i)) : : 想像成本来是52个人坐一排 : : 然後重抽一轮新的座号 : 就这个 52个人坐成一排的观念来讨论， : 你的方法是，从 1号到 52号， : 每一个号码，去抽出一个号码 n1, : 和 n1 座位的人 互换座位。 第一个人与1~52的人随机互换之後 第一个位置是谁的机率都是均等 (如果乱数均匀) 所以 第二个位置的人与2~52互换之後 第二个位置是谁的机率都是均等 以此类推... 因此只要排过一次 理论上就是随机均匀的 如果不放心 重复3次即可 演算法复杂度为O(N) : 我的方法是 : 做 52次，每次抽出两个号码 n1, n2 : 这两个人 互换座位。 每次随机选2个人互换 所以某个号码连续52次都不被选中的机率为(50/52)^52=0.13 洗完之後大概有7张牌不会动到 这在玩牌就叫做洗不乾净吧?! 第一个方式有7张牌不被动到的机率为(1/52)^7=9.72*10^-13 这第二个方式真的要靠比N大很多的交换次数来弥补 : 效果，应该是 差不多。 : 如果要 真正的去 检讨比较 两个方法的优劣， : 有必要去 精通统计学里面的 检测技巧， 不用阿 简单就证明完毕了 : 真正的拿各种检测方法去 评比优劣。 : 但是，有这麽 严重吗？ : 以上 两个方法，多做个 几轮， : 52*10轮，不就 搞定。 : 所需要的 CPU time, 不超过 0.1秒 如果今天要排2000万笔资料怎麽办? 第一个方式 快速 (每次只要产生一次乱数 只要洗N次 记忆体存取可预测性高 ) 准确 (数学可证明) 简单 (程式也没有比第二个更复杂) 为何不使用?? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 202.145.77.21