Случайный список <T>

855

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

mirezus
источник
3
Существует открытая проблема для интеграции этой функциональности в .NET: github.com/dotnet/corefx/issues/461
Натан
5
Возможно, вас заинтересует этот пакет NuGet , который содержит методы расширения для тасования IList <T> и IEnumerable <T> с использованием алгоритма Фишера-Йейтса, упомянутого ниже
ChaseMedallion
3
@Natan они закрыли вопрос, потому что кто-то «работал над многими проектами и разработал много библиотек и никогда не нуждался в таком методе», что разозлило меня. Теперь мы должны исследовать себя, искать лучшие реализации, тратить время, чтобы просто заново изобрести колесо.
Виталий Исаенко
1
Я вижу это правильно? Ни одного действительного функционального ответа через 10 лет? Может быть, нам нужна еще одна награда за решение, которое учитывает количество необходимой энтропии, чтобы перемешать список с 75 числами $ log2 (75!) = 364 $ и как мы можем это получить. Во время перестановки Фишера-Йетса нужно было бы повторно заполнить даже криптографически защищенный ГСЧ с 256-битной энтропией хотя бы один раз.
Falco
1
И если обычный кодировщик не может решить эту проблему, мы все играли в те же самые 0,01% возможных пасьянсов навсегда?
Falco

Ответы:

1137

Перемешайте все (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;
      }
    }
  }
}
граната
источник
32
Что если list.Count> Byte.MaxValue? Если n = 1000, то 255/1000 = 0, поэтому цикл do будет бесконечным, поскольку box [0] <0 всегда ложно.
AndrewS
18
Я хотел бы отметить, что сравнение некорректно. Проблема в использовании <code> new Random () </ code> в цикле, а не в случайности <code> Random </ code> Объяснение
Sven
9
Хорошей идеей будет передать экземпляр Random в метод Shuffle, а не создавать его внутри, как если бы вы вызывали Shuffle много раз в быстрой последовательности (например, перетасовывали множество коротких списков), все списки будут перетасовываться в одном и том же путь (например, первый элемент всегда перемещается в положение 3).
Марк Хит
7
Просто сделав Random rng = new Random();это, staticможно решить проблему в посте сравнения. Поскольку каждый последующий вызов будет следовать из предыдущих вызовов последний случайный результат.
Уэстон
5
# 2, не ясно, что версия с генератором Crypto работает, потому что максимальный диапазон байта равен 255, поэтому любой список, размер которого больше этого, не будет правильно перемешиваться.
Марк Соул
336

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

var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();
user453230
источник
40
Идентификаторы GUID должны быть уникальными, а не случайными. Часть из них основана на машинах, а другая - на основе времени, и лишь небольшая часть является случайной. blogs.msdn.com/b/oldnewthing/archive/2008/06/27/8659071.aspx
Despertar
99
Это хорошее элегантное решение. Если вы хотите, чтобы что-то отличное от guid генерировало случайность, просто закажите что-то другое. Например: var shuffledcards = cards.OrderBy(a => rng.Next()); compilr.com/grenade/sandbox/Program.cs
граната
20
Пожалуйста, не надо. Это не верно. «случайное упорядочение» - это НЕ случайный случай: вы вносите предвзятость и, что еще хуже, рискуете пойти бесконечными циклами
Вито Де Туллио
78
@VitoDeTullio: Вы не помните. Вы рискуете бесконечными циклами, когда предоставляете функцию случайного сравнения ; функция сравнения требуется для получения последовательного общего заказа . Случайный ключ в порядке. Это предположение неверно, потому что направляющие не гарантируются случайными , а не потому, что техника сортировки по случайному ключу неверна.
Эрик Липперт
24
@Doug: NewGuidтолько гарантирует, что он дает вам уникальный GUID. Это не дает никаких гарантий относительно случайности. Если вы используете GUID для другой цели, а не для создания уникального значения, вы делаете это неправильно.
Эрик Липперт
120

Я немного удивлен всеми неуклюжими версиями этого простого алгоритма здесь. Фишер-Йейтс (или Кнут Шаффл) немного сложнее, но очень компактен. Почему это сложно? Потому что вам нужно обратить внимание на то, r(a,b)возвращает ли ваш генератор случайных чисел значение, где bоно включено или исключено. Я также отредактировал описание Википедии, чтобы люди не слепо следовали псевдокоду и создавали трудно обнаруживаемые ошибки. Для .Net Random.Next(a,b)возвращает число, исключающее, bтак что без лишних слов, вот как это может быть реализовано в C # /. Net:

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

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

Попробуйте этот код .

Шиталь шах
источник
Не лучше ли изменить rnd (i, list.Count) на rnd (0, list.Count), чтобы можно было поменять любую карту?
Пончики
16
@ Донатс - нет. Если вы сделаете это, вы добавите смещение в случайном порядке.
Shital Shah
2
Разделив Swap <T> на отдельный метод, создается впечатление, что вы вызываете много ненужных T-выделений для temp.
Глина
2
Я бы поспорил, что LINQ может потенциально замедлить производительность перестановки, и это будет причиной не использовать его, особенно учитывая относительную простоту кода.
winglerw28
7
Когда i = list.Count - 1, т.е. последняя итерация, я rnd.Next(i, list.Count)верну вас. Поэтому вам нужно i < list.Count -1как условие цикла. Ну, это вам не нужно, но это экономит 1 итерацию;)
Pod
78

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

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}
Денис
источник
3
Обратите внимание, что это не потокобезопасно, даже если используется в поточно-
ориентированном
1
как мы передаем список <string> этой функции?
MonsterMMORPG
8
Этот алгоритм имеет две существенные проблемы: - OrderByиспользует вариант QuickSort для сортировки элементов по их (якобы случайным) ключам. Производительность быстрой сортировки - O (N log N) ; напротив, тасование Фишера-Йейтса - это O (N) . Для коллекции из 75 элементов это может не иметь большого значения, но разница станет заметной для больших коллекций.
Джон Бейер
10
... - Random.Next()может привести к разумно псевдослучайному распределению значений, но это не гарантирует, что значения будут уникальными. Вероятность дублирования ключей растет (нелинейно) с N до тех пор, пока не достигнет определенности, когда N достигнет 2 ^ 32 + 1. OrderByQuickSort является стабильным родом; таким образом, если нескольким элементам присвоено одно и то же значение псевдослучайного индекса, их порядок в выходной последовательности будет таким же, как во входной последовательности; таким образом, смещение вводится в «перемешивание».
Джон Бейер
27
@JohnBeyer: Есть гораздо более серьезные проблемы, чем этот источник предвзятости. В рандоме есть только четыре миллиарда возможных семян, что намного, намного меньше, чем количество возможных перетасовок набора среднего размера. Только небольшая часть возможных перемешиваний может быть сгенерирована. Это смещение затмевает смещение из-за случайных столкновений.
Эрик Липперт
16

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

var result = items.Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList()
Андрей Кучер
источник
3
лучшее решение для одного лайнера
vipin8169
1
Тебе не хватает точки с запятой в конце fyi
reggaeguitar
Если кто-то не уверен насчет rnd, добавьте это перед кодом выше Random rnd = new Random ();
Грег Тревеллик
10
    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;
    }
Адам Теген
источник
4
Разве вы не должны делать что-то вроде того, var listCopy = list.ToList()чтобы не выталкивать все элементы из входящего списка? Я действительно не понимаю, почему вы хотите изменить эти списки, чтобы очистить.
Крис Марисик
9

РЕДАКТИРОВАТЬ Это 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]];
}

Jodrell
источник
См. Stackoverflow.com/questions/4412405/… . Вы должны быть осведомлены уже.
nawfal
@nawfal посмотрите мою улучшенную реализацию.
Джодрелл
1
хм достаточно справедливо. Это GetNextили Next?
Nawfal
4

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

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);
}
Шехаб Фаузи
источник
3
Я бы оставил Randomэкземпляр класса вне функции как staticпеременную. В противном случае вы можете получить то же самое рандомизированное начальное число из таймера, если вызывается в быстрой последовательности.
Лимонное семя
Интересное замечание - если вы быстро создаете экземпляр класса Random в цикле, скажем, от 0 до 200 мс друг от друга, то у вас очень высока вероятность получить то же начальное значение рандомизации, что затем приводит к повторяющимся результатам. Однако вы можете обойти это, используя Random rand = new Random (Guid.NewGuid (). GetHashCode ()); Это эффективно вынуждает рандомизацию быть полученной из Guid.NewGuid ()
Baaleos
4

Это мой предпочтительный метод случайного воспроизведения, когда желательно не изменять оригинал. Это вариант алгоритма Фишера-Йейтса «наизнанку», который работает с любой перечисляемой последовательностью (длина sourceне должна быть известна с самого начала).

public static IList<T> NextList<T>(this Random r, IEnumerable<T> source)
{
  var list = new List<T>();
  foreach (var item in source)
  {
    var i = r.Next(list.Count + 1);
    if (i == list.Count)
    {
      list.Add(item);
    }
    else
    {
      var temp = list[i];
      list[i] = item;
      list.Add(temp);
    }
  }
  return list;
}

Этот алгоритм также может быть реализован путем выделения диапазона от и 0до length - 1случайного исчерпания индексов путем замены произвольно выбранного индекса на последний индекс, пока все индексы не будут выбраны ровно один раз. Этот код выше выполняет то же самое, но без дополнительного выделения. Который довольно опрятен.

Что касается Randomкласса, это генератор чисел общего назначения (и если бы я проводил лотерею, я бы подумал об использовании чего-то другого). По умолчанию также используется начальное значение времени. Небольшое облегчение проблемы состоит в том, чтобы заполнить Randomкласс с помощью метода RNGCryptoServiceProviderили, который вы могли бы использовать RNGCryptoServiceProviderв методе, подобном этому (см. Ниже), для генерации равномерно выбранных случайных двойных значений с плавающей запятой, но для проведения лотереи в значительной степени требуется понимание случайности и природы источник случайности.

var bytes = new byte[8];
_secureRng.GetBytes(bytes);
var v = BitConverter.ToUInt64(bytes, 0);
return (double)v / ((double)ulong.MaxValue + 1);

Смысл генерации случайного двойного числа (исключительно между 0 и 1) заключается в использовании для масштабирования до целочисленного решения. Если вам нужно выбрать что-то из списка, основанного на случайном двойном значении x, это всегда будет 0 <= x && x < 1просто.

return list[(int)(x * list.Count)];

Наслаждайтесь!

Джон Лейдгрен
источник
4

Если вы не возражаете против использования двух Lists, то это, вероятно, самый простой способ сделать это, но, вероятно, не самый эффективный или непредсказуемый:

List<int> xList = new List<int>() { 1, 2, 3, 4, 5 };
List<int> deck = new List<int>();

foreach (int xInt in xList)
    deck.Insert(random.Next(0, deck.Count + 1), xInt);
Xelights
источник
3

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

DMO
источник
3

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

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);
}
albertein
источник
list.RemoveAt - это операция O (n), которая делает эту реализацию слишком медленной.
Георгий Полевой,
1
    List<T> OriginalList = new List<T>();
    List<T> TempList = new List<T>();
    Random random = new Random();
    int length = OriginalList.Count;
    int TempIndex = 0;

    while (length > 0) {
        TempIndex = random.Next(0, length);  // get random value between 0 and original length
        TempList.Add(OriginalList[TempIndex]); // add to temp list
        OriginalList.RemoveAt(TempIndex); // remove from original list
        length = OriginalList.Count;  // get new list <T> length.
    }

    OriginalList = new List<T>();
    OriginalList = TempList; // copy all items from temp list to original list.
user7767814
источник
0

Вот эффективный Shuffler, который возвращает байтовый массив перемешанных значений. Это никогда не тасует больше, чем нужно. Его можно перезапустить с того места, где он ранее остановился. Моя фактическая реализация (не показана) - это компонент MEF, который позволяет заданную пользователем замену shuffler.

    public byte[] Shuffle(byte[] array, int start, int count)
    {
        int n = array.Length - start;
        byte[] shuffled = new byte[count];
        for(int i = 0; i < count; i++, start++)
        {
            int k = UniformRandomGenerator.Next(n--) + start;
            shuffled[i] = array[k];
            array[k] = array[start];
            array[start] = shuffled[i];
        }
        return shuffled;
    }

`

BSalita
источник
0

Вот потокобезопасный способ сделать это:

public static class EnumerableExtension
{
    private static Random globalRng = new Random();

    [ThreadStatic]
    private static Random _rng;

    private static Random rng 
    {
        get
        {
            if (_rng == null)
            {
                int seed;
                lock (globalRng)
                {
                    seed = globalRng.Next();
                }
                _rng = new Random(seed);
             }
             return _rng;
         }
    }

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> items)
    {
        return items.OrderBy (i => rng.Next());
    }
}
Кристофер Стивенсон
источник
0
 public Deck(IEnumerable<Card> initialCards) 
    {
    cards = new List<Card>(initialCards);
    public void Shuffle() 
     }
    {
        List<Card> NewCards = new List<Card>();
        while (cards.Count > 0) 
        {
            int CardToMove = random.Next(cards.Count);
            NewCards.Add(cards[CardToMove]);
            cards.RemoveAt(CardToMove);
        }
        cards = NewCards;
    }

public IEnumerable<string> GetCardNames() 

{
    string[] CardNames = new string[cards.Count];
    for (int i = 0; i < cards.Count; i++)
    CardNames[i] = cards[i].Name;
    return CardNames;
}

Deck deck1;
Deck deck2;
Random random = new Random();

public Form1() 
{

InitializeComponent();
ResetDeck(1);
ResetDeck(2);
RedrawDeck(1);
 RedrawDeck(2);

}



 private void ResetDeck(int deckNumber) 
    {
    if (deckNumber == 1) 
{
      int numberOfCards = random.Next(1, 11);
      deck1 = new Deck(new Card[] { });
      for (int i = 0; i < numberOfCards; i++)
           deck1.Add(new Card((Suits)random.Next(4),(Values)random.Next(1, 14)));
       deck1.Sort();
}


   else
    deck2 = new Deck();
 }

private void reset1_Click(object sender, EventArgs e) {
ResetDeck(1);
RedrawDeck(1);

}

private void shuffle1_Click(object sender, EventArgs e) 
{
    deck1.Shuffle();
    RedrawDeck(1);

}

private void moveToDeck1_Click(object sender, EventArgs e) 
{

    if (listBox2.SelectedIndex >= 0)
    if (deck2.Count > 0) {
    deck1.Add(deck2.Deal(listBox2.SelectedIndex));

}

    RedrawDeck(1);
    RedrawDeck(2);

}
Саммит Ладдха
источник
2
Добро пожаловать в переполнение стека! Пожалуйста, подумайте над тем, чтобы добавить в ваш ответ какое-то объяснение, а не просто огромный блок кода. Наша цель - научить людей понимать ответ и применять его в других ситуациях. Если вы прокомментируете свой код и добавите объяснение, вы сделаете свой ответ более полезным не только для человека, который задал вопрос на этот раз, но и для любого в будущем, который может столкнуться с той же проблемой.
starsplusplus
4
Большая часть этого кода совершенно не имеет отношения к вопросу, и единственная полезная часть в основном повторяет ответ Адама Тегена почти 6 лет назад.
TC
0

Простая модификация принятого ответа, которая возвращает новый список вместо того, чтобы работать на месте, и принимает более общий, IEnumerable<T>как это делают многие другие методы Linq.

private static Random rng = new Random();

/// <summary>
/// Returns a new list where the elements are randomly shuffled.
/// Based on the Fisher-Yates shuffle, which has O(n) complexity.
/// </summary>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
    var source = list.ToList();
    int n = source.Count;
    var shuffled = new List<T>(n);
    shuffled.AddRange(source);
    while (n > 1) {
        n--;
        int k = rng.Next(n + 1);
        T value = shuffled[k];
        shuffled[k] = shuffled[n];
        shuffled[n] = value;
    }
    return shuffled;
}
Extragorey
источник
-5

Старый пост, конечно, но я просто использую GUID.

Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList();

GUID всегда уникален, и поскольку он обновляется каждый раз, когда результат меняется каждый раз.

DavidMc
источник
Компактно, но есть ли у вас рекомендации по сортировке последовательных новых гидов по случайному качеству? Некоторые версии quid / uuid имеют метки времени и другие неслучайные части.
Йохан Лундберг
8
Этот ответ уже дан, и, что еще хуже, он предназначен для уникальности, а не случайности.
Алекс Ангас
-7

Очень простой подход к решению этой проблемы заключается в использовании нескольких случайных элементов в списке.

В псевдокоде это будет выглядеть так:

do 
    r1 = randomPositionInList()
    r2 = randomPositionInList()
    swap elements at index r1 and index r2 
for a certain number of times
Aleris
источник
1
Одной из проблем этого подхода является знание того, когда остановиться. Он также имеет тенденцию преувеличивать любые смещения в генераторе псевдослучайных чисел.
Марк Бесси
3
Да. Весьма неэффективно. Нет смысла использовать такой подход, когда существуют лучшие, более быстрые подходы, которые столь же просты.
PeterAllenWebb
1
не очень эффективно или эффективно ... Выполнение этого N раз, вероятно, оставило бы много элементов в их исходном положении.
NSjonas