Как перемешать (случайно переставить) элементы в массиве?
1,00
р.
Есть данные, записанные в массив или генерируемые на лету. Как можно получить их случайную перестановку в массиве или другом контейнере?
Например: как можно получить случайную перестановку чисел от 1 до n в массиве/списке?
Ответ
Обновление: начиная с .NET 8, проще всего не изобретать велосипед, а воспользоваться встроенной функцией Shuffle:
int[] data = [1, 2, 3, 4, 5] Random.Shared.Shuffle(data)
(для List понадобится 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.
Для случая, когда вам нужна не перетасовка на месте, а заполнение данными из другого источника, или данные генерируются на ходу (например, вы хотите получить перестановку чисел 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), подойдёт следующая модификация. Наш целевой контейнер должен быть List, чтобы его можно было динамически увеличивать.
data = new List() 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.
Например: как можно получить случайную перестановку чисел от 1 до n в массиве/списке?
Ответ
Обновление: начиная с .NET 8, проще всего не изобретать велосипед, а воспользоваться встроенной функцией Shuffle:
int[] data = [1, 2, 3, 4, 5] Random.Shared.Shuffle(data)
(для List понадобится 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.
Для случая, когда вам нужна не перетасовка на месте, а заполнение данными из другого источника, или данные генерируются на ходу (например, вы хотите получить перестановку чисел 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), подойдёт следующая модификация. Наш целевой контейнер должен быть List, чтобы его можно было динамически увеличивать.
data = new List() 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.
