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

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

7.11.2008 19:28:18
Существует открытая проблема для интеграции этой функции в .NET: github.com/dotnet/corefx/issues/461
Natan 7.03.2015 10:19:56
Возможно, вас заинтересует этот пакет NuGet , который содержит методы расширения для тасования IList <T> и IEnumerable <T> с использованием алгоритма Фишера-Йейтса, упомянутого ниже
ChaseMedallion 7.05.2016 14:44:49
@Natan fyi, они убили это
Chris Marisic 6.06.2016 15:28:29
Alexei Levenkov 5.02.2017 07:51:02
@ Натан закрыл вопрос, потому что кто-то «работал над многими проектами и разработал много библиотек и никогда не нуждался в таком методе», что разозлило меня. Теперь мы должны исследовать себя, искать лучшие реализации, тратить время, чтобы просто заново изобрести колесо.
Vitalii Isaenko 16.07.2019 11:56:54
19 ОТВЕТОВ
РЕШЕНИЕ

Перемешайте любой (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;
      }
    }
  }
}
1117
14.11.2017 06:56:11
Что если list.Count> Byte.MaxValue? Если n = 1000, то 255/1000 = 0, поэтому цикл do будет бесконечным циклом, поскольку box [0] <0 всегда ложно.
AndrewS 7.06.2011 10:47:51
Я хотел бы отметить, что сравнение некорректно. Проблема в использовании <code> new Random () </ code> в цикле, а не в случайности <code> Random </ code> Объяснение
Sven 29.09.2011 13:43:52
Рекомендуется передавать экземпляр Random методу Shuffle, а не создавать его внутри, как если бы вы вызывали Shuffle много раз в быстрой последовательности (например, перетасовывали множество коротких списков), все списки будут перетасовываться в одном и том же путь (например, первый элемент всегда перемещается в положение 3).
Mark Heath 7.02.2012 22:43:18
Просто сделать бы решить эту проблему в посте сравнения. Поскольку каждый последующий вызов будет следовать из предыдущих вызовов последний случайный результат. Random rng = new Random();static
weston 28.11.2012 13:58:48
# 2, не ясно, что версия с генератором Crypto работает, потому что максимальный диапазон байта составляет 255, поэтому любой список, который больше этого, не будет правильно перемешиваться.
Mark Sowul 8.05.2013 14:37:37

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

3
7.11.2008 19:35:19

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

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);
}
3
7.11.2008 19:35:30
list.RemoveAt - это операция O (n), которая делает эту реализацию слишком медленной.
George Polevoy 14.05.2017 21:09:06

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

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

do 
    r1 = randomPositionInList()
    r2 = randomPositionInList()
    swap elements at index r1 and index r2 
for a certain number of times
-7
7.11.2008 19:36:14
Одной из проблем этого подхода является знание того, когда остановиться. Он также имеет тенденцию преувеличивать любые смещения в генераторе псевдослучайных чисел.
Mark Bessey 7.11.2008 19:58:17
Да. Очень неэффективно. Нет смысла использовать такой подход, когда существуют лучшие, более быстрые подходы, которые столь же просты.
PeterAllenWebb 7.11.2008 21:25:34
не очень эффективно или эффективно ... Запуск его N раз, вероятно, оставил бы много элементов в их исходном положении.
NSjonas 7.12.2012 21:46:51
    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;
    }
10
7.11.2008 21:18:36
nawfal 30.05.2013 23:54:31
Разве вы не должны делать что-то вроде того, var listCopy = list.ToList()чтобы не выталкивать все элементы из входящего списка? Я действительно не понимаю, почему вы хотите изменить эти списки, чтобы очистить.
Chris Marisic 17.09.2014 17:38:13

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

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}
75
29.03.2016 10:05:27
Обратите внимание, что это не потокобезопасно, даже если используется в поточно-
BlueRaja - Danny Pflughoeft 25.09.2012 03:05:10
как мы передаем список <string> этой функции?
MonsterMMORPG 7.03.2013 12:27:00
Этот алгоритм имеет две существенные проблемы: - OrderByиспользует вариант быстрой сортировки для сортировки элементов по их (якобы случайным) ключам. Производительность быстрой сортировки - O (N log N) ; напротив, тасование Фишера-Йейтса - это O (N) . Для коллекции из 75 элементов это может не иметь большого значения, но разница станет заметной для больших коллекций.
John Beyer 26.06.2013 16:47:46
... - Random.Next()может привести к разумно псевдослучайному распределению значений, но это не гарантирует, что значения будут уникальными. Вероятность дублирования ключей растет (нелинейно) с N до тех пор, пока не достигнет определенности, когда N достигнет 2 ^ 32 + 1. OrderByQuickSort является стабильным родом; таким образом, если нескольким элементам присвоено одно и то же значение псевдослучайного индекса, их порядок в выходной последовательности будет таким же, как во входной последовательности; таким образом, смещение вводится в «перемешивание».
John Beyer 26.06.2013 17:06:48
@JohnBeyer: Есть гораздо более серьезные проблемы, чем этот источник предвзятости. В рандоме есть только четыре миллиарда возможных семян, что намного меньше, чем количество возможных случайных комбинаций умеренного размера. Только небольшая часть возможных перемешиваний может быть сгенерирована. Это смещение затмевает смещение из-за случайных столкновений.
Eric Lippert 13.09.2013 21:33:37

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

var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();
328
1.01.2017 04:18:18
Идентификаторы GUID должны быть уникальными, а не случайными. Часть из них основана на машинах, а другая - на основе времени, и лишь небольшая часть является случайной. blogs.msdn.com/b/oldnewthing/archive/2008/06/27/8659071.aspx
Despertar 5.05.2013 07:00:40
Это хорошее элегантное решение. Если вы хотите, чтобы что-то отличное от guid генерировало случайность, просто закажите что-то другое. Например: var shuffledcards = cards.OrderBy(a => rng.Next()); compilr.com/grenade/sandbox/Program.cs
grenade 27.05.2013 10:54:21
Пожалуйста, не надо. Это не верно. «случайное упорядочение» - это НЕ случайный случай: вы вносите предвзятость и, что еще хуже, рискуете пойти бесконечными циклами
Vito De Tullio 16.08.2013 10:07:34
@VitoDeTullio: Вы не помните. Вы рискуете бесконечными циклами, когда предоставляете функцию случайного сравнения ; функция сравнения требуется для получения последовательного общего заказа . Случайный ключ в порядке. Это предположение неверно, потому что направляющие не гарантируются случайными , а не потому, что техника сортировки по случайному ключу неверна.
Eric Lippert 13.09.2013 21:30:12
@Doug: NewGuidтолько гарантирует, что он дает вам уникальный GUID. Это не дает никаких гарантий относительно случайности. Если вы используете GUID для другой цели, а не для создания уникального значения, вы делаете это неправильно.
Eric Lippert 13.09.2013 21:31:20

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

8
23.05.2017 12:18:30
См. Stackoverflow.com/questions/4412405/… . Вы должны быть осведомлены уже.
nawfal 30.05.2013 23:55:34
@nawfal посмотрите мою улучшенную реализацию.
Jodrell 9.07.2014 07:46:21
хм достаточно справедливо. Это GetNextили Next?
nawfal 9.07.2014 07:57:25

Вот эффективный 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;
    }

`

0
24.01.2013 21:26:56

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

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
28.03.2013 17:29:12

Если вы не возражаете против использования двух 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);
3
21.02.2016 22:31:34

Я немного удивлен всеми неуклюжими версиями этого простого алгоритма здесь. Фишер-Йейтс (или Кнут Шаффл) немного сложнее, но очень компактен. Почему это сложно? Потому что вам нужно обратить внимание на то, 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;
}

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

117
18.11.2019 02:04:06
Не лучше ли изменить rnd (i, list.Count) на rnd (0, list.Count), чтобы можно было поменять любую карту?
Donuts 7.07.2014 06:04:05
@ Донатс - нет. Если вы сделаете это, вы добавите смещение в случайном порядке.
Shital Shah 19.07.2014 07:16:25
Разделив Swap <T> на отдельный метод, кажется, что вы вызываете много ненужных T-выделений для temp.
Clay 3.12.2015 14:52:17
Я бы поспорил, что LINQ может потенциально замедлить производительность перестановки, и это будет причиной не использовать его, особенно учитывая относительную простоту кода.
winglerw28 12.02.2016 01:26:46
Когда i = list.Count - 1, т.е. последняя итерация, я rnd.Next(i, list.Count)верну вас. Поэтому вам нужно i < list.Count -1как условие цикла. Ну, вам это не «нужно», но это экономит 1 итерацию;)
Pod 28.05.2016 20:14:03
 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);

}
0
16.06.2014 18:52:15
Добро пожаловать в переполнение стека! Пожалуйста, подумайте над тем, чтобы добавить в ваш ответ какое-то объяснение, а не просто огромный блок кода. Наша цель состоит в том, чтобы обучить людей, чтобы они понимали ответ и могли применять его в других ситуациях. Если вы прокомментируете свой код и добавите объяснение, вы сделаете свой ответ более полезным не только для человека, который задал вопрос на этот раз, но и для любого человека в будущем, у которого может быть такая же проблема.
starsplusplus 16.06.2014 19:14:39
Большая часть этого кода совершенно не имеет отношения к вопросу, и единственная полезная часть в основном повторяет ответ Адама Тегена почти 6 лет назад.
T.C. 16.06.2014 19:16:53

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

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
24.08.2014 17:48:56
Я бы оставил Randomэкземпляр класса вне функции в качестве staticпеременной. В противном случае вы можете получить такое же начальное значение рандомизации из таймера, если вызывается в быстрой последовательности.
Lemonseed 2.06.2016 16:11:40
Интересное замечание - если вы быстро создаете экземпляр класса Random в цикле, скажем, от 0 мс до 200 мс друг от друга, то у вас очень высока вероятность получения того же начального числа рандомизации, что затем приводит к повторяющимся результатам. Однако вы можете обойти это, используя Random rand = new Random (Guid.NewGuid (). GetHashCode ()); Это эффективно вынуждает рандомизацию быть полученной из Guid.NewGuid ()
Baaleos 16.02.2018 16:28:49

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

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

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

-5
21.08.2015 08:44:05
Компактно, но есть ли у вас рекомендации по сортировке последовательных новых гидов по случайному качеству? Некоторые версии quid / uuid имеют метки времени и другие неслучайные части.
Johan Lundberg 10.12.2015 14:47:23
Этот ответ уже дан, и, что еще хуже, он предназначен для уникальности, а не случайности.
Alex Angas 4.01.2016 22:21:10

Это мой предпочтительный метод случайного воспроизведения, когда желательно не изменять оригинал. Это вариант алгоритма Фишера-Йейтса «наизнанку», который работает с любой перечисляемой последовательностью (длину начала 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)];

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

3
19.09.2015 09:43:39

Простая модификация принятого ответа, которая возвращает новый список вместо того, чтобы работать на месте, и принимает более общий, 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;
}
0
8.09.2017 01:59:38

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

var result = items.Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList()
9
7.03.2020 10:06:26
лучшее решение для одного лайнера
vipin8169 8.03.2019 07:47:10
Вы пропустите точку с запятой в конце FYI
reggaeguitar 17.04.2020 17:47:39
    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.
0
1.07.2019 16:08:59