\begin{equation*} p_i=\frac{1}{i}\times\frac{i}{i+1}\times\frac{i+1}{i+2}\times\cdots\times\frac{n-1}{n}=\frac{1}{n} \end{equation*}

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from random import Random class RandomSelector: def __init__(self, rand=None): self._selectedItem = None self._count = 0 self._rand = rand if self._rand is None: self._rand = Random() def SelectedItem(self): return self._selectedItem def Count(self): return self._count def AddItem(self, item): if self._rand.randint(0, self._count) == 0: self._selectedItem = item self._count += 1 

  1 2 3 4 5 6 7 8 9 10 11 12 13 from random import Random def RandomSelect(rand=None): selection = None count = 0 if rand is None: rand = Random() while True: # Outputs the current selection and gets next item item = yield selection if rand.randint(0, count) == 0: selection = item count += 1 

  1 2 3 4 5 6 7 8 9 10 11 12 13 # Sample code to use RandomSelect function n = 10 repeat = 100000 occurrences = [0 for i in xrange(n)] rand = Random() for i in xrange(repeat): selector = RandomSelect(rand) selector.next() selection = None for item in xrange(n): selection = selector.send(item) occurrences[selection] += 1 print occurrences 

[10020, 10084, 10003, 10008, 9985, 10145, 9987, 9925, 9955, 9888]


  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static bool RandomSelect( IEnumerable source, Random random, out TSource selectedItem) { if (source == null) { throw new ArgumentNullException("source"); } if (random == null) { random = new Random(); } selectedItem = default(TSource); int count = 0; foreach (TSource item in source) { if (random.Next(++count) == 0) { selectedItem = item; } } return (count> 0); } 

OK，问题解决了。结束之前再做个简单的扩展，改成等概率随机选取 m 个元素（可知每个元素被选中的概率都是 m/n）。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 from random import Random def RandomSample(m=1, rand=None): selection = [] count = 0 if rand is None: rand = Random() while True: # Outputs the current selection and gets next item item = yield selection if len(selection) < m: selection.append(item) else: idx = rand.randint(0, count) if idx < m: selection[idx] = item count += 1 

\begin{equation*} p_i=\left\{\begin{array}{ll} \frac{m}{i}\times\frac{i}{i+1}\times\frac{i+1}{i+2}\times\cdots\times\frac{n-1}{n}=\frac{m}{n} & i > m \\ 1\times\frac{m}{m+1}\times\frac{m+1}{m+2}\times\cdots\times\frac{n-1}{n}=\frac{m}{n} & i \leq m \end{array} \right. \end{equation*}

So what do you think? Did I miss something? Is any part unclear? Leave your comments below.