STL应用之随机化全排列

输入：一个序列，可以是一组数字，如1,2,3,4....，也可以是一组字符串"111","222",....

输出：原序列的随机化序列

要求：每种随机的序列出现的概率相等，如输入{1,2,3},那么有6种随机化序列，要求输出一种即可，但每种随机序列输出的概率是六分之一

主要方法：

对于{1,2,3}，先将3固定，交换1,2，有{1,2,3},{2,1,3},再将每组的3与这组数据任意一个交换，最终可得六种序列，根据概率乘法公式，每种

序列出现的概率是六分之一

对于{1,2,3,4},将4固定，前面的{1,2,3}已经随机化6种序列，那么按照前面的方法，将4与每组所有数据交换，最终可得24种随机序列，每种

序列出现的概率是二十四分之一。

其余类推

编程需要考虑程序的通用性，采用泛型编程技术

代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <Iterator>
    

using namespace std;
const int n=10;

template<class Iterator>
void Myrandom_shuffle(Iterator beg,Iterator end) {
    Iterator it;
    srand(unsigned(time(0)));
    int diff;
    Iterator swp;

    for(it=beg+1;it!=end;it++) {
        diff=rand()%(it-beg+1);
        swp=beg+diff;
        swap(*it,*swp);
    }
}

typedef int Type;

template<class Iterator>
inline static void Output(Iterator beg,Iterator end) {
    copy(beg,end,ostream_iterator<Type>(cout," "));
}

void main() {
    vector<Type>v;
    int i;
    cout<<"Written by Wangzhicheng "<<endl;
    cout<<"原先序列:"<<endl;
    for(i=0;i<n;i++) {
        v.push_back(i+1);
    }
    Output(v.begin(),v.end());
    cout<<endl;
    Myrandom_shuffle(v.begin(),v.end());
    cout<<"混洗后的序列:"<<endl;
    Output(v.begin(),v.end());
    cout<<endl;
}

测试：