我需要一个快速算法从通用列表中选择5个随机元素。例如，我想从List<string>获得5个随机元素。
迭代通过并为每个元素使选择的概率=（需要的数量）/（数字左）
因此，如果您有40个项目，那么第一个项目将有5/40的机会被选中。如果是，则下一次有4/39的机会，否则它有5/39的机会。当你到达目的地时，你会得到5件物品，而且在此之前你通常会拥有所有物品。
从组中选择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时，我没有重新排序任何东西。那是因为我认为随机性应该在返回的集合中作为一个整体。我的意思是如果你想要来自1, 2, 3, 4, 5的5个随机物品，它的1, 3, 4, 2, 5或1, 2, 3, 4, 5应该无关紧要，但是如果你需要来自同一组的4个项目，那么它应该在1, 2, 3, 4，1, 3, 5, 2，2, 3, 5, 4等中不可预测地屈服。其次，当要返回的随机项目的数量超过原始组的一半，那么从组中删除source.Count - count项目比添加count项目更容易。出于性能原因，我使用source而不是sourceDict来获取remove方法中的随机索引。
因此，如果您有{1,2,3,4}，则最终可能会在{1,2,3}，{3,4,1}等3个项目中结束。
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次，那么你可能想要faster random class而不是System.Random，但我不认为这是一个大问题，考虑到后者很可能永远不会成为瓶颈，它足够快..
编辑：如果你需要重新安排退回物品的顺序，那么没有什么可以击败dhakim's Fisher-Yates approach - 简短，甜蜜和简单..
我结合上面的几个答案来创建一个Lazily评估的扩展方法。我的测试表明，Kyle的方法（Order（N））比drzaus使用一组提出随机指数选择（Order（K））慢很多倍。前者对随机数生成器执行更多调用，并且在项目上迭代次数更多。
我实施的目标是：
1）如果给出的IEnumerable不是IList，则不要实现完整列表。如果我获得了一系列物品，我不想耗尽内存。使用Kyle的方法获得在线解决方案。
2）如果我能说它是一个IList，请使用drzaus的方法，扭曲。如果K超过N的一半，我会冒险捶打，因为我一次又一次地选择了许多随机索引并且必须跳过它们。因此，我编写了一个不保留的指数列表。
3）我保证物品将按照遇到的顺序退回。凯尔的算法不需要改动。 drzaus'算法要求我不按照选择随机索引的顺序发出项目。我将所有索引收集到SortedSet中，然后按排序索引顺序发出项目。
4）如果K与N相比较大并且我反转了集合的意义，那么我枚举所有项目并测试索引是否不在集合中。这意味着我失去了Order（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＃的Random。 （FastRandom由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));
}
}
我使用的简单解决方案（可能不适合大型列表）：将列表复制到临时列表中，然后循环从临时列表中随机选择项目并将其放入选定项目列表中，同时从临时列表中删除它（因此它不能是重新选择）。
例：
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++;
}
这里有一个基于Fisher-Yates Shuffle的实现，其算法复杂度为O（n），其中n是子集或样本大小，而不是列表大小，正如John Shedletsky指出的那样。
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;
}
}
从@ 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
根据Kyle的回答，这是我的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 ;
}
这种方法可能等同于凯尔的。
假设您的列表大小为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--;
}
}
奇迹般有效 ：）
-Alex Gilbert
这是我在第一次切割时能想到的最好的：
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 - 总列表计数范围内的randoms列表，然后简单地将列表中的项目拉出来似乎是最好的方法，但使用Dictionary来确保唯一性是我仍在考虑的事情。
另请注意，我使用了字符串列表，根据需要进行替换。
为什么不是这样的：
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#
这比人们想象的要困难得多。见杰夫的great Article "Shuffling"。
我写了一篇关于该主题的非常简短的文章，包括C＃代码： Return random subset of N elements of a given array
使用linq：
YourList.OrderBy(x => rnd.Next()).Take(5)
目标：从集合源中选择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;
}
}
我最近在我的项目中使用类似于Tyler's point 1的想法做到了这一点。 我正在加载一堆问题并随机选择五个。使用IComparer实现排序。 a所有问题都加载在QuestionSorter列表中，然后使用List's Sort function和所选的前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（count2）
当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相比，我的时间大约减半（或更好）。
拥有一个大的列表将大大减少重复的几率。
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 = rand％（n-2），并做同样的事情，等等，直到你在s中有k个不同的元素。这具有最坏情况的运行时间O（k ^ 2）。所以对于k << n，这可以更快。如果你保持排序并跟踪它有哪些连续的间隔，你可以在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的数组，这里有一些伪随机：
# 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个元素的数组（索引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）运行时间。
最后，对于真正的stickler，if（n == k），你应该停在1而不是n-k，因为随机选择的整数总是0。
你可以使用它，但订购将在客户端进行
.AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
来自Dragons in the Algorithm，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对accepted answer的评论（释义）：
你应该能够在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);
}
}
}