Selecione N elementos randoms de uma lista em c #

Eu preciso de um algoritmo rápido para selecionar 5 elementos randoms de uma lista genérica. Por exemplo, eu gostaria de obter 5 elementos randoms de uma List .

Iterar através de e para cada elemento, fazer a probabilidade de seleção = (número necessário) / (número à esquerda)

Então, se você tivesse 40 itens, o primeiro teria uma chance de 5/40 de ser selecionado. Se for, o próximo tem uma chance de 4/39, caso contrário, ele tem uma chance de 5/39. No momento em que você chegar ao final, você terá seus 5 itens, e muitas vezes você terá todos eles antes disso.

Usando o linq:

 YourList.OrderBy(x => rnd.Next()).Take(5) 
 public static List GetRandomElements(this IEnumerable list, int elementsCount) { return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList(); } 

Este é realmente um problema mais difícil do que parece, principalmente porque muitas soluções matematicamente corretas não permitirão que você realmente atinja todas as possibilidades (mais sobre isso abaixo).

Primeiro, aqui estão alguns geradores de números corretos, fáceis de implementar, se você tiver um realmente random:

(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 o seu subconjunto random. Eu 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 o índice de k elementos randoms. Escolha um número r em {0, 1, 2, …, n-1} aleatoriamente, r = rand% n e adicione isso a s. Em seguida, pegue r = rand% (n-1) e coloque em s; adicione aos elementos # r menores que em s para evitar colisões. Em seguida, pegue r = rand% (n-2), e faça a mesma coisa, etc. até ter k elementos distintos em s. Este tem o pior tempo de execução O (k ^ 2). Então, para k < < n, isso pode ser mais rápido. Se você mantiver ordenado e rastrear quais intervalos contíguos ele possui, você pode implementá-lo em O (k log k), mas é mais trabalho.

@ Kyle – você está certo, no segundo pensamento eu concordo com sua resposta. Apressadamente li a princípio, e erroneamente pensei que você estivesse indicando para escolher sequencialmente cada elemento com probabilidade fixa k / n, o que estaria errado – mas sua abordagem adaptativa parece correta para mim. Me desculpe por isso.

Ok, e agora para o kicker: assintoticamente (para k fixo, n crescendo), existem n ^ k / k! escolhas de k elemento subconjunto de n elementos [isto é uma aproximação de (n escolha k)]. Se n é grande ek não é muito pequeno, esses números são enormes. O melhor comprimento de ciclo que você pode esperar em qualquer gerador de números randoms padrão de 32 bits é 2 ^ 32 = 256 ^ 4. Então, se temos uma lista de 1000 elementos, e queremos escolher 5 aleatoriamente, não há como um gerador de números randoms padrão atingir todas as possibilidades. No entanto, contanto que você esteja bem com uma opção que funcione bem para conjuntos menores, e sempre “pareça” aleatória, esses algoritmos devem estar ok.

Adendo : Depois de escrever isso, percebi que é complicado implementar a ideia (2) corretamente, então queria esclarecer essa resposta. Para obter o tempo O (k log k), você precisa de uma estrutura de matriz que suporte buscas e inserções do O (log m) – uma tree binária balanceada pode fazer isso. Usando tal estrutura para construir um array chamado s, aqui está algum 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, ni) # May be 0, must be < ni 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 executar alguns exemplos de casos para ver como isso implementa de forma eficiente a explicação em inglês acima.

Eu acho que a resposta selecionada é correta e muito doce. Eu implementei diferentemente, como também queria o resultado em ordem aleatória.

  static IEnumerable PickSomeInRandomOrder( IEnumerable someTypes, int maxCount) { Random random = new Random(DateTime.Now.Millisecond); Dictionary randomSortTable = new Dictionary(); 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 este problema, e mais algumas pesquisas no google me trouxeram o problema de embaralhar aleatoriamente uma lista: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Para aleatoriamente aleatoriamente sua lista (no lugar) você faz isso:

Para misturar uma matriz 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ê só precisa dos 5 primeiros elementos, então ao invés de executar o i de n-1 para 1, você só precisa executá-lo para n-5 (ex: n-5)

Vamos dizer que você precisa de k itens,

Isso se torna:

  for (i = n − 1; i >= nk; i--) { j = random integer with 0 ≤ j ≤ i exchange a[j] and a[i] } 

Cada item selecionado é trocado para o final da matriz, de modo que os elementos k selecionados são os últimos k elementos da matriz.

Isso leva tempo O (k), onde k é o número de elementos selecionados aleatoriamente que você precisa.

Além disso, se você não quiser modificar sua lista inicial, pode anotar todos os seus swaps em uma lista temporária, inverter essa lista e aplicá-los novamente, realizando assim o conjunto inverso de swaps e retornando sua lista inicial sem alterar O (k) tempo de execução.

Finalmente, para o stickler real, if (n == k), você deve parar em 1, não nk, já que o inteiro escolhido aleatoriamente será sempre 0.

De dragões no algoritmo , uma interpretação em c #:

 int k = 10; // items to select var items = new List(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }); var selected = new List(); 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--; } 

Este algoritmo selecionará os índices únicos da lista de itens.

Você pode usar isso, mas a encomenda acontecerá no lado do cliente

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

Estava pensando no comentário de @JohnShedletsky sobre a resposta aceita em relação a (paráfrase):

você deve ser capaz de fazer isso em O (subconjunto.Comprimento), em vez de O (originalList.Length)

Basicamente, você deve ser capaz de gerar índices randoms de subset e então arrancá-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 GetRandom(this IEnumerable 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 GetRandom(this T[] list, int numItems) { var items = new HashSet(); // 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 PluckRandomly(this IEnumerable list) { while( true ) yield return list.ElementAt(randomizer.Next(list.Count())); } } 

Se você quisesse ser ainda mais eficiente, provavelmente usaria um HashSet dos índices , não os elementos de lista reais (no caso de ter tipos complexos ou comparações caras);

O teste unitário

E para ter certeza de que não temos 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, int, IEnumerable> methodToGetRandomItems, int numToTake = 10, int repetitions = 100000, bool requireDistinct = true) { var items = Enumerable.Range(0, 100); IEnumerable 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); } } } 

Selecionar N itens randoms de um grupo não deve ter nada a ver com o pedido ! Aleatoriedade é sobre imprevisibilidade e não sobre embaralhar posições em um grupo. Todas as respostas que lidam com algum tipo de ordenação tendem a ser menos eficientes do que as que não são. Como a eficiência é a chave aqui, vou postar algo que não altera muito a ordem dos itens.

1) Se você precisa de valores randoms verdadeiros , o que significa que não há restrição sobre quais elementos escolher (isto é, uma vez que o item escolhido pode ser selecionado novamente):

 public static List GetTrueRandom(this IList source, int count, bool throwArgumentOutOfRangeException = true) { if (throwArgumentOutOfRangeException && count > source.Count) throw new ArgumentOutOfRangeException(); var randoms = new List(count); randoms.AddRandomly(source, count); return randoms; } 

Se você desativar o sinalizador de exceção, poderá escolher itens randoms qualquer número de vezes.

Se você tem {1, 2, 3, 4}, então ele pode dar {1, 4, 4}, {1, 4, 3} etc para 3 itens ou {1, 4, 3, 2, 4} para 5 itens!

Isso deve ser muito rápido, pois não tem nada para verificar.

2) Se você precisa de membros individuais do grupo sem repetição, então eu contaria com um dictionary (como muitos já apontaram).

 public static List GetDistinctRandom(this IList source, int count) { if (count > source.Count) throw new ArgumentOutOfRangeException(); if (count == source.Count) return new List(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(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 demorado do que outras abordagens de dictionary aqui porque eu não estou apenas adicionando, mas também removendo da lista, então é meio que dois loops. Você pode ver aqui que eu não reordenei nada quando a count se torna igual a source.Count . Isso porque acredito que a aleatoriedade deve estar no conjunto retornado como um todo . Quero dizer, se você quiser 5 itens randoms de 1, 2, 3, 4, 5 , não importa se é 1, 3, 4, 2, 5 ou 1, 2, 3, 4, 5 , mas se você precisar 4 itens do mesmo conjunto, então deve imprevisivelmente produzir em 1, 2, 3, 4 , 1, 3, 5, 2 , 2, 3, 5, 4 etc. Em segundo lugar, quando a contagem de itens randoms a serem devolvidos é mais da metade do grupo original, então é mais fácil remover source.Count - count itens do grupo do que adicionar itens de count . Por motivos de desempenho, usei source vez de sourceDict para obter um índice random no método remove.

Então, se você tem {1, 2, 3, 4}, isso pode acabar em {1, 2, 3}, {3, 4, 1} etc para 3 itens.

3) Se você precisa de valores randoms verdadeiramente distintos do seu grupo levando em conta as duplicatas no grupo original, então você pode usar a mesma abordagem como acima, mas um HashSet será mais claro que um dictionary.

 public static List GetTrueDistinctRandom(this IList source, int count, bool throwArgumentOutOfRangeException = true) { if (count > source.Count) throw new ArgumentOutOfRangeException(); var set = new HashSet(source); if (throwArgumentOutOfRangeException && count > set.Count) throw new ArgumentOutOfRangeException(); List 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(); randoms.AddRandomly(list, count); return randoms.ToList(); } 

A variável randoms é feita com um HashSet para evitar duplicatas sendo adicionadas no mais raro dos casos mais raros, onde Random.Next pode produzir o mesmo valor, especialmente quando a lista de input é pequena.

Então {1, 2, 2, 4} => 3 itens randoms => {1, 2, 4} e nunca {1, 2, 2}

{1, 2, 2, 4} => 4 itens randoms => exceção !! ou {1, 2, 4} dependendo do sinalizador definido.

Alguns dos methods de extensão que usei:

 static Random rnd = new Random(); public static int GetRandomIndex(this ICollection source) { return rnd.Next(source.Count); } public static T GetRandom(this IList source) { return source[source.GetRandomIndex()]; } static void AddRandomly(this ICollection toCol, IList fromList, int count) { while (toCol.Count < count) toCol.Add(fromList.GetRandom()); } public static Dictionary ToIndexedDictionary(this IEnumerable lst) { return lst.ToIndexedDictionary(t => t); } public static Dictionary ToIndexedDictionary(this IEnumerable lst, Func valueSelector) { int index = -1; return lst.ToDictionary(t => ++index, valueSelector); } 

Se é tudo sobre o desempenho com dezenas de milhares de itens na lista ter que ser iterado 10000 vezes, então você pode querer ter uma class aleatória mais rápida do que System.Random , mas eu não acho que seja um grande problema, considerando o último provavelmente nunca é um gargalo, é bastante rápido o suficiente ..

Edit: Se você precisa reorganizar a ordem dos itens retornados também, então não há nada que possa bater a abordagem de Fisher-Yates de dhakim – curta, doce e simples ..

A solução simples que eu uso (provavelmente não é bom para listas grandes): Copie a lista para lista temporária, em seguida, em loop aleatoriamente selecione Item da lista temporária e coloque-a na lista de itens selecionados, removendo-a da lista temporária de forma (por isso não pode ser reselecionado).

Exemplo:

 List temp = OriginalList.ToList(); List selectedItems = new List(); 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 por Lazily. Meus testes mostraram que a abordagem de Kyle (Order (N)) é muitas vezes mais lenta que a de drzaus usar um conjunto para propor os índices randoms para escolher (Order (K)). O primeiro executa muito mais chamadas para o gerador de números randoms, além de repetir mais vezes os itens.

Os objectives da minha implementação foram:

1) Não perceba a lista completa se for dado 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 memory. Use a abordagem de Kyle para uma solução on-line.

2) Se eu posso dizer que é um IList, use a abordagem de drzaus, com uma torção. Se K é mais da metade de N, arrisco me debater, pois escolho muitos índices randoms repetidamente e tenho que pulá-los. Assim componho uma lista dos índices para NÃO manter.

3) Garanto que os itens serão devolvidos na mesma ordem em que foram encontrados. O algoritmo de Kyle não precisou de alteração. O algoritmo de drzaus requeria que eu não emitisse itens na ordem em que os índices randoms fossem escolhidos. Eu recolho todos os índices em um SortedSet, em seguida, emiti itens em ordem de índice ordenado.

4) Se K é grande comparado a N e eu inverto o sentido do conjunto, então eu 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 o K está próximo de N nesses casos, não perco muito.

Aqui está o código:

  ///  /// 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. ///  /// Type of element in the items collection. /// Items to be randomly selected. /// Number of items to pick. /// 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. /// Enumerable over the retained items. /// /// See http://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c-sharp for the commentary. ///  public static IEnumerable TakeRandom(this IEnumerable items, int k, int n) { var r = new FastRandom(); var itemsList = items as IList; 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) new HashSet() : (ISet) new SortedSet(); 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 randoms especializados, mas você pode usar apenas random do c # se quiser. ( FastRandom 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 unitários:

 [TestClass] public class TakeRandomTests { ///  /// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability. ///  [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)); } ///  /// Ensure that when randomly choosing items from an IEnumerable that is not an IList, /// all items are chosen with roughly equal probability. ///  [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 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 Fisher-Yates Shuffle, cuja complexidade do algoritmo é O (n), onde n é o tamanho do subconjunto ou da amostra, em vez do tamanho da lista, como John Shedletsky apontou.

 public static IEnumerable GetRandomSample(this IList 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 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 c #.

 ///  /// Picks random selection of available game ID's ///  private static List 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(); 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 é de tamanho n e você quer k elementos.

 Random rand = new Random(); for(int i = 0; k>0; ++i) { int r = rand.Next(0, ni); if(r 

Funciona como um encanto 🙂

-Alex Gilbert

This is the best I could come up with on a first cut:

 public List getRandomItemsFromList(int returnCount, List list) { List returnList = new List(); Dictionary randoms = new Dictionary(); 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; } 

Using a list of randoms within a range of 1 – total list count and then simply pulling those items in the list seemed to be the best way, but using the Dictionary to ensure uniqueness is something I’m still mulling over.

Also note I used a string list, replace as needed.

why not something like this:

  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# 

It is a lot harder than one would think. See the great Article “Shuffling” from Jeff.

I did write a very short article on that subject including C# code:
Return random subset of N elements of a given array

I recently did this on my project using an idea similar to Tyler’s point 1 .
I was loading a bunch of questions and selecting five at random. Sorting was achieved using an IComparer .
aAll questions were loaded in the a QuestionSorter list, which was then sorted using the List’s Sort function and the first k elements where selected.

  private class QuestionSorter : IComparable { 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 unsortedQuestions = new List(); // add the questions here unsortedQuestions.Sort(unsortedQuestions as IComparer); // select the first k elements 

Here’s my approach (full text here http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

It should run in O(K) instead of O(N), where K is the number of wanted elements and N is the size of the list to choose from:

 public  List take(List 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 result = new ArrayList(k); Map used = new HashMap(); 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; } 

This isn’t as elegant or efficient as the accepted solution, but it’s quick to write up. First, permute the array randomly, then select the first K elements. In python,

 import numpy N = 20 K = 5 idx = np.arange(N) numpy.random.shuffle(idx) print idx[:K] 

I would use an extension method.

  public static IEnumerable TakeRandom(this IEnumerable elements, int countToTake) { var random = new Random(); var internalList = elements.ToList(); var selected = new List(); 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 GetRandom(this IList list, int count, Random random) { // Probably you should throw exception if count > list.Count count = Math.Min(list.Count, count); var selectedIndices = new SortedSet(); // 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; } } 

Memory: ~count
Complexity: O(count 2 )

When N is very large, the normal method that randomly shuffles the N numbers and selects, say, first k numbers, can be prohibitive because of space complexity. The following algorithm requires only O(k) for both time and space complexities.

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 

Using LINQ with large lists (when costly to touch each element) AND if you can live with the possibility of duplicates:

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

For my use i had a list of 100.000 elements, and because of them being pulled from a DB I about halfed (or better) the time compared to a rnd on the whole list.

Having a large list will reduce the odds greatly for duplicates.

Extending from @ers’s answer, if one is worried about possible different implementations of OrderBy, this should be safe:

 // 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 => xi).Take(5) // Sort by (at this point fixed) random index .Select(x => xv); // Go back to enumerable of entry