从C＃中的List <T>中选择N个随机元素
我需要一种快速算法来从通用列表中选择5个随机元素。例如，我想从List <string>中获得5个随机元素。
解决方案
回答
遍历每个元素，使选择的概率=(所需数量)/(剩余数量)
因此，如果我们有40个项目，则第一个将有5/40的机会被选中。如果是，则下一个机会有4/39机会，否则有5/39机会。到结束时，我们将拥有5个项目，而且在此之前，我们通常都会拥有所有这些项目。
回答
这实际上是一个比听起来要难的问题，主要是因为许多数学上正确的解决方案实际上无法让我们找到所有可能(下面更多内容)。
首先，这是一些易于实现的，如果我们有一个真正的随机数生成器，则可以对其进行纠正：
(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：
# 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
我建议通过几个示例来了解如何有效地实现上述英文说明。
回答
这是我第一次尝试时能想到的最好的方法：
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来确保唯一性。
另请注意，我使用了一个字符串列表，根据需要替换。
回答
摘自《算法中的龙》(The 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>();
var needed = k;
var available = items.Count;
var rand = new Random();
while (selected.Count < k) {
if( rand.NextDouble() < needed / available ) {
selected.Add(items[available-1])
needed--;
}
available--;
}
该算法将选择项目列表的唯一索引。
回答
我最近在项目中使用了与泰勒(Tyler)第一点类似的想法。
我正在加载一堆问题，然后随机选择五个。排序是使用IComparer实现的。
a所有问题均加载到QuestionSorter列表中，然后使用列表的Sort函数和所选的前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
回答
为什么不这样呢？
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#
回答
我认为所选答案正确无误。不过，我以不同的方式实现了它，因为我也希望结果按随机顺序排列。
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);
}
回答
这比人们想象的要难得多。参见Jeff的精彩文章"洗牌"。
我确实写了一篇关于该主题的简短文章，包括Ccode：
返回给定数组的N个元素的随机子集
回答
使用linq：
YourList.OrderBy(x => rnd.Next()).Take(5)
回答
我使用的简单解决方案(可能不适用于大型列表)：
将列表复制到临时列表中，然后在循环中从临时列表中随机选择项目，并将其放入选定的项目列表中，同时将其从临时列表中删除(因此无法重新选择)。
例子：
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++;
}
回答
这是我的方法(全文位于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;
}
