Произвести случайный выбор списка <T>
Как лучше всего рандомизировать порядок общего списка в C#? У меня есть конечный набор из 75 чисел в списке, которому я хотел бы назначить случайный порядок, чтобы нарисовать их для приложения типа лотереи.
Возможно, вас заинтересует этот пакет NuGet, который содержит методы расширения для перетасовки IList <T> и IEnumerable <T> с использованием алгоритма Фишера-Йейтса, упомянутого ниже.
@Natan fyi, они его убили
Также есть связанные обсуждения Выберите N случайных элементов из списка <T> и Перемешать с помощью OrderBy vs. Fisher-Yates.
Может у вас есть бесконечный набор из 75 чисел;)?
@Natan, они закрыли вопрос, потому что кто-то «работал над многими проектами и разработал множество библиотек и никогда не нуждался в таком методе», что меня разозлило. Теперь нам нужно исследовать себя, искать лучшие реализации, тратить время на то, чтобы просто изобретать велосипед.
Я правильно понимаю? Ни одного действительного функционального ответа за 10 лет? Может быть, нам нужна еще одна награда для решения, которое учитывает количество необходимой энтропии, чтобы перемешать список с 75 числами $ log2 (75!) = 364 $ и как мы можем это получить. Даже криптографически защищенный ГСЧ с 256 битами энтропии потребуется повторно загрузить хотя бы один раз во время тасования Фишера-Ятса.
И если обычный кодер не может решить эту проблему, все ли мы вечно играем в одни и те же 0,01% возможных пасьянсов?
Ответы 25
Если у вас есть фиксированное число (75), вы можете создать массив из 75 элементов, а затем пронумеровать свой список, перемещая элементы в рандомизированные позиции в массиве. Вы можете сгенерировать отображение номера списка в индекс массива, используя Перемешивание Фишера-Йетса.
Обычно я использую:
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);
}
list.RemoveAt - это операция O (n), что делает эту реализацию чрезмерно медленной.
Очень простой подход к этой проблеме - использовать произвольное количество элементов в списке.
В псевдокоде это будет выглядеть так:
do
r1 = randomPositionInList()
r2 = randomPositionInList()
swap elements at index r1 and index r2
for a certain number of times
Одна из проблем этого подхода - знать, когда остановиться. Он также имеет тенденцию преувеличивать любые смещения в генераторе псевдослучайных чисел.
да. Очень неэффективно. Нет причин использовать подобный подход, когда существуют более быстрые и более эффективные подходы, которые так же просты.
не очень эффективно или эффективно ... Запуск его N раз, скорее всего, оставит многие элементы в исходном положении.
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;
}
См. stackoverflow.com/questions/4412405/…
Разве вам не следует сделать что-то вроде var listCopy = list.ToList(), чтобы не выскакивать все элементы из списка входящих? Я действительно не понимаю, почему вы хотите изменить эти списки на пустые.
Перемешайте любой (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;
}
}
}
}
Хороший! Обожаю методы расширения: D
Обратите внимание, что производительность этого значительно ниже в LinkedLists по сравнению с ArrayLists. Обязательно отправляйте ему индексируемый массив производительности O (1).
@Jedi, если бы это было серьезной проблемой, возможно, было бы полезно создать список вторичного хранилища или массив, выполнить там перетасовку и заменить им содержимое списка.
Что, если list.Count> Byte.MaxValue? Если n = 1000, то 255/1000 = 0, поэтому цикл do будет бесконечным, поскольку box [0] <0 всегда ложно.
Хочу отметить, что сравнение некорректно. Проблема заключается в использовании <code> new Random () </code> в цикле, а не в случайности <code> Random </code> Объяснение
Рекомендуется передать экземпляр Random в метод Shuffle, а не создавать его внутри, как если бы вы вызывали Shuffle много раз в быстрой последовательности (например, перетасовывая много коротких списков), все списки будут перемешаны в одном и том же способ (например, первый элемент всегда перемещается в позицию 3).
В вашей сравнительной статье немного не хватает сути. System.Random не так плох, как вы показываете. new Random() - это с использованием зависящего от времени начального значения по умолчанию, поэтому в вашем тесте вообще нет рандомизации. По истинной причине см. boallen.com/random-numbers.html, но опять же, это немного зависит от ОС, поэтому System.Random может работать лучше или нет.
Простое преобразование Random rng = new Random(); в static решило бы проблему в сравнительной публикации. Поскольку каждый последующий вызов будет следовать за последним случайным результатом предыдущих вызовов.
Не забудьте удалить случайного поставщика после того, как закончите его использовать.
Создание статического значения Random - опасная идея, потому что теперь этот метод не является потокобезопасным. А как насчет точки AndrewS в «безопасной» версии?
Я буду честен @MarkSowul и скажу вам, что я мало знаю об опасностях статики или безопасности потоков. Съедут ли меня львы, заставят ли меня пони или с какими опасностями я столкнусь? Я также не знаю ответа или заявления, что понимаю вопрос, заданный AndrewS.
Если два разных потока используют версию с общим ГСЧ одновременно, ГСЧ может повредить свое состояние, поскольку он не является потокобезопасным (stackoverflow.com/a/11109361/155892).
# 2, неясно, работает ли версия с генератором криптографии, потому что максимальный диапазон байта равен 255, поэтому любой список большего размера не будет правильно перемешиваться.
Я согласен с тем, что моя идея не была потокобезопасной, и поскольку вы не понимали проблем безопасности потоков, я добавил класс ThreadSafeRandom на основе собственного ответа Марка Соулса, надеюсь, это круто!
Если бы вы использовали ThreadSafeRandom в ASP.NET, я полагаю, вы бы сгенерировали много экземпляров Local. Я бы даже не подумал, что они будут собирать мусор, пока AppDomain не сломается.
зачем делать provider.GetBytes (box); в то время как (! (поле [0] <n * (Byte.MaxValue / n))); int k = (коробка [0]% n); вместо do provider.GetBytes (box); в то время как (поле [0]> = n); int k = box [0];
Скажем, кто-то хочет предоставить копию перетасованного списка, сохранив оригинал нетронутым. Как бы это сделать?
Несмотря на то, что существует новая и улучшенная поточно-ориентированная версия, у вас все равно будет та же проблема, если один поток вызывает Shuffle в тесном цикле. Я отредактировал исходный пример, чтобы люди, которые просто копируют и вставляют решение, не читая обсуждения, не столкнутся с проблемой жесткого цикла.
@Will: Сделайте копию перед перемешиванием и перемешайте эту копию. Для этого отлично подойдет метод расширения Linq .ToList (), но обратите внимание, если у вас есть список ссылочного типа, оба будут ссылаться на исходный объект, например. если у вас есть List<Person> a = LoadSomehow(); List<Person> b = a.ToList(); b.Shuffle<string>();, в двух списках будут одинаковые экземпляры Person, но в разном порядке.
Необходимо внимательно изучить количество бит энтропии в вашем ГПСЧ. Например, чтобы перетасовать колоду из 52 карт и получить все возможные перетасованные колоды, и сделать это с равной вероятностью, вам нужен PRNG как минимум с 226-битным семенем! Пожалуйста, не используйте методы в этом ответе для перетасовки вещей, когда требуется равная вероятность всех возможных результатов , если вы не выполните надлежащие компьютерные науки, чтобы убедиться, что он работает правильно.
Ваш пример RNGCryptoServiceProvider работал для меня бесконечно
Я бы внес в это небольшое изменение, а именно, чтобы он копировал входящий список, перетасовывал этот новый список и возвращал его. Тогда вы можете делать такие вещи, как var shuffledList = originalList.Shuffle();
К сожалению, я не могу использовать поточно-ориентированную версию, так как я использую VB.NET, и нет unchecked или подходящей альтернативы.
В чем смысл условия цикла do while? Почему бы просто не взять байт и затем выполнить% list.Count?
Чтобы достичь хорошей энтропии с лучшей производительностью, без глупого цикла while или ограничения в 255 элементов, вы можете предварительно рассчитать количество случайных байтов, необходимых для выполнения алгоритма до завершения (sizeof(int) * (list.Count - 1) или long при работе с необработанными массивами) и заполнить байтовый массив одним вызовом GetBytes(). Затем оберните этот массив байтов в MemoryStream с помощью конструктора упаковки (практически бесплатно) и прочтите из него случайные целые числа с помощью BinaryReader. Не забывайте утилизировать одноразовые экземпляры! (Вы можете поддерживать более крупные списки, создав кольцевой буфер.)
зачем вам нужен случайный экземпляр, чтобы быть потокобезопасным? насколько я вижу, ваш код выполняет все вычисления в 1 потоке
Я думаю, что ваша реализация RNGCryptoServiceProvider создаст неопределенную случайность, когда количество списков превышает 255. У него также есть тенденция к бесконечному циклу по количеству списков. Доработка ниже: int RandomInteger () {cryptoServiceProvider.GetBytes (randomIntegerBuffer); вернуть BitConverter.ToInt32 (randomIntegerBuffer, 0); } var result = from item in source let record = new {Item = item, RandomKey = RandomInteger ()} orderby record.RandomKey select record.Item;} var result = from элемент в источнике let record = new {Item = item, RandomKey = RandomInteger ()} orderby record.RandomKey select record.Item;
Мне пришлось изменить счетчик массива, поскольку он вырезал отсутствующий индекс массива 0 int listSize = list.Count; while (listSize> 0) // пока список больше 0, конечно, я новичок - так что я тоже могу делать это странно: P
@grenade, мне нравится ваш ответ, но как вы избежали появления этой ошибки: error CS1061: Type System.Collections.Generic.List <Deck> 'не содержит определения для Shuffle' and no extension method Shuffle' типа System.Collections.Generic.List<Deck>' could be found.
@William Я столкнулся именно с этой проблемой, просто попытка перетасовать 1000 элементов приводит к бесконечному циклу. НЕ ИСПОЛЬЗУЙТЕ первую версию метода в ответе.
Мне просто любопытно. Неужели нужно сначала вычесть 1 из n, а затем добавить обратно? Кроме того, операторы посткремента создают дополнительный экземпляр, поэтому с точки зрения производительности лучше использовать здесь оператор прекремента. При этом я бы изменил две строчки на следующие: первая int k = ThreadSafeRandom.ThisThreadsRandom.Next(n); вторая --n. Но в любом случае я благодарен вам за предоставленный алгоритм.
Метод расширения для IEnumerable:
public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
Random rnd = new Random();
return source.OrderBy<T, int>((item) => rnd.Next());
}
Обратите внимание, что это не потокобезопасный, даже если используется в многопоточном списке.
У этого алгоритма есть две существенные проблемы: - OrderBy использует вариант QuickSort для сортировки элементов по их (предположительно случайным) ключам. Производительность QuickSort - O (N войти N); в отличие от этого тасование Фишера-Йетса - НА). Для коллекции из 75 элементов это может не иметь большого значения, но разница станет заметной для больших коллекций.
... - Random.Next() может создавать достаточно псевдослучайное распределение значений, но нет гарантирует, что значения будут уникальными. Вероятность дублирования ключей растет (нелинейно) с N до тех пор, пока не достигнет достоверности, когда N достигнет 2 ^ 32 + 1. OrderBy QuickSort - это сортировка стабильный; таким образом, если нескольким элементам будет присвоено одно и то же значение псевдослучайного индекса, то их порядок в выходной последовательности будет такой же, как во входной последовательности; таким образом, в "тасование" вносится перекос.
@JohnBeyer: Есть гораздо более серьезные проблемы, чем этот источник предвзятости. В Random есть только четыре миллиарда возможных начальных чисел, что намного меньше, чем количество возможных перетасовок для набора среднего размера. Может быть сгенерирована лишь малая часть возможных перетасовок. Это смещение затмевает смещение из-за случайных столкновений.
Если нам нужно только перемешать элементы в полностью случайном порядке (просто чтобы смешать элементы в списке), я предпочитаю этот простой, но эффективный код, который упорядочивает элементы по руководству ...
var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();
Это использование метода Linq для изменения порядка в списке. NewGuid создает случайный Гид (16-байтовое значение). Сортировать по использует предоставленную функцию для присвоения сопоставимого объекта каждой карте, а затем возвращает новую коллекцию, упорядоченную по Guids. Поскольку Guid очень длинные, вероятность столкновения (один и тот же Guid для двух разных объектов) очень мала.
Как вернуть это в список? list = (List <string>) list.OrderBy () является недопустимым приведением
@Mark list.OrderyBy (...). ToList ();
GUID должны быть уникальными, а не случайными. Часть из них основывается на машинах, другая - на части рабочего времени, и лишь небольшая часть является случайной. blogs.msdn.com/b/oldnewthing/archive/2008/06/27/8659071.aspx
Это красивое элегантное решение. Если вы хотите, чтобы что-то другое, кроме руководства, генерировало случайность, просто закажите что-нибудь еще. Например: var shuffledcards = cards.OrderBy(a => rng.Next());compilr.com/grenade/sandbox/Program.cs
Обратите внимание, что только определенные типы GUID являются машинными или временными. GUID, созданные таким образом (Guid.NewGuid ()), не являются ни машинными, ни временными (то есть последовательными GUID). Это хороший способ перемешать список.
Еще одна вещь, на которую следует обратить внимание, - это то, что лямбда может вызываться несколько раз, и в этом случае она будет возвращать разные значения для одного и того же элемента. Это может замедлить сортировку. Однако я не знаю, относится ли это к стандартной реализации OrderBy. В любом случае я бы рекомендовал использовать тасование Фишера-Йейтса.
Пожалуйста, не надо. Это не правильно. "случайное упорядочение" - это НЕ случайный выбор: вы вносите предвзятость и, что еще хуже, рискуете зайти в бесконечные циклы
@VitoDeTullio: Вы не помните. Вы рискуете бесконечными циклами, если предоставите случайный функция сравнения; функция сравнения необходима для получения согласованного общий заказ. Случайный ключ - это нормально. Это предложение неверно, потому что не гарантируется, что гиды будут случайными, а не потому, что неправильна техника сортировки по случайному ключу.
@Doug: NewGuid гарантирует только то, что дает вам уникальный GUID. Это не дает никаких гарантий относительно случайности. Если вы используете GUID не для создания значения уникальный, вы делаете это неправильно.
@Eric - Вы правы, это, вероятно, не самый случайный способ перемешать список. Для заинтересованных: stackoverflow.com/questions/2621563/…
+1 Мне это непонятно, но это простое и единственное решение, которое сработало, спасибо!
Он выполняет свою работу элегантно. Многие люди просто хотят перемешать свои списки и не заботятся о том, насколько они случайны. Они предпочитают этот метод любому другому, более академическому методу. Я знаю, что. Спасибо!
Спасибо за этот ответ, иногда вам просто нужен простой способ немного перетасовать вещи, и, похоже, это все.
Есть ли гарантия, что ключевая функция вызывается только один раз для каждого элемента? (Я не нашел упоминания об этом в документации.) Если так, то это довольно элегантно. В противном случае этот код действительно рискует бесконечными циклами (или увеличением времени выполнения) и другими трудно предсказуемыми несоответствиями.
@RolandIllig - Как это может привести к бесконечной петле?
@RolandIllig (1) OrderBy(x => x.Id) (2) Orderby(x => 5) (3) OrderBy(x => rng.Next()) Ничто из этого не создает бесконечного цикла. ценить, выбранный в OrderBy, не влияет на обработку элементов. Каждый элемент в списке получит свое значение ровно один раз. Обратите внимание, что вы были бы правы, если, например, OrderBy был пузырьковой сортировкой, при которой значения не кэшировались; но здесь дело обстоит не так.
@Flater «Каждый элемент в списке получит свое значение ровно один раз» - говорит кто?
@RolandIllig Enumerable.Range(0,10).OrderBy(x => GetRandomNumberAndLogMessageToConsole()); Полагаю, название достаточно информативное.
@RolandIllig: Также на pastebin для вашего удобства.
Это отличный ответ, но я хочу добавить предупреждение людям, использующим его: это плохая идея, если у вас действительно большие списки. Обозначение O (n) для .OrderBy (RandomFunc) - это n * log (n), а не n. Для 1-1000 записей это не имеет большого значения. Для миллиона записей это будет примерно в 100 раз медленнее; для миллиарда записей это будет в ~ 1000 раз медленнее.
Такая «случайность» привела к ошибке в моем приложении, на поиск которой потребовалось 4 дня (списки всегда были не случайными). Просто не делай этого.
Это простое решение для не криптографических целей.
Это НЕ решение заданного вопроса. Вопрос в том, «как СЛУЧАЙНО ИЗМЕНИТЬ список». Этот ответ не случаен. Это необъективно. Конечно, он может перемешать список элементов, но не случайным образом. Случайный означает, что все уникальные комбинации могут возникать с равномерным распределением.
Фантастически, как это продолжает развиваться. Если вы посмотрите на исходный код в ядре dotnet, Guid.NewGuid() делает, как люди говорят, извлекает из вызова взаимодействия в Windows ... если вы работаете в Windows. Однако каждая другая ОС использует RNGCryptoServiceProvider , который, безусловно, является производным делает из случайных байтов.
РЕДАКТИРОВАТЬ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 не является потокобезопасной или криптографически достаточно надежной для ваших нужд, вы можете внедрить свою реализацию в операцию.
Вот идея, расширить 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]];
}
См. stackoverflow.com/questions/4412405/…. вы уже должны знать.
@nawfal см. мою улучшенную реализацию.
хм достаточно честно. Это GetNext или Next?
Вот эффективный Shuffler, который возвращает байтовый массив перемешанных значений. Он никогда не перетасовывает больше, чем нужно. Его можно перезапустить с того места, где он был ранее остановлен. Моя фактическая реализация (не показана) - это компонент MEF, который позволяет использовать указанную пользователем замену.
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;
}
`
Вот поточно-ориентированный способ сделать это:
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());
}
}
Если вы не против использования двух 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);
Меня немного удивили все неуклюжие версии этого простого алгоритма. Фишер-Йейтс (или перетасовка Кнута) немного сложен, но очень компактен. Почему это сложно? Потому что вам нужно обратить внимание на то, возвращает ли ваш генератор случайных чисел 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), чтобы можно было заменить любую карту?
@Donuts - нет. Если вы сделаете это, вы добавите смещения в случайном порядке.
Выделив Swap <T> на отдельный метод, похоже, вы вызываете много ненужных выделений T для temp.
Я бы сказал, что LINQ потенциально может снизить производительность перетасовки, и это будет причиной не использовать его, особенно с учетом относительной простоты кода.
Когда i = list.Count - 1, то есть последняя итерация, rnd.Next(i, list.Count) вернет вам i. Следовательно, вам нужен i < list.Count -1 как условие цикла. Что ж, вам это не нужно, но экономит 1 итерацию;)
Этот код не работает должным образом. Последний номер всегда 0 или list.Count-1.
Не удалось заменить вызов list.Swap на ... var n = rnd.Next(0, i); (list[0], list[n]) = (list[n], list[0]);
@ShitalShah Текущий код в вашем ответе не дает правильных результатов, потому что это неправильная перетасовка Фишера-Ятса. Это должно быть исправлено, как и код в ссылке.
@Trisibo - не могли бы вы привести пример, в котором результат неверен?
Этот код не работает. Если вы использовали список строк из 3 букв, «A», «B» и «C», CBA и BCA буквально никогда не использовались бы при использовании этой функции из-за этой строки: list.Swap(0, rnd.Next(0, i)); переключение на следующие исправляет это и делает его работающей, непредвзятой псевдослучайной функцией: list.Swap(i-1, rnd.Next(0, i));
@GarrisonBecker прав, это единственное изменение, кажется, исправляет. Я пробовал ваш код, просто перетасовывая массив из 5 чисел (от 0 до 4) много раз (скажем, 1000000), объединяя результат каждой позиции в другой массив, а затем получая среднее значение для каждой позиции (значение / итерации); все средние значения должны быть похожи и довольно близки к 2, но это не так, например, первые 2 - около 1,4, а последнее - около 3,2.
Алгоритм неверен и всегда меняет местами с позицией 0. Это означает, что некоторые элементы будут отсортированы, но если rnd.Next () никогда не выберет элемент, он останется в покое. Для первой итерации, когда i = Count, если rnd.Next () не выбирает i-1, последний элемент никогда не будет перемещен. Простое рассмотрение списка после этого перемешивания покажет, что чем ближе элемент к концу, тем больше вероятность, что он находится в той же позиции, в которой он был начат. Исправление Гаррисона Беккера верное - замените Swap (0, ...) на Своп (i-1, ...)
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);
}
Добро пожаловать в Stack Overflow! Пожалуйста, подумайте о добавлении некоторых пояснений к вашему ответу, а не просто огромного блока кода. Наша цель - научить людей понимать ответ и применять его в других ситуациях. Если вы прокомментируете свой код и добавите объяснение, вы сделаете свой ответ более полезным не только для человека, задавшего вопрос на этот раз, но и для всех в будущем, у кого может быть такая же проблема.
Большая часть этого кода совершенно не имеет отношения к вопросу, а единственная полезная часть в основном повторяет ответ Адама Тегена почти 6 лет назад.
Вы можете добиться этого, используя этот простой метод расширения
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);
}
Я бы оставил экземпляр класса Random вне функции как переменную static. В противном случае вы можете получить то же семя рандомизации от таймера, если вызываете его быстро.
Интересное замечание: если вы быстро создаете экземпляр класса Random в цикле, скажем, между 0 и 200 мс друг друга, то у вас очень высока вероятность получить одно и то же семя рандомизации, что затем приведет к повторению результатов. Однако вы можете обойти это, используя Random rand = new Random (Guid.NewGuid (). GetHashCode ()); Это фактически заставляет рандомизацию быть полученной из Guid.NewGuid ()
Старый пост точно, но я просто использую GUID.
Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList();
Идентификатор GUID всегда уникален, и поскольку он восстанавливается каждый раз, когда результат изменяется каждый раз.
Компактный, но есть ли у вас ссылка на сортировку последовательных новых гидов, чтобы они были высококачественными случайными? Некоторые версии quid / uuid имеют отметки времени и другие неслучайные части.
Этот ответ уже был дан, и, что еще хуже, он рассчитан на уникальность, а не на случайность.
Это мой предпочтительный метод перемешивания, когда желательно не изменять оригинал. Это вариант Алгоритм Фишера – Йейтса «наизнанку», который работает с любой перечислимой последовательностью (длину 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);
Смысл генерации случайного числа double (исключительно от 0 до 1) заключается в использовании для масштабирования до целочисленного решения. Если вам нужно выбрать что-то из списка, основанного на случайном двойном x, который всегда будет 0 <= x && x < 1, это просто.
return list[(int)(x * list.Count)];
Наслаждаться!
Простая модификация принятый ответ, которая возвращает новый список вместо работы на месте и принимает более общий 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;
}
Идея состоит в том, чтобы получить анонимный объект с элементом и случайным порядком, а затем переупорядочить элементы в этом порядке и вернуть значение:
var result = items.Select(x => new { value = x, order = rnd.Next() })
.OrderBy(x => x.order).Select(x => x.value).ToList()
лучшее решение с одним вкладышем
В конце отсутствует точка с запятой.
Если кто-то не уверен насчет rnd, добавьте это перед приведенным выше кодом. Random rnd = new Random ();
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.
Я нашел интересное решение в сети.
Предоставлено: https://improveandrepeat.com/2018/08/a-simple-way-to-shuffle-your-lists-in-c/
var shuffled = myList.OrderBy (x => Guid.NewGuid ()). ToList ();
Это блестяще.
Кредиты принадлежат оригинальному автору!
Вот реализация тасования Фишера-Йейтса, которая позволяет указать количество возвращаемых элементов; следовательно, нет необходимости сначала сортировать всю коллекцию, прежде чем взять желаемое количество элементов.
Последовательность замены элементов обратная по умолчанию; и переходит от первого элемента к последнему, так что получение подмножества коллекции дает ту же (частичную) последовательность, что и перетасовка всей коллекции:
collection.TakeRandom(5).SequenceEqual(collection.Shuffle().Take(5)); // true
Этот алгоритм основан на (современной) версии Перемешивание Фишера-Йетса Дюрстенфельда в Википедии.
public static IList<T> TakeRandom<T>(this IEnumerable<T> collection, int count, Random random) => shuffle(collection, count, random);
public static IList<T> Shuffle<T>(this IEnumerable<T> collection, Random random) => shuffle(collection, null, random);
private static IList<T> shuffle<T>(IEnumerable<T> collection, int? take, Random random)
{
var a = collection.ToArray();
var n = a.Length;
if (take <= 0 || take > n) throw new ArgumentException("Invalid number of elements to return.");
var end = take ?? n;
for (int i = 0; i < end; i++)
{
var j = random.Next(i, n);
(a[i], a[j]) = (a[j], a[i]);
}
if (take.HasValue) return new ArraySegment<T>(a, 0, take.Value);
return a;
}
Ваш вопрос в том, как рандомизировать список. Это означает:
- Должны быть возможны все уникальные комбинации.
- Все уникальные комбинации должны происходить с одним и тем же распределением (AKA не является необъективным).
Большое количество ответов, опубликованных на этот вопрос, НЕ удовлетворяют двум приведенным выше требованиям для того, чтобы быть "случайными".
Вот компактная, несмещенная псевдослучайная функция, соответствующая методу тасования Фишера-Йейтса.
public static void Shuffle<T>(this IList<T> list, Random rnd)
{
for (var i = list.Count-1; i > 0; i--)
{
var randomIndex = rnd.Next(i + 1); //maxValue (i + 1) is EXCLUSIVE
list.Swap(i, randomIndex);
}
}
public static void Swap<T>(this IList<T> list, int indexA, int indexB)
{
var temp = list[indexA];
list[indexA] = list[indexB];
list[indexB] = temp;
}
Обратите внимание, что первое требование будет зависеть от ГПСЧ (или другого ГСЧ) по крайней мере в той же степени, в какой это зависит от метода перетасовки. Например, если период ГПСЧ меньше количества перестановок в списке, то есть некоторые перестановки, которые ГПСЧ выбрать не может. (Это сделано с учетом того, что для некоторых приложений и для достаточно большого списка, как правило, более важно, чтобы перемешивание выполнялось случайным образом, чем выбор из всех перестановок.)
Просто хотел предложить вариант с использованием IComparer<T> и List.Sort():
public class RandomIntComparer : IComparer<int>
{
private readonly Random _random = new Random();
public int Compare(int x, int y)
{
return _random.Next(-1, 2);
}
}
Использование:
list.Sort(new RandomIntComparer());
Можно использовать метод расширения Shuffle из пакета morelinq, он работает на IEnumerables
install-package morelinq
using MoreLinq;
...
var randomized = list.Shuffle();
private List<GameObject> ShuffleList(List<GameObject> ActualList) {
List<GameObject> newList = ActualList;
List<GameObject> outList = new List<GameObject>();
int count = newList.Count;
while (newList.Count > 0) {
int rando = Random.Range(0, newList.Count);
outList.Add(newList[rando]);
newList.RemoveAt(rando);
}
return (outList);
}
использование :
List<GameObject> GetShuffle = ShuffleList(ActualList);
Неоптимальный вариант fisher-yates, что тоже разрушает список источников. Принятый ответ - лучший способ, больше не нужно публиковать способы сделать это.
Существует нерешенная проблема интеграции этой функции в .NET: github.com/dotnet/corefx/issues/461