20

Есть данные, записанные в массив или генерируемые на лету. Как можно получить их случайную перестановку в массиве или другом контейнере?

Например: как можно получить случайную перестановку чисел от 1 до n в массиве/списке?

VladD
  • 206,799

3 Answers3

25

Обновление: начиная с .NET 8, проще всего не изобретать велосипед, а воспользоваться встроенной функцией Shuffle:

int[] data = [1, 2, 3, 4, 5];
Random.Shared.Shuffle(data);

(для List<T> понадобится Random.Shared.Shuffle(CollectionsMarshal.AsSpan(data));).

Дальше рассматриваем случай, когда существующий Shuffle не подходит (например, у вас более младшая версия .NET, или данные поступают в потоковом виде).


Если у вас уже есть набор данных (массив или List), скорее всего вам нужно перемешивание его «на месте». Для этого подойдёт алгоритм из 3.4.2P из TAOCP, известный также как Fisher–Yates shuffle.

Пусть ваши данные находятся в массиве T[] data. Пусть random — экземпляр типа Random*. Тогда для перемешивания подходит следующий код:

for (int i = data.Length - 1; i >= 1; i--)
{
   int j = random.Next(i + 1);
   // обменять значения data[j] и data[i]
   var temp = data[j];
   data[j] = data[i];
   data[i] = temp;
}

Код очевидным образом адаптируется для случая List<T>.


Для случая, когда вам нужна не перетасовка на месте, а заполнение данными из другого источника, или данные генерируются на ходу (например, вы хотите получить перестановку чисел 1...n), можно воспользоваться немного модифицированным алгоритмом.

Если количество данных известно заранее (пусть это будет n), делаем так:

data = new T[n];
for (int i = 0; i < n; i++)
{
    int j = random.Next(i + 1);
    if (j != i)
        data[i] = data[j];
    data[j] = generate(i);
}

Здесь generate(i) — выражение, которое даёт следующий, i-ый член исходной последовательности. Например, если данные поступают из массива source, то generate(i) — это просто source[i]. Если вы перемешиваете числа от 1 до n, это просто i + 1, и т. д.

Для случая, когда количество элементов не известно заранее (например, из произвольного IEnumerable<T>), подойдёт следующая модификация. Наш целевой контейнер должен быть List<T>, чтобы его можно было динамически увеличивать.

data = new List<T>();
foreach (var s in source)
{
    int j = random.Next(data.Length + 1);
    if (j == data.Count)
    {
        data.Add(s);
    }
    else
    {
        data.Add(data[j]);
        data[j] = s;
    }
}

Код основан на цитированной статье из Википедии.


*Если вы пользуетесь .NET Framework (но не .NET Core), не стоит создавать новый экземпляр Random каждый раз при выполнении этого алгоритма: это даёт большие шансы, что два раза подряд сгенерированная перестановка будет фактически одинаковой. Если ваша программа однопоточная, лучше всего создать единственный статический экземпляр Random в начале программы, и использовать его.

Для .NET Core этой проблемы нет, создавайте экземпляры Random, где вам удобнее.

Начиная с .NET 6, можно просто использовать потокобезопасный Random.Shared.

VladD
  • 206,799
  • Уточню, что в с++ есть встроенная функция для этого, а данный алгоритм использовать нужно крайне аккуратно из-за особенностей rand() на некоторых платформах ( слишком часто в нем только 16 последних бит). – pavel Jul 24 '16 at 15:10
  • @pavel: Да, на C++ это даже в стандартной библиотеке. Но там требуется итератор произвольного доступа, так что вариант с генерацией придётся всё равно кодировать руками. – VladD Jul 24 '16 at 15:49
  • А точно Random.Shared.Shuffle а не просто Random.Shuffle? – Grundy Nov 17 '23 at 13:54
  • а, все, увидел в конце про Shared – Grundy Nov 17 '23 at 14:01
  • @Grundy: метод Shuffle в любом случае не статический, так что Random.Shuffle не скомпилируется. – VladD Nov 17 '23 at 14:05
4

На взрослом https://stackoverflow.com/questions/273313/randomize-a-listt

Там победитель алгоритм, тот, что привел VladD

private static Random rng = new Random((int) DateTime.Now.Ticks & 0x0000FFFF);


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

Можно вспомнить БД

items.Select(i=> new {I=i, sort= Guid.NewGuid()}).OrderBy (i =>i.sort).Select(i=>i.I);

items.Select(i=> new {I=i, sort= rng.Next()}).OrderBy (i =>i.sort).Select(i=>i.I);
Serginio
  • 1,057
  • 2
    Первый вариант ничем не отличается от варианта в моём ответе. Вариант с rng.Next и Guid просто ужасен. – VladD Jul 25 '16 at 13:15
  • Ну почему же. Еще раз такой вариант применяется для получения случайных данных в БД в сочетании с TOP. Каждый вариант имеет право на жизнь. Главное даже в понимании. По скорости будет твой вариант быстрее, но с точки зрения понимания варианты с OrderBy вполне приемлемы. Заметь как проголосовали на взрослом сайте. Кроме того Enumerable не всегда List – Serginio Jul 25 '16 at 14:11
  • 2
    @Serginio дело в том, что в SQL RAND() вызывается не больше одного раза на строчку (по крайней мере в SQL Server). А в C# (linq to objects) нет никакой гарантии, что выражение, переданное в OrderBy, не вызовется дважды для одной строки. Т.е. можно наткнуться на кривую реализацию OrderBy, которая будет вызывать NewGuid при каждом попарном сравнении значений. –  Jul 25 '16 at 14:34
  • А разве ты не видел items.Select(i=> new (I=i, sort= Guid.NewGuid())).OrderBy (i =>i.sort).Select(i=>i.I); – Serginio Jul 25 '16 at 14:40
  • 2
    Кроме того, временная сложность сортировки O(N Log N), а Фишера-Ейтса O(N) – VladD Jul 25 '16 at 14:40
  • Я знаю. Я же тебе ответил в первом комментарии. Суть не в скорости. Для Linq скорость не главное, главное понимание. – Serginio Jul 25 '16 at 14:42
  • 1
    Если вы ссылаетесь на «_взрослый_» сайт, вы должны бы почитать комментарии Эрика, который говорит, что Guid не предназначен выступать в роли источника случайных чисел. – VladD Jul 25 '16 at 14:43
  • Для Linq скорость не главное а потом программы жрут памяти раз в 1000 больше и работают не быстрее чем в 2000 году, а процессоры то мощнее стали... – pavel Jul 25 '16 at 14:46
  • @ VladD Я показал алгоритмы используемые для получения случайных данных в БД. Посмотри сколько человек проголосовало за те предложения. – Serginio Jul 25 '16 at 14:48
  • @ pavel Тогда нужно брать в руки другой язык программирования. Для большинства задач Linq выше крыши. Для большинства задач нужна скорость и надежность разработки, а не скорость выполнения. Поверь мне программисту 1С – Serginio Jul 25 '16 at 14:51
  • @Serginio: Почему количество голосов на en.SO аргумент? – VladD Jul 25 '16 at 15:20
  • 1
    Просто используют то, что людям понятно. Другое дело, что Shuffle нужно вводить как стандартный метод Linq – Serginio Jul 25 '16 at 19:39
  • 1
    @Serginio на большом so за Guid отдано в 4 раза меньше голосов, чем за ФЕ. Это означает, что вариант с Guid минимум в 4 раза хуже. А если учесть его очевидную понятность, и набранные за счет этого голоса - то можно смело утверждать что он ужасен :) –  Jul 27 '16 at 14:22
  • @Serginio и кстати, linq появился как раз ради скорости - ради возможности отобразить запрос в базу данных, а не выполнять его, предварительно вычитав всю базу в память. То, что на нем можно написать неэффективный код - еще не означает что "для linq скорость не главное". Это посто означает что на linq можо написать неэффективный код, как и на всем остальном :) –  Jul 27 '16 at 14:24
  • В Linq используются делегаты, которые в отличие от C++ шаблонов не инлайнятся. Кстати для Max и Min для элементарных типов сделаны отдельные методы. Еще раз я изначально сказал, что Fisher–Yates shuffle лучше, но есть и другие подходы. Пузырьковую сортировку никто не отменял. – Serginio Jul 27 '16 at 14:41
  • @Serginio в linq используются синтаксические деревья, которые, в отличие от шаблонов C++, отображаются сразу в SQL. И, кстати, без упоминания вида @ username, без проблела, оповещения о комментариях не приходят. –  Jul 27 '16 at 14:45
  • @PashaPash Мы сейчас говорим о Linq to Object. Я знаю, что применяется. Я говорил об аналогах применения алгоритмов в БД. Да я тут недавно. Не знаю всех особенностей. Кстати по поводу линка и простых типов http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,dd1aa43ba83e50eb – Serginio Jul 27 '16 at 15:02
  • @PashaPasha Узнал, что ключи кэширутся https://github.com/Microsoft/referencesource/blob/master/System.Core/System/Linq/Enumerable.cs#L2526 – Serginio Oct 27 '16 at 13:54
  • @Serginio: Это вы прочитали в исходниках одной конкретной реализации. Это ни в коем случае не является гарантией ни для данной имплементации на будущее или на прошлое, ни для других имплементаций. Гарантией может являться только документация. Пожалуйста, не пропагандируйте некорректные, и к тому же ещё и неэффективные решения. – VladD Mar 01 '18 at 13:25
-1

не хочешь использовать Guid.NewGuid().ToString() для случайной сортировки? var lstResult = yourList.OrderBy(x => Guid.NewGuid().ToString()).ToList();

  • 3
    мы это обсуждали в другой теме, когда с точки зрения Стандарта вызывается лямбда, гарантируется ли единственный вызов для каждого элемента иначе сортировка будет совсем кривой. – pavel Jul 25 '16 at 12:59