从 C# 中的 List<T> 中选择 N 个随机元素

https://stackoverflow.com/questions/48087

09-06-2019
|

题

我需要一个快速算法从通用列表中选择 5 个随机元素。例如，我想从 a 中获取 5 个随机元素 List<string>.

解决方案

迭代并为每个元素做出选择的概率=（需要的数量）/（剩余的数量）

因此，如果您有 40 个项目，则第一个项目有 5/40 的机会被选中。如果是，下一个有 4/39 的机会，否则有 5/39 的机会。当你读到最后时，你将拥有 5 件物品，而且通常在此之前你就会拥有所有物品。

其他提示

使用 linq：

YourList.OrderBy(x => rnd.Next()).Take(5)

public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}

这实际上是一个比听起来更难的问题，主要是因为许多数学上正确的解决方案实际上无法让您实现所有可能性（更多内容见下文）。

首先，这里有一些易于实现的、正确的（如果你有真正的随机数生成器）：

(0) 凯尔的答案，即 O(n)。

（1）生成一个n对列表[(0, rand), (1, rand), (2, rand), ...]，按第二个坐标对它们进行排序，并使用前k个（对你来说，k =5) 索引来获取随机子集。我认为这很容易实现，尽管它是 O(n log n) 时间。

(2) 初始化一个空列表 s = []，它将增长为 k 个随机元素的索引。在{0, 1, 2, ..., n-1}中随机选择一个数字r，r = rand % n，并将其添加到s中。接下来取 r = rand % (n-1) 并插入 s；将 s 中小于它的 # 个元素添加到 r 中以避免冲突。接下来取 r = rand % (n-2)，并做同样的事情，等等。直到 s 中有 k 个不同的元素。最坏情况下的运行时间为 O(k^2)。因此，对于 k << n，这可能会更快。如果对 s 进行排序并跟踪它具有哪些连续间隔，则可以在 O(k log k) 中实现它，但需要更多工作。

@Kyle - 你是对的，再想一想我同意你的答案。我一开始匆忙地读了它，并错误地认为你是在指示以固定概率 k/n 顺序选择每个元素，这是错误的 - 但你的自适应方法对我来说似乎是正确的。对于那个很抱歉。

好的，现在来说说重点：渐进地（对于固定的 k，n 不断增长），有 n^k/k！从 n 个元素中选择 k 个元素子集[这是 (n 选择 k) 的近似值]。如果n很大，并且k不是很小，那么这些数字就很大。在任何标准 32 位随机数生成器中，您期望的最佳周期长度是 2^32 = 256^4。因此，如果我们有一个包含 1000 个元素的列表，并且我们想随机选择 5 个元素，那么标准随机数生成器不可能满足所有可能性。然而，只要您可以接受适合较小集合的选择，并且始终“看起来”随机，那么这些算法应该没问题。

附录: ：写完这篇文章后，我意识到正确实现想法（2）是很棘手的，所以我想澄清这个答案。为了获得 O(k log k) 时间，您需要一个支持 O(log m) 搜索和插入的类似数组的结构 - 平衡二叉树可以做到这一点。使用这样的结构来构建一个名为 s 的数组，下面是一些伪Python：

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

我建议运行几个示例案例，看看它如何有效地实现上述英文解释。

我认为所选的答案是正确的并且非常甜蜜。不过，我的实现方式有所不同，因为我也希望结果按随机顺序排列。

    static IEnumerable<SomeType> PickSomeInRandomOrder<SomeType>(
        IEnumerable<SomeType> someTypes,
        int maxCount)
    {
        Random random = new Random(DateTime.Now.Millisecond);

        Dictionary<double, SomeType> randomSortTable = new Dictionary<double,SomeType>();

        foreach(SomeType someType in someTypes)
            randomSortTable[random.NextDouble()] = someType;

        return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
    }

我刚刚遇到了这个问题，更多的谷歌搜索让我遇到了随机洗牌列表的问题： http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

要完全随机地洗牌您的列表（就地），您可以执行以下操作：

打乱包含 n 个元素的数组 a（索引 0..n-1）：

  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

如果您只需要前 5 个元素，则无需从 n-1 到 1 一直运行 i，而只需将其运行到 n-5（即：n-5)

假设你需要 k 件物品，

这变成：

  for (i = n − 1; i >= n-k; i--)
  {
       j = random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]
  }

所选的每个项目都会向数组末尾交换，因此所选的 k 个元素是数组的最后 k 个元素。

这需要时间 O(k)，其中 k 是您需要的随机选择元素的数量。

此外，如果您不想修改初始列表，您可以在临时列表中写下所有交换，反转该列表，然后再次应用它们，从而执行相反的交换集并在不更改的情况下返回初始列表O(k) 运行时间。

最后，对于真正的坚持者，如果 (n == k)，您应该停在 1，而不是 n-k，因为随机选择的整数将始终为 0。

您可以使用它，但排序将在客户端进行

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);

从算法中的龙, ，C# 中的解释：

int k = 10; // items to select
var items = new List<int>(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
var selected = new List<int>();
double needed = k;
double available = items.Count;
var rand = new Random();
while (selected.Count < k) {
   if( rand.NextDouble() < needed / available ) {
      selected.Add(items[(int)available-1])
      needed--;
   }
   available--;
}

该算法将选择项目列表的唯一索引。

正在考虑 @JohnShedletsky 的评论接受的答案关于（释义）：

你应该能够在 O(subset.Length) 中做到这一点，而不是 O(originalList.Length)

基本上，你应该能够生成 subset 随机索引，然后从原始列表中提取它们。

方法

public static class EnumerableExtensions {

    public static Random randomizer = new Random(); // you'd ideally be able to replace this with whatever makes you comfortable

    public static IEnumerable<T> GetRandom<T>(this IEnumerable<T> list, int numItems) {
        return (list as T[] ?? list.ToArray()).GetRandom(numItems);

        // because ReSharper whined about duplicate enumeration...
        /*
        items.Add(list.ElementAt(randomizer.Next(list.Count()))) ) numItems--;
        */
    }

    // just because the parentheses were getting confusing
    public static IEnumerable<T> GetRandom<T>(this T[] list, int numItems) {
        var items = new HashSet<T>(); // don't want to add the same item twice; otherwise use a list
        while (numItems > 0 )
            // if we successfully added it, move on
            if( items.Add(list[randomizer.Next(list.Length)]) ) numItems--;

        return items;
    }

    // and because it's really fun; note -- you may get repetition
    public static IEnumerable<T> PluckRandomly<T>(this IEnumerable<T> list) {
        while( true )
            yield return list.ElementAt(randomizer.Next(list.Count()));
    }

}

如果您想提高效率，您可能会使用 HashSet 的指数, ，而不是实际的列表元素（如果您有复杂的类型或昂贵的比较）；

单元测试

并确保我们不会发生任何碰撞等。

[TestClass]
public class RandomizingTests : UnitTestBase {
    [TestMethod]
    public void GetRandomFromList() {
        this.testGetRandomFromList((list, num) => list.GetRandom(num));
    }

    [TestMethod]
    public void PluckRandomly() {
        this.testGetRandomFromList((list, num) => list.PluckRandomly().Take(num), requireDistinct:false);
    }

    private void testGetRandomFromList(Func<IEnumerable<int>, int, IEnumerable<int>> methodToGetRandomItems, int numToTake = 10, int repetitions = 100000, bool requireDistinct = true) {
        var items = Enumerable.Range(0, 100);
        IEnumerable<int> randomItems = null;

        while( repetitions-- > 0 ) {
            randomItems = methodToGetRandomItems(items, numToTake);
            Assert.AreEqual(numToTake, randomItems.Count(),
                            "Did not get expected number of items {0}; failed at {1} repetition--", numToTake, repetitions);
            if(requireDistinct) Assert.AreEqual(numToTake, randomItems.Distinct().Count(),
                            "Collisions (non-unique values) found, failed at {0} repetition--", repetitions);
            Assert.IsTrue(randomItems.All(o => items.Contains(o)),
                        "Some unknown values found; failed at {0} repetition--", repetitions);
        }
    }
}

选择N 随机的 组中的项目不应与以下内容有任何关系命令！随机性是指不可预测性，而不是改变群体中的位置。所有处理某种排序的答案都必然比不处理排序的答案效率低。由于效率是这里的关键，因此我将发布一些不会过多改变项目顺序的内容。

1）如果您需要真的随机值，这意味着对选择哪些元素没有限制（即一旦选择了项目就可以重新选择）：

public static List<T> GetTrueRandom<T>(this IList<T> source, int count, 
                                       bool throwArgumentOutOfRangeException = true)
{
    if (throwArgumentOutOfRangeException && count > source.Count)
        throw new ArgumentOutOfRangeException();

    var randoms = new List<T>(count);
    randoms.AddRandomly(source, count);
    return randoms;
}

如果您将例外标志设置为关闭，则可以任意次数地选择随机项目。

如果您有 { 1, 2, 3, 4 }，那么它可以为 3 个项目提供 { 1, 4, 4 }、{ 1, 4, 3 } 等，甚至为 { 1, 4, 3, 2, 4 } 提供5 件！

这应该相当快，因为它没有什么需要检查的。

2）如果您需要个人如果小组成员没有重复，那么我会依靠字典（正如许多人已经指出的那样）。

public static List<T> GetDistinctRandom<T>(this IList<T> source, int count)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    if (count == source.Count)
        return new List<T>(source);

    var sourceDict = source.ToIndexedDictionary();

    if (count > source.Count / 2)
    {
        while (sourceDict.Count > count)
            sourceDict.Remove(source.GetRandomIndex());

        return sourceDict.Select(kvp => kvp.Value).ToList();
    }

    var randomDict = new Dictionary<int, T>(count);
    while (randomDict.Count < count)
    {
        int key = source.GetRandomIndex();
        if (!randomDict.ContainsKey(key))
            randomDict.Add(key, sourceDict[key]);
    }

    return randomDict.Select(kvp => kvp.Value).ToList();
}

该代码比这里的其他字典方法要长一些，因为我不仅要添加，还要从列表中删除，所以它有点两个循环。你可以在这里看到我没有 重新排序 任何事情当 count 变得等于 source.Count. 。那是因为我相信 随机性应该在 返回集 作为一个整体. 。我的意思是如果你想要的话 5 随机物品来自 1, 2, 3, 4, 5, ，如果是的话也没关系 1, 3, 4, 2, 5 或者 1, 2, 3, 4, 5, ，但如果你需要 4 来自同一组的项目，那么它应该不可预测地产生 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4 ETC。第二， 当返回的随机项数超过原始组的一半时，则更容易删除 source.Count - count 组中的项目 比添加 count 项目。出于性能原因我使用了 source 代替 sourceDict 在删除方法中获取随机索引。

因此，如果您有 { 1, 2, 3, 4 }，则 3 个项目可能会出现 { 1, 2, 3 }、{ 3, 4, 1 } 等。

3）如果您需要通过考虑原始组中的重复项来从您的组中获得真正不同的随机值，那么您可以使用与上述相同的方法，但是 HashSet 会比字典更轻。

public static List<T> GetTrueDistinctRandom<T>(this IList<T> source, int count, 
                                               bool throwArgumentOutOfRangeException = true)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    var set = new HashSet<T>(source);

    if (throwArgumentOutOfRangeException && count > set.Count)
        throw new ArgumentOutOfRangeException();

    List<T> list = hash.ToList();

    if (count >= set.Count)
        return list;

    if (count > set.Count / 2)
    {
        while (set.Count > count)
            set.Remove(list.GetRandom());

        return set.ToList();
    }

    var randoms = new HashSet<T>();
    randoms.AddRandomly(list, count);
    return randoms.ToList();
}

这 randoms 变量被设为 HashSet 以避免在最罕见的情况下添加重复项 Random.Next 可以产生相同的值，特别是当输入列表很小时。

所以 { 1, 2, 2, 4 } => 3 个随机项 => { 1, 2, 4 } 而不是 { 1, 2, 2}

{ 1, 2, 2, 4 } => 4 个随机项目 => 例外！！或 { 1, 2, 4 }，具体取决于标志设置。

我使用过的一些扩展方法：

static Random rnd = new Random();
public static int GetRandomIndex<T>(this ICollection<T> source)
{
    return rnd.Next(source.Count);
}

public static T GetRandom<T>(this IList<T> source)
{
    return source[source.GetRandomIndex()];
}

static void AddRandomly<T>(this ICollection<T> toCol, IList<T> fromList, int count)
{
    while (toCol.Count < count)
        toCol.Add(fromList.GetRandom());
}

public static Dictionary<int, T> ToIndexedDictionary<T>(this IEnumerable<T> lst)
{
    return lst.ToIndexedDictionary(t => t);
}

public static Dictionary<int, T> ToIndexedDictionary<S, T>(this IEnumerable<S> lst, 
                                                           Func<S, T> valueSelector)
{
    int index = -1;
    return lst.ToDictionary(t => ++index, valueSelector);
}

如果这一切都与性能有关，列表中的数千个项目必须迭代 10000 次，那么您可能想要更快的随机类比 System.Random, ，但我认为这没什么大不了的，因为后者很可能永远不是瓶颈，它足够快。

编辑： 如果您还需要重新安排退货的顺序，那么没有什么比这更好的了达基姆的费舍尔-耶茨方法 - 简短、甜蜜、简单..

我使用的简单解决方案（可能不适用于大型列表）：将列表复制到临时列表中，然后在循环中随机从临时列表中选择项目并将其放入选定项目列表中，同时将其从临时列表中删除（因此无法重新选择）。

例子：

List<Object> temp = OriginalList.ToList();
List<Object> selectedItems = new List<Object>();
Random rnd = new Random();
Object o;
int i = 0;
while (i < NumberOfSelectedItems)
{
            o = temp[rnd.Next(temp.Count)];
            selectedItems.Add(o);
            temp.Remove(o);
            i++;
 }

我结合了上面的几个答案来创建一个延迟评估的扩展方法。我的测试表明，Kyle 的方法 (Order(N)) 比 drzaus 使用一组来提出要选择的随机索引 (Order(K)) 慢很多倍。前者对随机数生成器执行更多的调用，并且对项目进行更多的迭代。

我的实施目标是：

1) 如果给定的 IEnumerable 不是 IList，则不会实现完整列表。如果给我一个包含无数项的序列，我不想耗尽内存。使用凯尔的方法来获得在线解决方案。

2）如果我能看出它是一个 IList，请使用 drzaus 的方法，但要稍作修改。如果 K 超过 N 的一半，我就会面临崩溃的风险，因为我一次又一次地选择许多随机索引，并且不得不跳过它们。因此，我编写了一个不保留的索引列表。

3) 我保证物品将按照遇到的顺序退回。凯尔的算法不需要改变。drzaus 的算法要求我不按照选择随机索引的顺序发出项目。我将所有索引收集到一个 SortedSet 中，然后按排序索引顺序发出项目。

4）如果K比N大并且我反转集合的意义，那么我枚举所有项目并测试索引是否不在集合中。这意味着我丢失了（k）运行时间，但是由于k在这些情况下接近n，所以我不会损失太多。

这是代码：

    /// <summary>
    /// Takes k elements from the next n elements at random, preserving their order.
    /// 
    /// If there are fewer than n elements in items, this may return fewer than k elements.
    /// </summary>
    /// <typeparam name="TElem">Type of element in the items collection.</typeparam>
    /// <param name="items">Items to be randomly selected.</param>
    /// <param name="k">Number of items to pick.</param>
    /// <param name="n">Total number of items to choose from.
    /// If the items collection contains more than this number, the extra members will be skipped.
    /// If the items collection contains fewer than this number, it is possible that fewer than k items will be returned.</param>
    /// <returns>Enumerable over the retained items.
    /// 
    /// See http://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c-sharp for the commentary.
    /// </returns>
    public static IEnumerable<TElem> TakeRandom<TElem>(this IEnumerable<TElem> items, int k, int n)
    {
        var r = new FastRandom();
        var itemsList = items as IList<TElem>;

        if (k >= n || (itemsList != null && k >= itemsList.Count))
            foreach (var item in items) yield return item;
        else
        {  
            // If we have a list, we can infer more information and choose a better algorithm.
            // When using an IList, this is about 7 times faster (on one benchmark)!
            if (itemsList != null && k < n/2)
            {
                // Since we have a List, we can use an algorithm suitable for Lists.
                // If there are fewer than n elements, reduce n.
                n = Math.Min(n, itemsList.Count);

                // This algorithm picks K index-values randomly and directly chooses those items to be selected.
                // If k is more than half of n, then we will spend a fair amount of time thrashing, picking
                // indices that we have already picked and having to try again.   
                var invertSet = k >= n/2;  
                var positions = invertSet ? (ISet<int>) new HashSet<int>() : (ISet<int>) new SortedSet<int>();

                var numbersNeeded = invertSet ? n - k : k;
                while (numbersNeeded > 0)
                    if (positions.Add(r.Next(0, n))) numbersNeeded--;

                if (invertSet)
                {
                    // positions contains all the indices of elements to Skip.
                    for (var itemIndex = 0; itemIndex < n; itemIndex++)
                    {
                        if (!positions.Contains(itemIndex))
                            yield return itemsList[itemIndex];
                    }
                }
                else
                {
                    // positions contains all the indices of elements to Take.
                    foreach (var itemIndex in positions)
                        yield return itemsList[itemIndex];              
                }
            }
            else
            {
                // Since we do not have a list, we will use an online algorithm.
                // This permits is to skip the rest as soon as we have enough items.
                var found = 0;
                var scanned = 0;
                foreach (var item in items)
                {
                    var rand = r.Next(0,n-scanned);
                    if (rand < k - found)
                    {
                        yield return item;
                        found++;
                    }
                    scanned++;
                    if (found >= k || scanned >= n)
                        break;
                }
            }
        }  
    }

我使用专门的随机数生成器，但你可以使用 C# 的 随机的 如果你想。（快速随机 由 Colin Green 编写，是 SharpNEAT 的一部分。它的周期为 2^128-1，比许多 RNG 都要好。）

以下是单元测试：

[TestClass]
public class TakeRandomTests
{
    /// <summary>
    /// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_Array_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials/20;
        var timesChosen = new int[100];
        var century = new int[100];
        for (var i = 0; i < century.Length; i++)
            century[i] = i;

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in century.TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount/100;
        AssertBetween(avg, expectedCount - 2, expectedCount + 2, "Average");
        //AssertBetween(min, expectedCount - allowedDifference, expectedCount, "Min");
        //AssertBetween(max, expectedCount, expectedCount + allowedDifference, "Max");

        var countInRange = timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    /// <summary>
    /// Ensure that when randomly choosing items from an IEnumerable that is not an IList, 
    /// all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_IEnumerable_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials / 20;
        var timesChosen = new int[100];

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in Range(0,100).TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount / 100;
        var countInRange =
            timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    private IEnumerable<int> Range(int low, int count)
    {
        for (var i = low; i < low + count; i++)
            yield return i;
    }

    private static void AssertBetween(int x, int low, int high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }

    private static void AssertBetween(double x, double low, double high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }
}

这里你有一个基于的实现费舍尔-耶茨洗牌正如 John Shedletsky 指出的，其算法复杂度为 O(n)，其中 n 是子集或样本大小，而不是列表大小。

public static IEnumerable<T> GetRandomSample<T>(this IList<T> list, int sampleSize)
{
    if (list == null) throw new ArgumentNullException("list");
    if (sampleSize > list.Count) throw new ArgumentException("sampleSize may not be greater than list count", "sampleSize");
    var indices = new Dictionary<int, int>(); int index;
    var rnd = new Random();

    for (int i = 0; i < sampleSize; i++)
    {
        int j = rnd.Next(i, list.Count);
        if (!indices.TryGetValue(j, out index)) index = j;

        yield return list[index];

        if (!indices.TryGetValue(i, out index)) index = i;
        indices[j] = index;
    }
}

根据凯尔的回答，这是我的 C# 实现。

/// <summary>
/// Picks random selection of available game ID's
/// </summary>
private static List<int> GetRandomGameIDs(int count)
{       
    var gameIDs = (int[])HttpContext.Current.Application["NonDeletedArcadeGameIDs"];
    var totalGameIDs = gameIDs.Count();
    if (count > totalGameIDs) count = totalGameIDs;

    var rnd = new Random();
    var leftToPick = count;
    var itemsLeft = totalGameIDs;
    var arrPickIndex = 0;
    var returnIDs = new List<int>();
    while (leftToPick > 0)
    {
        if (rnd.Next(0, itemsLeft) < leftToPick)
        {
            returnIDs .Add(gameIDs[arrPickIndex]);
            leftToPick--;
        }
        arrPickIndex++;
        itemsLeft--;
    }

    return returnIDs ;
}

这个方法可能和Kyle的方法是等价的。

假设您的列表大小为 n 并且您需要 k 个元素。

Random rand = new Random();
for(int i = 0; k>0; ++i) 
{
    int r = rand.Next(0, n-i);
    if(r<k) 
    {
        //include element i
        k--;
    }
}

奇迹般有效：）

——亚历克斯·吉尔伯特

从@ers的答案延伸，如果有人担心 OrderBy 可能有不同的实现，那么这应该是安全的：

// Instead of this
YourList.OrderBy(x => rnd.Next()).Take(5)

// Temporarily transform 
YourList
    .Select(v => new {v, i = rnd.Next()}) // Associate a random index to each entry
    .OrderBy(x => x.i).Take(5) // Sort by (at this point fixed) random index 
    .Select(x => x.v); // Go back to enumerable of entry

这是我在第一次剪辑时能想到的最好的：

public List<String> getRandomItemsFromList(int returnCount, List<String> list)
{
    List<String> returnList = new List<String>();
    Dictionary<int, int> randoms = new Dictionary<int, int>();

    while (randoms.Count != returnCount)
    {
        //generate new random between one and total list count
        int randomInt = new Random().Next(list.Count);

        // store this in dictionary to ensure uniqueness
        try
        {
            randoms.Add(randomInt, randomInt);
        }
        catch (ArgumentException aex)
        {
            Console.Write(aex.Message);
        } //we can assume this element exists in the dictonary already 

        //check for randoms length and then iterate through the original list 
        //adding items we select via random to the return list
        if (randoms.Count == returnCount)
        {
            foreach (int key in randoms.Keys)
                returnList.Add(list[randoms[key]]);

            break; //break out of _while_ loop
        }
    }

    return returnList;
}

使用 1 - 总列表计数范围内的随机列表，然后简单地将这些项目拉到列表中似乎是最好的方法，但使用字典来确保唯一性是我仍在考虑的事情。

另请注意，我使用了字符串列表，请根据需要进行替换。

为什么不是这样的：

 Dim ar As New ArrayList
    Dim numToGet As Integer = 5
    'hard code just to test
    ar.Add("12")
    ar.Add("11")
    ar.Add("10")
    ar.Add("15")
    ar.Add("16")
    ar.Add("17")

    Dim randomListOfProductIds As New ArrayList

    Dim toAdd As String = ""
    For i = 0 To numToGet - 1
        toAdd = ar(CInt((ar.Count - 1) * Rnd()))

        randomListOfProductIds.Add(toAdd)
        'remove from id list
        ar.Remove(toAdd)

    Next
'sorry i'm lazy and have to write vb at work :( and didn't feel like converting to c#

这比人们想象的要困难得多。请参阅很棒的文章“洗牌” 来自杰夫.

我确实写了一篇关于该主题的非常短的文章，其中包括 C# 代码：
返回给定数组的 N 个元素的随机子集

目标：从集合源中选择N个不重复的项目。我为任何通用集合创建了一个扩展。我是这样做的：

public static class CollectionExtension
{
    public static IList<TSource> RandomizeCollection<TSource>(this IList<TSource> source, int maxItems)
    {
        int randomCount = source.Count > maxItems ? maxItems : source.Count;
        int?[] randomizedIndices = new int?[randomCount];
        Random random = new Random();

        for (int i = 0; i < randomizedIndices.Length; i++)
        {
            int randomResult = -1;
            while (randomizedIndices.Contains((randomResult = random.Next(0, source.Count))))
            {
                //0 -> since all list starts from index 0; source.Count -> maximum number of items that can be randomize
                //continue looping while the generated random number is already in the list of randomizedIndices
            }

            randomizedIndices[i] = randomResult;
        }

        IList<TSource> result = new List<TSource>();
        foreach (int index in randomizedIndices)
            result.Add(source.ElementAt(index));

        return result;
    }
}

我最近在我的项目中使用了类似的想法泰勒的观点1.
我加载了一堆问题并随机选择了五个。排序是使用比较器.
a所有问题均加载到 QuestionSorter 列表中，然后使用列表的排序功能以及选择的前 k 个元素。

    private class QuestionSorter : IComparable<QuestionSorter>
    {
        public double SortingKey
        {
            get;
            set;
        }

        public Question QuestionObject
        {
            get;
            set;
        }

        public QuestionSorter(Question q)
        {
            this.SortingKey = RandomNumberGenerator.RandomDouble;
            this.QuestionObject = q;
        }

        public int CompareTo(QuestionSorter other)
        {
            if (this.SortingKey < other.SortingKey)
            {
                return -1;
            }
            else if (this.SortingKey > other.SortingKey)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }

用法：

    List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();

    // add the questions here

    unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);

    // select the first k elements

这是我的方法（全文在这里 http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

它应该以 O(K) 而不是 O(N) 的速度运行，其中 K 是所需元素的数量，N 是可供选择的列表的大小：

public <T> List<T> take(List<T> source, int k) {
 int n = source.size();
 if (k > n) {
   throw new IllegalStateException(
     "Can not take " + k +
     " elements from a list with " + n +
     " elements");
 }
 List<T> result = new ArrayList<T>(k);
 Map<Integer,Integer> used = new HashMap<Integer,Integer>();
 int metric = 0;
 for (int i = 0; i < k; i++) {
   int off = random.nextInt(n - i);
   while (true) {
     metric++;
     Integer redirect = used.put(off, n - i - 1);
     if (redirect == null) {
       break;
     }
     off = redirect;
   }
   result.add(source.get(off));
 }
 assert metric <= 2*k;
 return result;
}

这不像公认的解决方案那么优雅或高效，但它很快就能写出来。首先，随机排列数组，然后选择前 K 个元素。在Python中，

import numpy

N = 20
K = 5

idx = np.arange(N)
numpy.random.shuffle(idx)

print idx[:K]

我会使用扩展方法。

    public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> elements, int countToTake)
    {
        var random = new Random();

        var internalList = elements.ToList();

        var selected = new List<T>();
        for (var i = 0; i < countToTake; ++i)
        {
            var next = random.Next(0, internalList.Count - selected.Count);
            selected.Add(internalList[next]);
            internalList[next] = internalList[internalList.Count - selected.Count];
        }
        return selected;
    }

public static IEnumerable<T> GetRandom<T>(this IList<T> list, int count, Random random)
    {
        // Probably you should throw exception if count > list.Count
        count = Math.Min(list.Count, count);

        var selectedIndices = new SortedSet<int>();

        // Random upper bound
        int randomMax = list.Count - 1;

        while (selectedIndices.Count < count)
        {
            int randomIndex = random.Next(0, randomMax);

            // skip over already selected indeces
            foreach (var selectedIndex in selectedIndices)
                if (selectedIndex <= randomIndex)
                    ++randomIndex;
                else
                    break;

            yield return list[randomIndex];

            selectedIndices.Add(randomIndex);
            --randomMax;
        }
    }

记忆：〜计数
复杂：O(计数²)

当 N 非常大时，随机打乱 N 个数字并选择前 k 个数字的常规方法可能会因空间复杂性而难以实现。以下算法仅需要 O(k) 的时间和空间复杂度。

http://arxiv.org/abs/1512.00501

def random_selection_indices(num_samples, N):
    modified_entries = {}
    seq = []
    for n in xrange(num_samples):
        i = N - n - 1
        j = random.randrange(i)

        # swap a[j] and a[i] 
        a_j = modified_entries[j] if j in modified_entries else j 
        a_i = modified_entries[i] if i in modified_entries else i

        if a_i != j:
            modified_entries[j] = a_i   
        elif j in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(j)

        if a_j != i:
            modified_entries[i] = a_j 
        elif i in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(i)
        seq.append(a_j)
    return seq

将 LINQ 与大型列表一起使用（当触摸每个元素的成本很高时）并且如果您可以忍受重复的可能性：

new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))

对于我的使用，我有一个包含 100.000 个元素的列表，由于它们是从数据库中提取的，因此与整个列表上的 rnd 相比，我的时间大约减少了一半（或更好）。

拥有一个大列表将大大减少重复的可能性。

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow