本文共 1337 字，大约阅读时间需要 4 分钟。

        上次写遗传算法用到STL里的random_shuffle函数，算法的主要思想在《计算机程序设计艺术》的3.4.2节有详细的分析，现在这里简单说明一下算法的实现。

应包含头文件：

        #include<algorithm>

函数原型：

SGI版本一

template 
   
    inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last) {	__random_shuffle(first, last, distance_type(first));}template 
    
     void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last, Distance*) {	if (first == last)		return;	for (RandomAccessIterator i = first + 1; i != last; ++i)#ifdef __STL_NO_DRAND48         //DRAND48和LRAND48都是基于均匀分布区间上的随机函数		iter_swap(i, first + Distance(rand() % ((i - first) + 1)));#else		iter_swap(i, first + Distance(lrand48() % ((i - first) + 1)));#endif}
    
   

template 
   
    void random_shuffle(RandomAcessIterator first, RandomAcessIterator last, RandomNumberGenerator& rand){//注意rand应为引用参数	if (first == last)		return;	for (RandomAcessIterator i = first + 1; i != last; ++i)		iter_swap(i, first + rand((i - first) + 1));}
   

        将[first,last)的元素次序随机重排。N个元素的排列方式共有N!种，random_shuffle会产生一个均匀分布，因此任何一个排列被选中的概率为1/N!。

简单实例：

#include
   
    #include
    
     #include
     
      int main(){	std::vector
      
        vec;	for (int i = 0; i < 10; ++i){		vec.push_back(i);	}	random_shuffle(vec.begin(), vec.end());	for (int i = 0; i < 10; ++i){		std::cout << vec[i] << " ";	}}
      
     
    
   

输出:        8 1 9 2 0 5 7 3 4 6

转载地址：http://urebi.baihongyu.com/