65.9K
CodeProject 正在变化。 阅读更多。
Home

以伪随机方式从列表中均匀选择项目

Sal Razzaq
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.38/5 (7投票s)

2013年12月2日

CPOL

3分钟阅读

viewsIcon

30161

downloadIcon

139

如何公平地从列表中选择项目

引言

最近，我需要编写代码来从一个小列表中随机选择项目。

给定一个项目列表，["R", "G", "B"]，选择一个项目，“R”、“G”或“B”。

平均而言，在给定的会话中需要进行大约 99 次选择。在会话结束时，我希望大约选择 33 次 R、33 次 G 和 33 次 B (33 + 33 + 33 = 99)。

.NET 提供了一个System.Random 类来随机选择给定范围内的数字。我使用的数值范围是 0、1、2，分别对应于 R、G、B。不幸的是，单独使用System.Random 并不能产生均匀分布的选择值。

  1. 有些值比其他值选择的次数更多。
  2. 有时，在连续的选择中会选择相同的值。

因此，我开始努力编写一个随机选择算法来解决上述两个缺点。

背景

以下是我的第一次尝试编写一个从列表中随机选择项目的类。

public class RandomPickerSimple<T>
{
    private List<T> m_Items;
    private Random m_Random;

    public RandomPickerSimple(List<T> items)
    {
        this.m_Items = items;
        m_Random = new Random();
    }

    public T PickItem()
    {
        int pickedIndex = m_Random.Next(0, m_Items.Count);
        return m_Items[pickedIndex];
    }
}

给定一个列表 ["R", "G", "B"]，我使用RandomPickerSimple 类进行了 99 次选择。以下是 3 次运行的结果。

 B R R B R G B R R G G B B B B R G R G G B G G G R B R G G B G R R B B R 
     B G G G G R G R B R R G G G B R G B B G B G B R G G G G R G B B R 
     G R R G B R G B R B R B G B R B G G G B R G R B R R B G B R
 "B":31 "G":37 "R":31

  G G G B G R G B G G B B G G R B B R R B R B G G R B B B B R G B R R G G 
    G R B G R G B G R B R R R G B G R B B G B R B G R G B G R B B G B G G B 
    G B B G R R R G G G B G G R B G G R G G R R G G B R G
 "B":31 "G":41 "R":27
 
  G R G R G B G R B G B B R G R G G R R R B R B G B B R B B R G G G R B R 
    R G R G R G G R B R R G G B B B R R B R R R G G G B G B B G R R G B G B R 
    B B G B B G G B B R R R B G G R G R R R G B R R G R
 "B":29 "G":33 "R":37 

从以上结果可以看出：

  • 项目没有被均匀选择。例如，在最后一次运行中，“B”被选择了 29 次，而“R”被选择了 37 次。
  • 在连续的选择中选择了相同的项目。请注意最后一次运行中连续选择的“R R R”、“G G G”和“B B B”值。

更复杂的 RandomPicker

为了更均匀地选择项目，我进行了以下调整。

public class RandomPicker<T>
{
    private Dictionary<T, int> m_Items;
    private Random m_Random;
    private T m_LastPick;

    public RandomPicker(List<T> items)
    {
        if (items.Count < 2)
            throw new ArgumentOutOfRangeException("The list must contain at least two items.");
        this.m_Items = new Dictionary<T, int>();
        items.ForEach(x => this.m_Items.Add(x, 0));
        m_Random = new Random();
    }

    private List<T> GetCandidateList()
    {
        int minOccur = m_Items.Values.Min();
        var list = m_Items.Keys.Where(x => m_Items[x] == minOccur).ToList();
        list.Remove(this.m_LastPick);
        if (list.Count < 1)
        {
            list = m_Items.Keys.ToList();
            list.Remove(this.m_LastPick);
        }
        return list;
    }

    public T PickItem()
    {
        var candidateList = GetCandidateList();
        int pickedIndex = m_Random.Next(0, candidateList.Count);
        m_Items[candidateList[pickedIndex]]++;
        m_LastPick = candidateList[pickedIndex];
        return candidateList[pickedIndex];
    }
}

主要改进如下。

  1. 该类跟踪每个项目被选择的次数 (在m_Items字典中)。
  2. 该类根据项目在之前的选择中被选择的次数构建候选项目列表 (参见GetCandidateList()方法)。
  3. 该类记住上次的选择，以便不在连续的选择中选择相同的项目 (参见m_LastPick变量)。

给定一个列表 ["R", "G", "B"]，我使用RandomPicker 类进行了 99 次选择。以下是三次运行的结果：

 B R G B G R G R B G B R B G R G R B R G B R B G R 
  B G R B G R B G R G B G B R B G R G B R G B R B G R B G R 
  B G R G B R G B R B G R B G R B G R G R B G B R G R B G B R G R B G R B R G B G B R B G R
 "B":33 "G":33 "R":33

  G B R G B R G B R G B R G R B G B R G R B R G B R B G B G R B G R 
   G R B R B G B G R B R G R B G B G R G B R G R B R B G R B G R B G B G R B R G 
   B G R G B R B R G B R G R G B R G B G R B G B R G B R
 "B":33 "G":33 "R":33

  R B G B R G R G B G R B G B R B R G B G R B R G B R G B R G R B G B G R B 
   R G B G R G B R G R B G B R G R B R B G R B G R B G R B G R B G B R 
   G B G R B R G B R G B G R B R G R B G B R G R B G R G B
 "B":33 "G":33 "R":33 

从以上结果可以看出：

  • 项目选择更均匀。在所有三次运行中，“R”、“G”和“B”都被选择了 33 次。
  • 没有在连续的选择中选择相同的项目。

为了进一步验证结果，我对一个整数列表 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 运行了随机选择测试。运行结果如下 (99 次选择)。

 10 3 12 1 11 2 5 8 7 9 4 6 12 2 3 4 11 6 5 8 10 7 9 1 12 10 11 4 
      5 7 1 9 2 3 8 6 12 4 10 1 6 3 2 11 9 8 7 5 7 9 8 6 5 12 1 4 10 11 2 3 2 10 4 12 11 
      5 1 9 3 7 6 8 6 1 2 11 4 12 5 3 7 8 10 9 1 7 5 4 2 9 6 3 8 12 11 10 12 2 11
 "1":8 "2":9 "3":8 "4":8 "5":8 "6":8 "7":8 "8":8 "9":8 "10":8 "11":9 "12":9 

结果表明，列表中的整数被均匀选择，并且在连续的选择中没有重复相同的整数。

值得关注的点  

在大量尝试（例如，100,000 次以上）中，RandomPickerSimple会产生相当均匀的选择分布。但是，对于较少的选择次数，结果可能相当不均匀。RandomPicker试图在较少的选择次数内产生均匀的项目选择分布。

[2013 年 12 月 3 日更新]

正如许多评论者所指出的（感谢你们的评论！），这种算法在数学意义上并不是纯粹的随机算法。仅仅因为上次选择的项目在下一次选择中没有机会被选中就违反了随机性的定义。该算法有三个主要目标。

  1. 从列表中选择项目时增加一定程度的随机性
  2. 不要在连续的选择中选择相同的项目
  3. 经过多次选择后，列表中的所有项目都应该被均匀选择

包含这些类和测试的 Visual Studio 解决方案已附加到本文。

历史  

  • 首次修订。
  • 更改标题以更清晰地反映代码的目的。在兴趣点中添加了说明。
© . All rights reserved.