c＋＋（9）
问题：给定一个有序序列1~n，要你将其完全打乱，要求每个元素在任何一个位置出现的概率均为1/n。
解决方案：依次遍历数组，对第n个元素，以1/n的概率与前n个元素中的某个元素互换位置，最后生成的序列即满足要求，1/n的概率可通过rand() % n实现。见如下程序：
void swap(int* p, int* q)
&&&&int tmp = *p;
&&&&*p = *q;
void shuffle(int *arr, int n)
&&&&for(i = 0; i & i++) {
&&&&&&&&int idx = rand() % (i + 1); //选取互换的位置
&&&&&&&&swap(&arr[idx], &arr[i]);
&使用数学归纳法证明：
l&&当n=1时，idx必为0，所以元素arr[0]在任何一个位置的概率为1/1，命题成立。
l&&假设当n=k时，命题成立，即n=k时，原数组中任何一个元素在任何一个位置的概率为1/k。
&则当n=k+1时，当算法执行完k次时，前k个元素在前k个位置的概率均为1/k。
&当执行最后一步时，前k个元素中任何一个元素被替换到第k+1位置的概率为：(1-1/(k+1)) * 1/k = 1/(k+1);&在前面k个位置任何一个位置的概率为(1-1/(k+1)) * 1/k = 1/(k+1);
故前k个元素在任意位置的的概率都为1/(k+1)
&所以，对于前k个元素，它们在k+1的位置上概率为1/(k+1)。
&对于第k+1个元素，其在原位置的概率为1/k+1，在前k个位置任何一个位置的概率为：(1-k/（k+1)）&* (1/k)=1/（k+1），所以对于第k+1个元素，其在整个数组前k+1个位置上的概率也均为1/k+1。
&综上所述，对于任意n，只要按照方案中的方法，即可满足每个元素在任何一个位置出现的概率均为1/n。
扩展：一道google面试题
给定一个未知长度的整数流（数目大于1000），如何从中随机选取1000个随机数。
解决方法：
l&&定义长度为1000的数组，对于数据流中的前1000个关键字，显然都要放到数组中。
l&&对于数据流中的的第n（n&1000）个关键字，则这个关键字被随机选中的概率为&1000/n。故以&1000/n&的概率用这个关键字去替换数组中的一个。这样就可以保证所有关键字都以&1000/n的概率被选中。对于后面的关键字都进行这样的处理，这样就可以保证数组中总是保存着1000个随机关键字。
注：以1000/n的概率选择一个数替换，可通过rand() % n实现，则这个数被替换到前1000个位置中的概率为1000/n。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：17766次
排名：千里之外
原创：25篇
转载：15篇
评论：11条
(1)(1)(1)(1)(1)(1)(3)(3)(7)(19)(2)直插入代码~~懒了
import java.util.R
class Card
Card(String n,String s)
this.num=n;
this.suit=s;
public String toString()
String ss=suit+":"+num+"
class DeskOfCard
Card card[];
public void initcard()//初始化
String num[]={"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
String suit[]={"方块","梅花","红桃","黑桃"};
card = new Card[52];
for(int i=0;i&52;i++)
card[i] = new Card(num[i%13],suit[i/13]);
public void shufflecard()//洗牌
Random rd = new Random();
for(int i=0;i&52;i++)
int j = rd.nextInt(52);//生成随机数
Card temp = card[i];//交换
card[i]=card[j];
public void dealcard()//发牌
for(int i=0;i&52;i++)
if(i%4==0) System.out.println("\n");
System.out.print(card[i]);
public class TestCard
public static void main(String[] args)
DeskOfCard cc = new DeskOfCard();
cc.initcard();
cc.shufflecard();
cc.dealcard();
阅读(...) 评论()洗牌算法（等概率随机排列数组，Fisher&Yates&shuffling）
Shuffling is a procedure used to randomize a deck of playing
cards to provide an element of chance in card games.
—wikipedia
1.如何洗牌？
我们玩扑克牌时洗牌可以使用Riffle方法，可以参考
2.洗牌算法
那么计算机如何洗牌呢？这就涉及到怎么设计一个洗牌算法，其中Fisher&Yates
shuffle是常用到的洗牌算法，非常简单。
伪代码如下：
shuffle an array a of n elements (indices 0..n-1):
i from n & 1 downto 1 do
← random integer with 0 ≤ j ≤ i
&&&&&&&exchange
a[j] and a[i]
python代码实现：
def fyshuffling(a):
i in range(len(a)-1,0,-1):
&&&&&&&&j=random.randint(0,i)
&&&&&&&&a[i],a[j]=a[j],a[i]
注：在python的random模块中提供了shuffle方法,使用的也是Fisher&Yates
shuffle算法。
云风在blog里面也讨论过，下面的讨论有很多。
在随机梯度下降(stochastic gradient
descent)中，因为要多次重复再训练集上进行，所以每次打乱训练集的顺序可以用洗牌算法。当然还有其他。
///////////////////////////////////////////////////////////////////////////////////////////////////
http://amyangfei.me//shuffle-algorithm/
前几天看了酷壳上的一篇文章，之后仔细看了Wikipedia对算法的介绍，这里简单的总结一下，基本是翻译Wikipedia。
Fisher and Yates’ original method
该算法最初是1938年由Ronald A. Fisher和Frank Yates在《Statistical tables for
biological, agricultural and medical
research》一书中描述，算法生成1-N个数的随机排列的过程如下：
原始数组中有数字1到N
设原始数组未被标记的数字个数为k，生成一个1到k之间的随机数
取出原始数组未被标记数字中的第k个，将其标记并插入到新的排列数组尾端。
重复过程2直到原始数组中没有未被标记的数字
过程3中生成的新数组就是一个对原始数组的随机排列
该算法可以理解为已知有n个元素，先从n个元素中任选一个，放入新空间的第一个位置，然后再从剩下的n-1个元素中任选一个，放入第二个位置，依此类推。算法在过程3查找未被标记的第k个数字有很多重复操作，导致算法效率并不高，总的时间复杂度为O(N2
)，空间复杂度为O(N)。算法的python实现如下所示：
from random import random
def FisherYateOldShullfe(items):
ret = [None] * len(items)
for i in reversed(range(0, len(items))):
j = int(random() * (i+1))
ret[i] = items[j]
del items[j]
return ret
if __name__ == '__main__':
srclist = [n for n in range(10)]
print FisherYateOldShullfe(srclist)
Modern version of the Fisher&Yates shuffle
改进版的Fisher&Yates shuffle算法是1964年Richard Durstenfeld在
Communications of the ACM volume 7, issue 7中首次提出，相比于原始Fisher-Yates
shuffle最大的改进是不需要在步骤3中重复的数未被标记的数字，该算法不再将标记过的数字移动到一个新数组的尾端，而是将随机数选出的数字与排在最
后位置的未标记数字进行交换。算法在python下的实现如下所示：
from random import random
def FisherYatesShuffle(items):
for i in reversed(range(1, len(items))):
j = int(random() * (i+1))
items[i], items[j] = items[j], items[i]
if __name__ == '__main__':
srclist = [n for n in range(10)]
FisherYatesShuffle(srclist)
print srclist
该算法同样可以理解成为这样的过程：从1到n个数字中依次随机抽取一个数字，并放到一个新序列的尾端（该算法通过互换数字实现），逐渐形成一个新的
序列。计算一下概率：如果某个元素被放入第i（1≤i≤n）个位置，就必须是在前 i-1 次选取中都没有选到它，并且第 i
次恰好选中它。其概率为：
算法中只有一个从1到N-1的循环，循环内操作为常数步，因而算法总的时间复杂度为O(N)，空间复杂度为O(1)。
Inside-out algorithm
Fisher-Yates
shuffle是一种在原地交换的生成过程，即给定一个序列，算法在这个序列本身的存储空间进行操作。与这种in-place的方式不同，inside-
out针对给定序列，会生成该序列随机排列的一个副本。这种方法有利于对长度较大的序列进行随机排列。
Inside-out算法的基本思想是从前向后扫描，依次增加i，每一步操作中将新数组位置i的数字更新为原始数组位置i的数字，然后在新数组中将位置i
和随机选出的位置j（0≤j≤i）交换数字。算法亦可以理解为现将原始数组完全复制到新数组，然后新数组位置i(i from 1 to
n-1)依次和随机位置j交换数字。算法的python实现如下：
from random import random
def insideout(source):
ret = [None] * len(source)
ret[0] = source[0]
for i in range(1, len(source)):
j = int(random() * (i+1))
ret[i] = ret[j]
ret[j] = source[i]
return ret
if __name__ == '__main__':
srclist = [n for n in range(10)]
print insideout(srclist)
对于这个算法，我们分析可以出现多少种不同的排列数，从$i=1$开始，每一次交换都可以衍生出$(i+1)$倍的排列数，因而总的排列方案数如下
图。在随机函数完全随机的情况下每一种排列都是等概率出现的，因而这种算法得到的是一个随机排序。它的时间复杂度和空间复杂度都是O(N)。
该算法有一个优点就是可以通过不断读取原始数组的下一个元素同时使新的排列数组长度加一，进而生成一个随机排列，即可以对长度未知的序列进行随机排列。实现的伪代码如下：
while source.moreDataAvailable
j &- random integer with 0 &= j &= a.length
if j = a.length
a.append(source.next)
a.append(a[j])
a[j] &- source.next
另一种想法
对n个元素的随机排序对应于这n个元素全排列中的一种，所以有这样一种方法求随机排序：求n个元素的随机排列，给定一个随机数k（1≤k≤n!），
取出n!个全排列中的第k个即是一种随机排序。于是需要解决2个问题：一是在一个足够大的范围内求随机数；另外是实现一种是在n!个全排列中求第k个全排
列的方法。第一个问题很古老，有人说随机数的最大范围决定于随即种子的大小，我有一种想法是对分段求随机数，比如需要求最大范围为N的随机数，那么可以对
N进行M进制分解，分别求M进制下的每一位的随机数，最后合成一个大的随机数；而第二个问题就比较容易了，有很多全排列生成算法，通过“原排
列”-&“原中介数”-&“新中介数”-&“新排列”的过程，可以很方便的求出第k个全排列。
//////////////////////////////////////////////////////////////////////////////////////////////////
/Jerry-Chou/archive//2311610.html
最近工作上遇到一个问题，即将一组数据，比如[A,B,C,D,E]其中的两个B,E按随机排列，其他的仍在原来的位置：
原始数组：[A,B,C,D,E]
随机字母：[B,D]
可能结果：[A,B,C,D,E],[A,D,C,B,E]
在解决这个问题的过程中，需要解决的一个问题是，怎么样让一个数组随机排序？上网一查，这也是计算机科学基础问题，也称之为洗牌算法(Shuffle
Algorithm)。
2，问题及解决
很简单：给定一个数组，将其中的元素随机排列。比如给定数组arry=&[1,2,3,4,5]。有A5-5种结果即5!=120种结果
也很简单，如果用白话来说就是：
a,选中第1个元素，将其与n个元素中的任意一个交换(包括第1个元素自己)。这时排序后的第1个元素已经确定。
b,选中第2个元素，将其与n-1个元素中作任意一个交换(包括第2个元素自己)。
c,重复上面步骤，直到剩1个元素为止。
知道其算法了，实现就简单了：
Randomize the list elements using Fisher&Yates shuffle algorithm
elements type
public static
void Shuffle(this
IList list)
&&&&Random
rng = new Random();
n = list.C
&&&&&&&&n--;
&&&&&&&&int
k = rng.Next(n + 1);
value = list[k];
&&&&&&&&list[k]
= list[n];
&&&&&&&&list[n]
该算法复杂度为O(n)，且无偏差，各个元素随机概率相等。确实是一个好算法:)。
在Wiki上，还有一些该算法的变种，但还是上面讲的那种比较好用，最初的Fisher&Yates算法并不好用，复杂度为O(n^2)。
//////////////////////////////////////////////////////////////////////////////////////
/futuredo/archive//2735686.html
头看酷壳上那篇《一些有意思的算法代码》，在清单上看到第一条是Binomial
Heap，回想一下好像是算法导论里刚刚研习过的内容，对，是二项堆，特别想看看具体的实现，点开链接看到满满的注释，顿时幸福洋溢。再看作
Schwarz，他是一个斯坦福大学计算机科学系的讲师，在自己的网站放了一些自己实现的算法和数据结构，觉得挺好的，有空可以去看看，这是链接：。
改天再谈谈二项堆的内容，今天先贴一个应该是其中最短的代码，Random
Shuffle随机洗牌，随便学习一下算法和C++。（这位老师还非常愿意分享自己的代码，只是注满注释的代码显得太长了）
码注释很多也很浅显，就不翻译了。虽说核心的代码就两行，但是里面的所有内容还是很应该学习的，比如，可以在自选范围内进行随机排列，可以传入自定义的随
机数产生算法，使用了模板这样任何数据类型都可以进行排列。这个算法核心的意思也就一句话来概括：随机选取一个数组元素，和第一个元素进行交换，然后继续
按照这种方法处理剩下的数组元素，只需要线性时间和常量空间即可。
这里面还有一点没有想到的是，在函数参数列表里居然可以传入函数名称，然后在里面执行这个传入的函数，难道是函数指针，C++真是忘得差不多了。
==================================================================================
#ifndef&RandomShuffle_Included
#define&RandomShuffle_Included
#include&&//&For&iter_swap
#include&&&&//&For&rand
template&&&span
style="color: #0000"&typename&RandomIterator&
void&RandomShuffle(RandomIterator&begin,&RandomIterator&end);
template&&&span
style="color: #0000"&typename&RandomIterator,&typename&RandomGenerator&
void&RandomShuffle(RandomIterator&begin,&RandomIterator&end,
&&&&&&&&&&&&&&&&&&&RandomGenerator&rnd);
template&&&span
style="color: #0000"&typename&RandomIterator,&typename&RandomGenerator&
void&RandomShuffle(RandomIterator&begin,&RandomIterator&end,
&&&&&&&&&&&&&&&&&&&RandomGenerator&rnd)&{
&&for&(RandomIterator&itr&=&&itr&!=&&++itr)
&&&&std::iter_swap(itr,&itr&+&rnd()&%&(end&-&itr));
template&&&span
style="color: #0000"&typename&RandomIterator&
void&RandomShuffle(RandomIterator&begin,&RandomIterator&end)&{
&&RandomShuffle(begin,&end,&std::rand);
==================================================================================
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}