Selecione N elementos aleatórios em uma Lista <T> em C #

Eu preciso de um algoritmo rápido para selecionar 5 elementos aleatórios de uma lista genérica. Por exemplo, eu gostaria de obter 5 elementos aleatórios de a List<string>.

Repita 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 uma chance de 5/40 de ser selecionado. Se for, o próximo tem uma chance de 4/39, caso contrário, tem uma chance de 5/39. Quando você chegar ao final, você terá seus 5 itens e, muitas vezes, todos eles antes disso.

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, esse é um problema mais difícil do que parece, principalmente porque muitas soluções matematicamente corretas falharão ao permitir que você atinja todas as possibilidades (mais sobre isso abaixo).

Primeiro, aqui estão alguns geradores fáceis de implementar, corrija se você tiver um número verdadeiramente aleatório:

(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. Eu acho que isso é fácil de implementar, embora seja hora O (n log n).

(2) Inicie uma lista vazia s = [] que crescerá para ser o índice 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 cole em s; adicione r menos # elementos 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. Isso tem o pior tempo de execução O (k ^ 2). Portanto, para k << n, isso pode ser mais rápido. Se você mantiver a classificação e rastrear quais intervalos contíguos, poderá implementá-lo em O (k log k), mas é mais trabalhoso.

@ Kyle - você está certo, pensando bem, eu concordo com sua resposta. Eu li apressadamente a princípio e pensei erroneamente que você estava indicando a escolha seqüencial de 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, n crescente), existem n ^ k / k! opções do subconjunto de elementos k de n elementos [esta é uma aproximação de (n escolha k)]. Se n for grande ek não for muito pequeno, esses números serão enormes. O melhor comprimento 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 temos uma lista de 1000 elementos e queremos escolher 5 aleatoriamente, não há como um gerador de números aleatórios padrão atingir todas as possibilidades. No entanto, desde que você esteja de acordo com uma opção que funcione bem para conjuntos menores e sempre "pareça" aleatória, esses algoritmos deverão estar ok.

Adendo : Depois de escrever isso, percebi que é complicado implementar a idéia (2) corretamente, então queria esclarecer esta resposta. Para obter o tempo O (k log k), você precisa de uma estrutura semelhante a uma matriz que suporte pesquisas e inserções O (log m) - uma árvore binária equilibrada pode fazer isso. Usando essa estrutura para criar uma matriz chamada 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 casos de amostra para ver como isso implementa com eficiência a explicação acima em inglês.

Eu acho que a resposta selecionada é correta e muito gentil. Eu o implementei de maneira 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 encontrar 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 completamente aleatoriamente sua lista (no local), 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ê precisa apenas dos 5 primeiros elementos, em vez de executar i de n-1 a 1, basta executá-lo para 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, portanto, os k elementos 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, poderá anotar todos os seus swaps em uma lista temporária, reverter a lista e aplicá-los novamente, realizando o conjunto inverso de swaps e retornando sua lista inicial sem alterar O (k) tempo de execução.

Finalmente, para o verdadeiro defensor, se (n == k), você deve parar em 1, e não em nk, pois o número inteiro escolhido aleatoriamente sempre será 0.

Você pode usar isso, mas a encomenda 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 seleciona indicações exclusivas da lista de itens.

Selecionar N itens aleatórios de um grupo não deve ter nada a ver com ordem ! A aleatoriedade é sobre imprevisibilidade e não sobre a troca de posições em um grupo. Todas as respostas que lidam com alguns tipos de pedidos devem ser menos eficientes do que as que não são. Como a eficiência é a chave aqui, publicarei algo que não altera muito a ordem dos itens.

1) Se você precisar de valores aleatórios verdadeiros , significa que não há restrições sobre quais elementos escolher (ou seja, uma vez que o item escolhido 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 várias vezes.

Se você tiver {1, 2, 3, 4}, poderá fornecer {1, 4, 4}, {1, 4, 3} etc para 3 itens ou até {1, 4, 3, 2, 4} para 5 itens!

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

2) Se você precisar de membros individuais do grupo sem repetição, eu usaria 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, portanto são dois loops. Você pode ver aqui que eu não reordenei nada quando countse tornou igual a source.Count. Isso porque acredito que a aleatoriedade deve estar no conjunto retornado como um todo . Quero dizer, se você quer 5 itens aleatórios a partir 1, 2, 3, 4, 5, não deve importa se a sua 1, 3, 4, 2, 5ou 1, 2, 3, 4, 5, mas se você precisar de 4 itens do mesmo conjunto, então ele deve imprevisível produzir em 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4etc. Em segundo lugar, quando a contagem de itens aleatórios para ser retornado é mais da metade do grupo original, então é mais fácil removersource.Count - countitens do grupo do que adicionar countitens. Por razões de desempenho, usei em sourcevez de sourceDictobter um índice aleatório no método remove.

Portanto, se você tiver {1, 2, 3, 4}, isso pode terminar 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 do grupo original, poderá usar a mesma abordagem acima, mas a HashSetserá 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();
}

A randomsvariável é criada HashSetpara evitar que duplicatas sejam adicionadas nos casos mais raros, em que Random.Nextpode gerar 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 tem a ver com desempenho, com dezenas de milhares de itens na lista precisando ser repetidos 10000 vezes, convém ter uma classe aleatória mais rápida do que System.Random, mas não acho que isso seja importante, considerando que o último provavelmente nunca é um gargalo, é bastante rápido ..

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

Estava pensando no comentário de @JohnShedletsky na resposta aceita sobre (paráfrase):

você deve conseguir isso em O (subconjunto.Length), em vez de O (originalList.Length)

Basicamente, você deve ser capaz de gerar subsetíndices aleatórios e depois 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 HashSetdos índices , não os elementos da lista real (caso tenha tipos complexos ou comparações caras);

O teste de unidade

E para garantir que não tenhamos 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);
        }
    }
}

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 (Ordem (N)) é muitas vezes mais lenta que o uso de um conjunto por drzaus para propor os índices aleatórios a serem escolhidos (Ordem (K)). O primeiro realiza muito mais chamadas para o gerador de números aleatórios, além de repetir mais vezes 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 reviravolta. Se K é mais da metade de N, corro o risco de debater, pois escolho muitos índices aleatórios várias vezes e preciso ignorá-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 exigiu alterações. O algoritmo de drzaus exigia que eu não emitisse itens na ordem em que os índices aleatórios foram escolhidos. Reuni todos os índices em um SortedSet e emito itens na ordem de índice classificada.

4) Se K for grande em comparação com N e eu inverter o sentido do conjunto, enumerarei todos os itens e testarei se o índice não está no conjunto. Isso significa que eu perco o tempo de execução da Ordem (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 especializado de números aleatórios, mas você pode simplesmente usar o C # 's Random, se quiser. (O FastRandom foi escrito por Colin Green e faz parte do SharpNEAT. Ele possui um período de 2 ^ 128-1, melhor do 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));
    }
}

Estendendo-se da resposta de @ers, se alguém estiver preocupado com possíveis implementações diferentes do 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 pude apresentar 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 randoms 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 cadeias, substitua conforme necessário.

A solução simples que eu uso (provavelmente não é boa para listas grandes): copie a lista para uma lista temporária e, em loop, selecione aleatoriamente Item da lista temp e coloque-a na lista de itens selecionados enquanto remove-a da lista temp (para que não possa ser remarcada).

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

Aqui você tem uma implementação baseada no Fisher-Yates Shuffle cuja complexidade do algoritmo é O (n) em que n é o tamanho do subconjunto ou 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;
    }
}

Baseado na resposta de Kyle, aqui está minha implementação de 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 seja do 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 Gilbert

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 "Shuffling" de Jeff.

Eu escrevi um artigo muito curto sobre esse assunto, incluindo o código C #:
Retorne um subconjunto aleatório de N elementos de uma determinada matriz

Objetivo: selecione N número de itens da origem da coleção sem duplicação. Eu criei uma extensão para qualquer coleção genérica. Aqui está 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 no meu projeto usando uma ideia semelhante ao ponto 1 de Tyler .
Eu estava carregando um monte de perguntas e selecionando cinco aleatoriamente. A classificação foi realizada usando um IComparer .
Todas as perguntas foram carregadas na lista a QuestionSorter, que foi classificada com a função Classificação da lista e os primeiros k elementos 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 ).

Ele 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 escrever. Primeiro, permita a matriz aleatoriamente e, em seguida, selecione os primeiros K elementos. Em python,

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: ~ contagem
Complexidade: O (contagem ² )

Quando N é muito grande, o método normal que aleatoriamente embaralha os números N 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 o LINQ com listas grandes (quando caro tocar cada elemento) E se você puder viver 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 serem extraídos de um banco de dados, eu aproximadamente pela metade (ou melhor) do tempo comparado a um rnd na lista inteira.

Ter uma lista grande reduzirá muito as chances de duplicatas.

Isso resolverá seu problema

var entries=new List<T>();
var selectedItems = new List<T>();


                for (var i = 0; i !=10; i++)
                {
                    var rdm = new Random().Next(entries.Count);
                        while (selectedItems.Contains(entries[rdm]))
                            rdm = new Random().Next(entries.Count);

                    selectedItems.Add(entries[rdm]);
                }