Рандомизировать список <T>

Question

Каков наилучший способ рандомизировать порядок универсального списка в C #? У меня есть конечный набор из 75 чисел в списке, которому я хотел бы назначить случайный заказ, чтобы нарисовать их для приложения типа лотереи.

Answer 1

Перемешать любое (I)List с помощью метода расширения, основанного на перемешивании Фишера-Йейтса :

private static Random rng = new Random();  

public static void Shuffle<T>(this IList<T> list)  
{  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}

Использование:

List<Product> products = GetProducts();
products.Shuffle();

Приведенный выше код использует критикуемый метод System.Random для выбора кандидатов на своп. Это быстро, но не так случайно, как должно быть. Если вам нужно более высокое качество случайности в случайном порядке, используйте генератор случайных чисел в System.Security.Cryptography следующим образом:

using System.Security.Cryptography;
...
public static void Shuffle<T>(this IList<T> list)
{
    RNGCryptoServiceProvider provider = new RNGCryptoServiceProvider();
    int n = list.Count;
    while (n > 1)
    {
        byte[] box = new byte[1];
        do provider.GetBytes(box);
        while (!(box[0] < n * (Byte.MaxValue / n)));
        int k = (box[0] % n);
        n--;
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}

Простое сравнение доступно в этом блоге (WayBack Machine).

Редактировать: После того, как я написал этот ответ пару лет назад, многие люди комментировали или писали мне, чтобы указать на большой глупый недостаток в моем сравнении. Они конечно правы. Нет ничего плохого в System.Random, если он используется так, как задумано. В моем первом примере, приведенном выше, я создаю экземпляр переменной rng внутри метода Shuffle, который вызывает проблемы, если метод будет вызываться повторно. Ниже приведен фиксированный, полный пример, основанный на действительно полезном комментарии, полученном сегодня от @weston здесь, на SO.

Program.cs:

using System;
using System.Collections.Generic;
using System.Threading;

namespace SimpleLottery
{
  class Program
  {
    private static void Main(string[] args)
    {
      var numbers = new List<int>(Enumerable.Range(1, 75));
      numbers.Shuffle();
      Console.WriteLine("The winning numbers are: {0}", string.Join(",  ", numbers.GetRange(0, 5)));
    }
  }

  public static class ThreadSafeRandom
  {
      [ThreadStatic] private static Random Local;

      public static Random ThisThreadsRandom
      {
          get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + Thread.CurrentThread.ManagedThreadId))); }
      }
  }

  static class MyExtensions
  {
    public static void Shuffle<T>(this IList<T> list)
    {
      int n = list.Count;
      while (n > 1)
      {
        n--;
        int k = ThreadSafeRandom.ThisThreadsRandom.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
      }
    }
  }
}

Answer 2

Если нам нужно перетасовать элементы только в совершенно случайном порядке (просто чтобы смешать элементы в списке), я предпочитаю этот простой, но эффективный код, который упорядочивает элементы по guid ...

var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();

Answer 3

Я немного удивлен всеми неуклюжими версиями этого простого алгоритма здесь. Фишер-Йейтс (или Кнут Шаффл) немного сложнее, но очень компактен. Если вы пойдете в Википедию, вы увидите версию этого алгоритма, которая имеет цикл for в обратном порядке, и многие люди на самом деле не понимают, почему это наоборот. Основная причина в том, что эта версия алгоритма предполагает, что генератор случайных чисел Random(n) в вашем распоряжении имеет два следующих свойства:

1. Принимает n как один входной параметр.
2. Возвращает число от 0 до n включительно .

Однако генератор случайных чисел .Net не удовлетворяет свойству # 2. Вместо этого Random.Next(n) возвращает число от 0 до n-1 включительно. Если вы попытаетесь использовать цикл for в обратном порядке, вам нужно будет вызвать Random.Next(n+1), который добавляет одну дополнительную операцию.

Однако в генераторе случайных чисел .Net есть еще одна приятная функция Random.Next(a,b), которая возвращает a к b-1 включительно. Это на самом деле прекрасно вписывается в реализацию этого алгоритма с нормальным циклом for. Итак, без лишних слов, вот правильная, эффективная и компактная реализация:

public static void Shuffle<T>(this IList<T> list, Random rnd)
{
    for(var i=0; i < list.Count - 1; i++)
        list.Swap(i, rnd.Next(i, list.Count));
}

public static void Swap<T>(this IList<T> list, int i, int j)
{
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

Answer 4

Метод расширения для IEnumerable:

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}

Answer 5

    public static List<T> Randomize<T>(List<T> list)
    {
        List<T> randomizedList = new List<T>();
        Random rnd = new Random();
        while (list.Count > 0)
        {
            int index = rnd.Next(0, list.Count); //pick a random item from the master list
            randomizedList.Add(list[index]); //place it at the end of the randomized list
            list.RemoveAt(index);
        }
        return randomizedList;
    }

Answer 6

EDIT RemoveAt - слабость в моей предыдущей версии. Это решение преодолевает это.

public static IEnumerable<T> Shuffle<T>(
        this IEnumerable<T> source,
        Random generator = null)
{
    if (generator == null)
    {
        generator = new Random();
    }

    var elements = source.ToArray();
    for (var i = elements.Length - 1; i >= 0; i--)
    {
        var swapIndex = generator.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

Обратите внимание на необязательный Random generator, если реализация базового фреймворка Random не является поточно-ориентированной или недостаточно криптографической для ваших нужд, вы можете внедрить свою реализацию в операцию.

В этом ответе можно найти подходящую реализацию для поточно-безопасной криптографической реализации Random.

---

Вот идея, расширяющая IList (надеюсь) эффективным способом.

public static IEnumerable<T> Shuffle<T>(this IList<T> list)
{
    var choices = Enumerable.Range(0, list.Count).ToList();
    var rng = new Random();
    for(int n = choices.Count; n > 1; n--)
    {
        int k = rng.Next(n);
        yield return list[choices[k]];
        choices.RemoveAt(k);
    }

    yield return list[choices[0]];
}

Answer 7

Вы можете добиться этого, используя этот простой метод расширения

public static class IEnumerableExtensions
{

    public static IEnumerable<t> Randomize<t>(this IEnumerable<t> target)
    {
        Random r = new Random();

        return target.OrderBy(x=>(r.Next()));
    }        
}

, и вы можете использовать его, выполнив следующее

// use this on any collection that implements IEnumerable!
// List, Array, HashSet, Collection, etc

List<string> myList = new List<string> { "hello", "random", "world", "foo", "bar", "bat", "baz" };

foreach (string s in myList.Randomize())
{
    Console.WriteLine(s);
}

Answer 8

Идея состоит в том, чтобы получить анонимный объект с элементом и случайным порядком, а затем изменить порядок элементов по этому порядку и вернуть значение:

var result = items.Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList()

Answer 9

Я обычно использую:

var list = new List<T> ();
fillList (list);
var randomizedList = new List<T> ();
var rnd = new Random ();
while (list.Count != 0)
{
    var index = rnd.Next (0, list.Count);
    randomizedList.Add (list [index]);
    list.RemoveAt (index);
}

Answer 10

Если у вас фиксированное число (75), вы можете создать массив из 75 элементов, а затем перечислить ваш список, перемещая элементы в рандомизированные позиции в массиве. Вы можете сгенерировать отображение номера списка на индекс массива, используя Fisher-Yates shuffle .