Selecione N elementos aleatórios de um List<T> em C#
https://stackoverflow.com/questions/48087
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Preciso de um algoritmo rápido para selecionar 5 elementos aleatórios de uma lista genérica.Por exemplo, gostaria de obter 5 elementos aleatórios de um List<string>.
Solução
Itere e para cada elemento faça a probabilidade de seleção = (número necessário)/(número restante)
Portanto, se você tivesse 40 itens, o primeiro teria 5/40 de chance de ser selecionado.Se for, o próximo tem 4/39 de chance, caso contrário, tem 5/39 de chance.Quando chegar ao final, você terá seus 5 itens e, muitas vezes, terá todos eles antes disso.
Outras dicas
Usando 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();
}
Na verdade, este é um problema mais difícil do que parece, principalmente porque muitas soluções matematicamente corretas não permitirão que você alcance todas as possibilidades (mais sobre isso abaixo).
Primeiro, aqui estão alguns geradores de números verdadeiramente aleatórios, fáceis de implementar e corretos:
(0) A resposta de Kyle, que é O(n).
(1) Gere uma lista de n pares [(0, rand), (1, rand), (2, rand), ...], classifique-os pela segunda coordenada e use o primeiro k (para você, k =5) índices para obter seu subconjunto aleatório.Acho que isso é fácil de implementar, embora seja o tempo O(n log n).
(2) Inicie uma lista vazia s = [] que crescerá para ser os índices de k elementos aleatórios.Escolha um número r em {0, 1, 2, ..., n-1} aleatoriamente, r = rand% n, e adicione-o a s.Em seguida, pegue r = rand% (n-1) e insira s;adicione a r os # elementos menores que em s para evitar colisões.Em seguida, pegue r = rand% (n-2) e faça a mesma coisa, etc.até que você tenha k elementos distintos em s.Isso tem o tempo de execução do pior caso O (k ^ 2).Portanto, para k << n, isso pode ser mais rápido.Se você mantiver s classificado e rastrear quais intervalos contíguos ele possui, poderá implementá-lo em O (k log k), mas é mais trabalhoso.
@Kyle - você está certo, pensando bem, concordo com sua resposta.Eu li apressadamente no início e pensei erroneamente que você estava indicando a escolha sequencial de cada elemento com probabilidade fixa k/n, o que estaria errado - mas sua abordagem adaptativa parece correta para mim.Desculpe por isso.
Ok, e agora para o kicker:assintoticamente (para crescimento k, n fixo), existem n^k/k!escolhas de k subconjunto de elementos de n elementos [esta é uma aproximação de (n escolha k)].Se n for grande e k não for muito pequeno, esses números serão enormes.A melhor duração de ciclo que você pode esperar em qualquer gerador de números aleatórios padrão de 32 bits é 2 ^ 32 = 256 ^ 4.Portanto, se tivermos uma lista de 1.000 elementos e quisermos escolher 5 aleatoriamente, não há como um gerador de números aleatórios padrão atingir todas as possibilidades.No entanto, contanto que você esteja de acordo com uma escolha que funciona bem para conjuntos menores e sempre "parece" aleatória, esses algoritmos devem funcionar bem.
Termo aditivo:Depois de escrever isso, percebi que é complicado implementar a ideia (2) corretamente, então gostaria de esclarecer esta resposta.Para obter o tempo O(k log k), você precisa de uma estrutura semelhante a um array que suporte pesquisas e inserções O(log m) - uma árvore binária balanceada pode fazer isso.Usando essa estrutura para construir um array chamado s, aqui está um pseudopython:
# 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
Sugiro analisar alguns exemplos de casos para ver como isso implementa com eficiência a explicação em inglês acima.
Acho que a resposta selecionada está correta e muito gentil.Eu implementei de forma diferente, pois também queria o resultado em ordem aleatória.
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);
}
Acabei de me deparar com esse problema, e mais algumas pesquisas no Google me levaram ao problema de embaralhar aleatoriamente uma lista: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Para embaralhar sua lista de forma completamente aleatória (no lugar), faça o seguinte:
Para embaralhar uma matriz a de n elementos (índices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
Se você precisar apenas dos primeiros 5 elementos, em vez de executar i de n-1 a 1, você só precisará executá-lo até n-5 (ou seja:n-5)
Digamos que você precise de k itens,
Isso se torna:
for (i = n − 1; i >= n-k; i--)
{
j = random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
}
Cada item selecionado é trocado no final da matriz, de modo que os k elementos selecionados são os últimos k elementos da matriz.
Isso leva um tempo O(k), onde k é o número de elementos selecionados aleatoriamente de que você precisa.
Além disso, se não quiser modificar sua lista inicial, você pode anotar todas as suas trocas em uma lista temporária, reverter essa lista e aplicá-las novamente, realizando assim o conjunto inverso de trocas e retornando sua lista inicial sem alterar o tempo de execução O(k).
Finalmente, para o defensor real, se (n == k), você deve parar em 1, não em n-k, pois o número inteiro escolhido aleatoriamente será sempre 0.
Você pode usar isso, mas o pedido acontecerá no lado do cliente
.AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
De Dragões no Algoritmo, uma interpretação em 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--;
}
Este algoritmo selecionará índices exclusivos da lista de itens.
Estava pensando no comentário de @JohnShedletsky no resposta aceita sobre (paráfrase):
você deve ser capaz de fazer isso em O (subset.Length), em vez de O (originalList.Length)
Basicamente, você deve ser capaz de gerar subset índices aleatórios e, em seguida, retirá-los da lista original.
O método
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()));
}
}
Se você quisesse ser ainda mais eficiente, provavelmente usaria um HashSet do índices, não os elementos reais da lista (caso você tenha tipos complexos ou comparações caras);
O teste de unidade
E para ter certeza de que não teremos colisões, etc.
[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);
}
}
}
Selecionando N aleatório itens de um grupo não devem ter nada a ver com ordem!A aleatoriedade tem a ver com imprevisibilidade e não com a mudança de posições em um grupo.Todas as respostas que lidam com algum tipo de ordem serão menos eficientes do que aquelas que não o fazem.Como a eficiência é a chave aqui, vou postar algo que não altere muito a ordem dos itens.
1) Se você precisar verdadeiro valores aleatórios, o que significa que não há restrição sobre quais elementos escolher (ou seja, uma vez escolhido o item pode ser selecionado novamente):
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;
}
Se você desativar o sinalizador de exceção, poderá escolher itens aleatórios quantas vezes quiser.
Se você tiver {1, 2, 3, 4}, então pode dar {1, 4, 4}, {1, 4, 3} etc para 3 itens ou até mesmo {1, 4, 3, 2, 4} para 5 itens!
Isso deve ser bem rápido, pois não há nada para verificar.
2) Se você precisar Individual membros do grupo sem repetição, então eu confiaria em um dicionário (como muitos já apontaram).
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();
}
O código é um pouco mais longo do que outras abordagens de dicionário aqui porque não estou apenas adicionando, mas também removendo da lista, então são dois loops.Você pode ver aqui que eu não reordenado qualquer coisa quando count torna-se igual a source.Count.Isso é porque eu acredito a aleatoriedade deve estar no conjunto retornado como um todo.Quero dizer, se você quiser 5 itens aleatórios de 1, 2, 3, 4, 5, não deveria importar se é 1, 3, 4, 2, 5 ou 1, 2, 3, 4, 5, mas se você precisar 4 itens do mesmo conjunto, então ele deve render imprevisivelmente em 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4 etc.Em segundo lugar, quando a contagem de itens aleatórios a serem retornados for superior à metade do grupo original, será mais fácil removê-los source.Count - count itens do grupo do que adicionar count Unid.Por razões de desempenho, usei source em vez de sourceDict para obter o índice aleatório no método remove.
Então, se você tiver {1, 2, 3, 4}, isso pode acabar em {1, 2, 3}, {3, 4, 1} etc. para 3 itens.
3) Se você precisar de valores aleatórios verdadeiramente distintos do seu grupo, levando em consideração as duplicatas no grupo original, poderá usar a mesma abordagem acima, mas um HashSet será mais leve que um dicionário.
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();
}
O randoms variável é transformada em HashSet para evitar que duplicatas sejam adicionadas nos casos mais raros em que Random.Next pode produzir o mesmo valor, especialmente quando a lista de entrada é pequena.
Então {1, 2, 2, 4} => 3 itens aleatórios => {1, 2, 4} e nunca {1, 2, 2}
{ 1, 2, 2, 4 } => 4 itens aleatórios => exceção!!ou {1, 2, 4} dependendo do sinalizador definido.
Alguns dos métodos de extensão que usei:
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);
}
Se é tudo uma questão de desempenho com dezenas de milhares de itens na lista tendo que ser iterados 10.000 vezes, então você pode querer ter classe aleatória mais rápida que System.Random, mas não acho que isso seja grande coisa, considerando que o último provavelmente nunca é um gargalo, é bastante rápido.
Editar: Se você também precisar reorganizar a ordem dos itens devolvidos, não há nada que possa superar Abordagem Fisher-Yates de dhakim - curto, doce e simples..
A solução simples que uso (provavelmente não é boa para listas grandes):Copie a lista para a lista temporária e, em loop, selecione aleatoriamente o item da lista temporária e coloque-o na lista de itens selecionados enquanto o remove da lista temporária (para que não possa ser selecionado novamente).
Exemplo:
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++;
}
Combinei várias das respostas acima para criar um método de extensão avaliado preguiçosamente.Meus testes mostraram que a abordagem de Kyle (Order(N)) é muitas vezes mais lenta do que o uso de um conjunto por drzaus para propor os índices aleatórios a serem escolhidos (Order(K)).O primeiro realiza muito mais chamadas para o gerador de números aleatórios, além de iterar mais vezes sobre os itens.
Os objetivos da minha implementação foram:
1) Não realize a lista completa se receber um IEnumerable que não seja um IList.Se eu receber uma sequência de um zilhão de itens, não quero ficar sem memória.Use a abordagem de Kyle para uma solução on-line.
2) Se eu puder dizer que é um IList, use a abordagem do drzaus, com uma diferença.Se K for mais da metade de N, corro o risco de sofrer uma surra ao escolher muitos índices aleatórios repetidas vezes e ter que ignorá-los.Assim componho uma lista dos índices que NÃO devem ser mantidos.
3) Garanto que os itens serão devolvidos na mesma ordem em que foram encontrados.O algoritmo de Kyle não exigiu alterações.O algoritmo de drzaus exigia que eu não emitisse itens na ordem em que os índices aleatórios são escolhidos.Eu reúno todos os índices em um SortedSet e emito os itens na ordem de classificação do índice.
4) Se K for grande comparado a N e eu inverto o sentido do conjunto, então enumero todos os itens e testo se o índice não está no conjunto.Isso significa que eu perco o tempo de execução do pedido (k), mas como K está próximo de n nesses casos, não perco muito.
Aqui está o código:
/// <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;
}
}
}
}
Eu uso um gerador de números aleatórios especializado, mas você pode usar apenas C# Aleatório se você quiser.(RápidoRandom foi escrito por Colin Green e faz parte do SharpNEAT.Tem um período de 2^128-1 que é melhor que muitos RNGs.)
Aqui estão os testes de unidade:
[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));
}
}
Aqui você tem uma implementação baseada em Embaralhamento Fisher-Yates cuja complexidade do algoritmo é O(n) onde n é o subconjunto ou tamanho da amostra, em vez do tamanho da lista, como apontou 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;
}
}
Com base na resposta de Kyle, aqui está minha implementação em 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 ;
}
Este método pode ser equivalente ao de Kyle.
Digamos que sua lista tenha tamanho n e você queira k elementos.
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--;
}
}
Funciona como um encanto :)
-Alex Gilberto
Estendendo-se da resposta de @ers, se alguém estiver preocupado com possíveis implementações diferentes de OrderBy, isso deve ser seguro:
// 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
Este é o melhor que consegui fazer em um primeiro corte:
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;
}
Usar uma lista de aleatórios dentro de um intervalo de 1 - contagem total da lista e simplesmente puxar esses itens da lista parecia ser a melhor maneira, mas usar o Dicionário para garantir a exclusividade é algo que ainda estou pensando.
Observe também que usei uma lista de strings, substitua conforme necessário.
por que não algo assim:
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#
É muito mais difícil do que se poderia pensar.Veja o ótimo artigo "embaralhamento" de Jeff.
Escrevi um artigo muito curto sobre esse assunto, incluindo código C#:
Retornar subconjunto aleatório de N elementos de um determinado array
Meta:Selecione o número N de itens da fonte de coleta sem duplicação.Criei uma extensão para qualquer coleção genérica.Veja como eu fiz isso:
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;
}
}
Recentemente fiz isso em meu projeto usando uma ideia semelhante a Ponto 1 de Tyler.
Eu estava carregando um monte de perguntas e selecionando cinco aleatoriamente.A classificação foi obtida por meio de um Comparador.
aTodas as perguntas foram carregadas na lista QuestionSorter, que foi então classificada usando o Função de classificação da lista e os primeiros k elementos foram selecionados.
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;
}
}
}
Uso:
List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();
// add the questions here
unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);
// select the first k elements
Aqui está minha abordagem (texto completo aqui http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).
Deve ser executado em O(K) em vez de O(N), onde K é o número de elementos desejados e N é o tamanho da lista para escolher:
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;
}
Isso não é tão elegante ou eficiente quanto a solução aceita, mas é rápido de escrever.Primeiro, permute a matriz aleatoriamente e, em seguida, selecione os primeiros K elementos.Em píton,
import numpy
N = 20
K = 5
idx = np.arange(N)
numpy.random.shuffle(idx)
print idx[:K]
Eu usaria um método de extensão.
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;
}
}
Memória:~contar
Complexidade:O(contar2)
Quando N é muito grande, o método normal que embaralha aleatoriamente os N números e seleciona, digamos, os primeiros k números, pode ser proibitivo devido à complexidade do espaço.O algoritmo a seguir requer apenas O(k) para complexidades de tempo e espaço.
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
Usando LINQ com listas grandes (quando é caro tocar em cada elemento) E se você pode conviver com a possibilidade de duplicatas:
new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))
Para meu uso, eu tinha uma lista de 100.000 elementos e, por causa deles terem sido extraídos de um banco de dados, reduzi a metade (ou melhor) do tempo em comparação com um rnd na lista inteira.
Ter uma lista grande reduzirá muito as chances de duplicatas.
