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

  1. 引子:

  平日工作学习时总会遇到一些令人欣喜的代码段子（Snippet），虽然都很短小，但是其间所含的道理都颇有意味，遂而觉得应该不时的将她们记下，一来算作复习整理，二来也给有兴趣的朋友做些参考，虽然题目说成了一个系列，但自己也不知道能写多少，大概准则估计也就是写到哪算哪了，今天算是第一篇，瞎扯扯随机选择 ：）

  2. 问题:

  题目很简单，如何等概率的选取一个集合中的元素，譬如我们现在有一个vector(C++)：

  

vector
   
     v = { 1, 2, 3, 4, 5 };int selected = random_select(v);
   

  如何实现这个random_select 函数呢？其实有个很简单的方法，便是随机选取一个范围在[0, v.size()) 中的整数即可，代码大抵是这个样子：

int random_number(int max) {    return rand() % max;}int random_select(const vector
   
    & v) {    return v[random_number(v.size())];}
   

  当然，我们还可以继续优化上述代码，譬如将random_select泛化等等，在此就不赘述了，仅从功能性角度来看，上面代码确实完成了我们的期望：“等概率”的随机选取了vector集合中的某个元素。（这里“等概率”之所以加上引号，是因为真实的选取结果其实并不是绝对等概率的，问题在于我们使用了rand()取余来获取随机数，而这种方法所产生的随机数大部分情况下都不是均匀分布的，S.T.L（注意是个人名：））对于此有个非常精彩的）

  但在现实生活中，很多情况下我们未必一开始就知道集合的长度，譬如我们目前只有begin和end两个前向迭代器：

ForwardIterator begin = some_func_get_begin();ForwardIterator end = some_func_get_end();ForwardIterator iter = random_select(begin, end);

  那么这里的 random_select 应该如何实现才能保证等概率的选取这个集合中的元素呢？有个方法大概可以算是归约吧，就是首先使用迭代器遍历一遍集合，然后我们便可以知道集合的长度了，然后问题也就归约到之前的随机选取问题了。不管怎么说，这是一个可行的办法，但是明眼人一看就知道这种方法不是很简洁，甚至可以说有些坏味道，但是如果马上让我来实现一下 random_select 的话，我估摸着可能也会采取这种方法，尽管心里觉得别扭，幸而前些日子在看到了一个更简单的方法，很有意思：）如果用代码实现的话，大概是这个样子：   使用 C++ 的一个完整示例：

#include 
   
    #include 
    
     #include 
     
      using namespace std;namespace {class Random {public:    int Next(int min, int max) {        uniform_int_distribution<> distribution(min, max);        return distribution(m_engine);    }    int Next(int max) {        return Next(0, max);    }private:    mt19937 m_engine;} random;template
      
       ForwardIterator random_select(ForwardIterator begin, ForwardIterator end) {    int count = 0;    auto selected = end;    for (auto iter = begin; iter != end; ++iter) {        if (random.Next(count++) == 0) {            selected = iter;        }    }    return selected;}}int main() {    list
       
         l = { 1, 2, 3, 4, 5 };    int testCount = 32;    for (int i = 0; i < testCount; ++i) {        cout << *random_select(std::begin(l), std::end(l)) << " ";        if ((i + 1) % 10 == 0) {            cout << "\n";        }    }    return 0;}
       
      
     
    
   

  另有一个C#的完整示例，原理是一致的，也顺道贴一下：

using System;using System.Collections.Generic;namespace RandomSelect {		class Program {				static Random random = new Random();				public static T RandomSelect
   
    (IEnumerable
    
      enumerable) {			int count = 0;			T selected = default(T);						var enumerator = enumerable.GetEnumerator();			while (enumerator.MoveNext()) {				if (random.Next(++count) == 0) {					selected = enumerator.Current;				}			}						return selected;		}				public static void Main(string[] args) {			var list = new List
     
       { 1, 2, 3, 4, 5 };			int testCount = 32;			for (int i = 0; i < testCount; ++i) {				Console.Write(RandomSelect(list));				Console.Write(" ");				if ((i + 1) % 10 == 0) {					Console.WriteLine();				}			}			Console.WriteLine();						Console.Write("Press any key to continue . . .");			Console.ReadKey(true);		}		}}
     
    
   

3. 道理:

  不知你看懂了多少代码，其实上面代码砍头去尾之后，真正有趣的大概就是这么一段：

for (auto iter = begin; iter != end; ++iter) {        if (random.Next(count++) == 0) {            selected = iter;        }    }

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