20

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

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

3 ответа 3

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.

5
  • Уточню, что в с++ есть встроенная функция для этого, а данный алгоритм использовать нужно крайне аккуратно из-за особенностей rand() на некоторых платформах ( слишком часто в нем только 16 последних бит).
    – pavel
    Commented 24 июл. 2016 в 15:10
  • @pavel: Да, на C++ это даже в стандартной библиотеке. Но там требуется итератор произвольного доступа, так что вариант с генерацией придётся всё равно кодировать руками.
    – VladD
    Commented 24 июл. 2016 в 15:49
  • А точно Random.Shared.Shuffle а не просто Random.Shuffle?
    – Grundy
    Commented 17 нояб. 2023 в 13:54
  • а, все, увидел в конце про Shared
    – Grundy
    Commented 17 нояб. 2023 в 14:01
  • @Grundy: метод Shuffle в любом случае не статический, так что Random.Shuffle не скомпилируется.
    – VladD
    Commented 17 нояб. 2023 в 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);
19
  • 2
    Первый вариант ничем не отличается от варианта в моём ответе. Вариант с rng.Next и Guid просто ужасен.
    – VladD
    Commented 25 июл. 2016 в 13:15
  • 2
    @Serginio дело в том, что в SQL RAND() вызывается не больше одного раза на строчку (по крайней мере в SQL Server). А в C# (linq to objects) нет никакой гарантии, что выражение, переданное в OrderBy, не вызовется дважды для одной строки. Т.е. можно наткнуться на кривую реализацию OrderBy, которая будет вызывать NewGuid при каждом попарном сравнении значений.
    – user177221
    Commented 25 июл. 2016 в 14:34
  • 2
    Кроме того, временная сложность сортировки O(N Log N), а Фишера-Ейтса O(N)
    – VladD
    Commented 25 июл. 2016 в 14:40
  • 1
    Если вы ссылаетесь на «взрослый» сайт, вы должны бы почитать комментарии Эрика, который говорит, что Guid не предназначен выступать в роли источника случайных чисел.
    – VladD
    Commented 25 июл. 2016 в 14:43
  • 1
    Просто используют то, что людям понятно. Другое дело, что Shuffle нужно вводить как стандартный метод Linq
    – Serginio
    Commented 25 июл. 2016 в 19:39
-1

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

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.