关于算法：从C＃中的List < T >中选择N个随机元素

Select N random elements from a List in C#

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

使用linq：

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

遍历每个元素，使每个元素的选择概率=(所需数量)/(剩余数量)

因此，如果您有40个项目，则第一个将有5/40的机会被选中。如果是，那么下一个机会就有4/39机会，否则就有5/39机会。到结束时，您将拥有5件商品，而且通常在此之前都拥有它们。

1
2
3
4

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；向r添加＃个元素，使其小于s个元素，以免发生冲突。接下来取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：

1
2
3
4
5
6
7

# 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

我建议通过几个示例来了解如何有效地实现上述英文说明。

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

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

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

我只是遇到了这个问题，更多的Google搜索使我陷入了随机改组列表的问题：http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

要完全随机地(按位置)随机排列列表，请执行以下操作：

随机排列n个元素的数组a(索引0..n-1)：

1
2
3

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

如果只需要前5个元素，则无需将i从n-1一直运行到1，只需将其运行到n-5(即n-5)即可。

假设您需要k项，

变成：

1
2
3
4
5

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)运行时间。

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

您可以使用它，但是订购将在客户端进行

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

摘自《算法中的龙》，C＃中的一种解释：

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

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对有关(释义)的已接受答案的评论：

you should be able to to this in O(subset.Length), rather than O(originalList.Length)

基本上，您应该能够生成subset随机索引，然后将其从原始列表中删除。

方法

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
27
28
29
30

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，而不是实际的列表元素(以防复杂类型或昂贵的比较)。

单元测试

并确保我们没有任何碰撞等。

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
27

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

我结合以上几个答案来创建一个Lazily评估的扩展方法。我的测试表明，凯尔(Order(N))的方法比drzaus使用集合提议随机索引以选择(Order(K))慢许多倍。前者对随机数生成器执行更多调用，并对这些项进行更多次迭代。

我实施的目标是：

1)如果给定的不是IList的IEnumerable，则不要实现完整列表。如果给我一系列不计其数的项目，则我不想耗尽内存。使用Kyle的方法获得在线解决方案。

2)如果我可以确定它是一个IList，请使用drzaus的方法。如果K大于N的一半，我会冒着重击的风险，因为我一次又一次选择许多随机索引，而不得不跳过它们。因此，我编写了一个索引列表以不保存。

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

4)如果K比N大，并且我颠倒了集合的含义，那么我将列举所有项目并测试索引是否不在集合中。这意味着
我损失了Order(K)运行时间，但是由于在这种情况下K接近N，因此我的损失不大。

这是代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/// <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＃的Random。 (FastRandom由Colin Green编写，是SharpNEAT的一部分。它的周期为2 ^ 128-1，比许多RNG都要好。)

以下是单元测试：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

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

从组中选择N个随机项目与订单无关！随机性与不可预测性有关，而不与组中的混洗位置有关。处理某种排序的所有答案必然效率不高。由于效率是关键，因此我将发布一些不会改变项目顺序的东西。

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

1
2
3
4
5
6
7
8
9
10

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

如果将异常标志设置为关闭，则可以任意次数选择随机项。

If you have { 1, 2, 3, 4 }, then it can give { 1, 4, 4 }, { 1, 4, 3 } etc for 3 items or even { 1, 4, 3, 2, 4 } for 5 items!

这应该非常快，因为它无需检查。

2)如果您需要不重复的小组成员，那么我将依靠词典(正如许多人已经指出的那样)。

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
27
28

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时，我什么都没有重新排序。那是因为我相信随机性应该在整个返回集合中。我的意思是，如果您要从1, 2, 3, 4, 5中获得5个随机项，那么它的1, 3, 4, 2, 5还是1, 2, 3, 4, 5都没关系，但是如果您需要同一集合中的4个项目，那么它在1, 2, 3, 4中的产量应该是不可预测的，<其次，当要返回的随机项目数超过原始组的一半时，从组中删除source.Count - count项比添加count项更容易。出于性能原因，我使用了source而不是sourceDict来获取remove方法中的随机索引。

So if you have { 1, 2, 3, 4 }, this can end up in { 1, 2, 3 }, { 3, 4, 1 } etc for 3 items.

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

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
27
28

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可以产生相同值的最罕见情况下(特别是在输入列表较小时)添加重复项。

So { 1, 2, 2, 4 } => 3 random items => { 1, 2, 4 } and never { 1, 2, 2}

{ 1, 2, 2, 4 } => 4 random items => exception!! or { 1, 2, 4 } depending on the flag set.

我使用的一些扩展方法：

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
27
28

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 lst,
Func<S, T> valueSelector)
{
int index = -1;
return lst.ToDictionary(t => ++index, valueSelector);
}

如果它的性能与列表中的数千个项目必须重复进行10000次，那么您可能想拥有比System.Random更快的随机类，但是考虑到后者，我认为这没什么大不了的永远不会成为瓶颈，它足够快。

编辑：如果您还需要重新安排退货的顺序，那么没有什么可以比dhakim的Fisher-Yates方法更好的了-简短，甜美和简单。

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

例：

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

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

从@ers的答案扩展，如果您担心OrderBy的不同实现可能会很安全：

1
2
3
4
5
6
7
8

// 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

在这里，您有一个基于Fisher-Yates Shuffle的实现，其算法复杂度为O(n)，其中n是子集或样本大小，而不是列表大小，如John Shedletsky所指出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

此方法可能等效于Kyle。

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

1
2
3
4
5
6
7
8
9
10

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

奇迹般有效：)

-亚历克斯·吉尔伯特

基于Kyle的回答，这是我的c＃实现。

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
27

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

目标：从收集源中选择N个项目，而不重复。
我为任何通用集合创建了扩展。这是我的操作方式：

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
27

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
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
27
28
29
30
31
32
33

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-列表总数之内的随机列表，然后简单地拉出列表中的那些项似乎是最好的方法，但是我仍然在考虑使用Dictionary来确保唯一性。

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

为什么不这样呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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#

这比人们想象的要难得多。参见Jeff的精彩文章"洗牌"。

我确实写了一篇有关C＃代码的简短文章：
返回给定数组的N个元素的随机子集

我最近在项目中使用了与泰勒(Tyler)第一点类似的想法。
我正在加载一堆问题，然后随机选择五个。使用IComparer实现了排序。
a所有问题均加载到QuestionSorter列表中，然后使用列表的Sort函数和所选的前k个元素对其进行排序。

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
27
28
29
30
31
32
33
34
35
36

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

用法：

1
2
3
4
5
6
7

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是要选择的列表的大小：

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

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
27

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

内存：?count
复杂度：O(count2)

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

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

就我的使用而言，我有一个100.000个元素的列表，并且由于它们是从数据库中提取的，因此与整个列表中的rnd相比，我的时间减少了一半(或更好)。

拥有大量清单将大大减少重复的几率。

我会使用扩展方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

这不像公认的解决方案那样优雅或高效，但是可以很快地编写出来。首先，随机排列数组，然后选择前K个元素。在python中，

1
2
3
4
5
6
7
8
9

import numpy

N = 20
K = 5

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

print idx[:K]

当N非常大时，由于空间的复杂性，随机洗净N个数字并选择第一个k个数字的常规方法可能会被禁止。对于时间和空间复杂度，以下算法仅需要O(k)。

http://arxiv.org/abs/1512.00501

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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