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

Question

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

c#algorithmcollectionsrandomelement

208

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

- JC Grubbs

15

“随机”一词是否包含重复选择？换句话说，同一个元素是否可以被多次选中？（真正的随机）或者一旦选择了一个元素，该元素是否应从可用池中删除，不能再次选择？ - Pretzel

你只是洗牌并取前N个..为什么这里会有这么多讨论？ - Fattie

被接受的答案并非完全错误，甚至不算错。请参见此处：https://dev59.com/N5Pfa4cB1Zd3GeqPEIJc。即使未提及，用例考虑也不是无关紧要的。 - uckelman

嗨@uckelman，干杯，已经有大量的讨论指出了明显的问题；蓄水池抽样仅在某些领域（实际上，在维基百科文章的第二个当前句子中完全概述）中有用。所提出的问题特别是关于C#中的List<string>，用户特别想要一个快速简单的解决方案。（显然，答案是排序并取五个。如果您在领域内做任何其他事情，那将是极其糟糕的工程。请注意，当然可以编造... - Fattie

...正在使用Hadoop和GPU或其他技术，然后在那个领域里，您需要分析哪种（正如您所说）蓄水池抽样方法（其中包括许多方法，并且仍在不断研究中）最好。更具体地说，看看选定的“答案”。假设这是一个实际项目，比如Nintendo的游戏团队之类的。场地上有“40”辆坦克，必须随机选择5辆。其中一名程序员开始编写该解决方案-他们只会被立即解雇！天哪。不当的工程设计是极其糟糕的工程设计。 - Fattie

显示剩余9条评论

35个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cameron A. Ellis · Answer 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#

- Kvam · Answer 2

我会使用扩展方法。

    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;
    }

- Dai · Answer 3

当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

- user6574009 · Answer 4

public static IEnumerable<Element> GetRandomElements(this IList<Element> list, int n)
{
    var count = list.Count();
    if (count < n)
    {
        throw new Exception("n cannot be bigger than the list size.");
    }
    var indexes = new HashSet<int>();
    while (set.Count < n)
    {
        indexes.Add(Random.Next(count));
    }
    return indexes.Select(x => list[x]);
}

我使用这个作为参考：数组与列表的性能比较

实现还可以，因为列表足够快以通过id获取元素。

"随机"在方法范围之外定义，Hashset确保每个索引的唯一性。

限制：如果列表很大而n很小，则算法效果更好。否则，由于冲突，while循环可能需要很长时间。

在这种情况下使用

public static IEnumerable<Element> GetRandomElements(this IList<Element> list, int n)
{
    return list.OrderBy(x => Random.Next()).Take(n);
}

可能是一个可用的选项

- Cyrille · Answer 5

这将解决您的问题

var entries=new List<T>();
var selectedItems = new List<T>();


                for (var i = 0; i !=10; i++)
                {
                    var rdm = new Random().Next(entries.Count);
                        while (selectedItems.Contains(entries[rdm]))
                            rdm = new Random().Next(entries.Count);

                    selectedItems.Add(entries[rdm]);
                }