将一个数组中的元素序列打算顺序进行重排，并需要保证重排后的每一种结果是等概率且随机的。下面的两种算法哪一种是正确的？（注：random(a,b)返回一个a~b的随机整数）

1. for i=1 to n do swap( a[i], a[random(1,n)] );
2. for i=1 to n do swap( a[i], a[random(i,n)] );

首先，1～n的序列打乱重排共有n!个不同的排列，且每种排列被选中的概率为1/N!，只有这样的算法才是等概率且随机的。

第一种算法将会产生n^n种情况，显然其中出现了重复的情况。那么会不会虽然出现重复，但每种排列重复的次数相同，所以算法依然是等概率且随机的呢？答案是，不会。

假设上述情况成立，则n^n必定n!整除。但是，绝大多数情况下，n!的质因子远多于n^n的质因子（即n的质因子）。根据Bertrand-Chebyshev定理，在n/2和n之间一定还有一个质数。这两个质数的乘积已经大于n了。搞了半天，第一种看似对称而美观的算法居然是错的！即对所有大于2的n，上述整除都不不可能的。

第二种算法是符合要求的随机洗牌算法。

使用数学归纳法证明：

1、当n=1时，所以元素arr[0]在任何一个位置的概率为1/1，命题成立。

2、假设当n=k时，命题成立，即原数组中任何一个元素在任何一个位置的概率为1/k。

3、则当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。

解释完了洗牌算法的原理，那下面就是自己实现的random_shuffle的代码。

void swap(int& a,int& b)//不要尝试用“抑或”运算完成元素的交换，详见抑或运算
   int temp=b;
   a=temp;
void randomShuffle(int array[], int len)
     for(int i=1;i<len;i++)
         int j=rand()%(i+1);
         swap(array[i],array[j]);

 注：本文解释部分参考了以下文章：
 
http://hi.baidu.com/wulei407/blog/item/b6ea451b6572f9fdaf513315.html
 
http://blog.chinaunix.net/uid-20196318-id-216658.html
                    将一个数组中的元素序列打算顺序进行重排，并需要保证重排后的每一种结果是等概率且随机的。下面的两种算法哪一种是正确的？（注：random(a,b)返回一个a~b的随机整数）1. for i=1 to n do swap( a[i], a[random(1,n)] );2. for i=1 to n do swap( a[i], a[random(i,n)] );解释：首先，1～n
				
python函数用法，random.shuffle()用于将一个列表中的元素打乱顺序，值得注意的是使用这个方法不会生成新的列表，只是将原列表的次序打乱。
python random.shuffle代码案例
# python random.shuffle用法
import random
x = [i for i in range(10)]
print(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
random.shuffle(x)
print(x)
[2, 5, 4, 8, 0, 3,
				
扑克牌洗牌有多种算法：
第1个：每次从原数组A取出范围[1,i]的数放入B数组。 缺点是每次都要将数组i后面的元素进行移动。 是一个o(n2)算法
void xipai(int n){   // o(n2)
	int x = n;
	int idx = 1;
	while(n){
		int t = rand() % n;
		B[idx++] = A[ t + 1];
		for(int i = t + 1; i < n; i++){
			A[i] = A[i + 1];
void randomShuffle(int a[], int n){
	for(int i = 0; i < n; ++i){
		int j = rand() % (n - i) + i;
要求输入一组数据，输出的结果为这组数据的随机排列。
【解题思路】
1.      调用头文件algorithms中的random_shuffle函数。该函数的本质就是生成随机位置，不断交换，使得数据重新排列。
2.      产生随机数，结合swap函数实现数组的重新排列。
#include 
#include 
#include 
#include 
#inclu
1)从N张牌中随机选取一张牌k，将牌arry[N]与arry[k]交换位置
2)在剩下的牌中随机选取一张牌j，与位置为N-i（i为交换次数）的牌交换位置。
3)重复步骤2直到没有剩下的牌
2.代码`
#include<iostream>
#include<cstdlib>
#include<ctime>
using names...
random shuffle
shuffle有洗牌的意思，该方法也类似洗牌，从一个列表的前缀中随机取一个位置，和前缀的末尾做交换，这样对于每一位，都类似洗牌把它随机插进前面某个位置，就能实现把整个列表打乱成随机的分布，最后我们只需要取打乱后列表的前iii位，即是不重复的了。
template <typename T>
vector<T&g
				
对于一个数组a，我想打乱它原有的顺序，那么可以用该函数。
注意，如果要真正的随机，需要srand(time(NULL))操作，因为random_shuffle用的是随机数发生器，还记得rand()吗，如果不srand随机数种子，得到的随机数是固定的。
#include<bits/stdc++.h>
using namespace std;
int main()
    int a[1024];
    for(int i=0;i<1024;i++)a[i]=i;
    srand(t
        this->nums = nums;
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
#include &lt;vector&gt;
#include &lt;string&gt;
#include &lt;random&gt; // std::default_random_engine
#include &lt;time....