При выполнении некоторых задач требуется перемешать случайным образом (перетасовать) массив или список с данными. Для решения данной проблемы существуют специальные алгоритмы. Рассмотрим один один из таких алгоритмов под названием Тасование Фишера-Йетса.
Алгоритм Фишера — Йетса (Современная версия)
Тасование Фишера-Йетса (Fisher–Yates shuffle) используется для выполнения случайных перестановок множества элементов. Например, массивов или списков.
На псевдокоде алгоритм можно представить следующим образом:
|
1 2 3 4 |
Чтобы перемешать массив a из n элементов (индексы элементов от 0 до n - 1): для всех i от n − 1 до 1 выполнить j ← случайное число 0 ≤ j ≤ i обменять местами a[j] и a[i] |
Ниже будут приведены реализации данного алгоритма на языках Си и C#.
Перемешать массив на Си
Перемешать элементы массива, состоящего из целых чисел, на языке программирования Си можно с помощью следующей функции shuffle (реализованной ниже). Пример программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> #include <cstdlib> #include <ctime> // arr - массив для перестановки, N - количество элементов в массиве void shuffle(int* arr, int N) { // инициализация генератора случайных чисел srand(time(NULL)); // реализация алгоритма перестановки for (int i = N - 1; i >= 1; i--) { int j = rand() % (i + 1); int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } } int main() { int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; shuffle(arr, 10); for (int i = 0; i < 10; i++) printf("%d ", arr[i]); printf("\n"); return 0; } |
Результат работы программы (изначально массив был заполнен десятичными цифрами в порядке от 0 до 9):
Можно отредактировать функцию shuffle, изменив тип данных массива, указав вместо целого типа данных int, любой другой нужный.
Перемешать массив на C#
Перемешать элементы массива целых чисел на языке C# можно с помощью следующего метода, реализующего алгоритм Фишера — Йетса:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public static void Shuffle(int[] arr) { // создаем экземпляр класса Random для генерирования случайных чисел Random rand = new Random(); for (int i = arr.Length - 1; i >= 1; i--) { int j = rand.Next(i + 1); int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } } |
Целый тип int можно заменить на любой другой, который вам потребуется.
Чтобы не дублировать код, создавая методы под каждый тип данных, можно создать один универсальный метод, используя обобщения C#:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public static void Shuffle<T>(T[] arr) { Random rand = new Random(); for (int i = arr.Length - 1; i >= 1; i--) { int j = rand.Next(i + 1); T tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } } |
Как перемешать список на C#
Тасование Фишера-Йетса также можно использовать для перемешивания списков и других коллекций. Реализуем алгоритм для случайной перестановки элементов списка List на C#, используя обобщенный тип данных.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public static void Shuffle<T>(List<T> list) { Random rand = new Random(); for (int i = list.Count - 1; i >= 1; i--) { int j = rand.Next(i + 1); T tmp = list[j]; list[j] = list[i]; list[i] = tmp; } } |
Для более удобного использования метода перемешивания элементов, можно создать потомка класса коллекции (например списка) и реализовать в классе-потомке данный метод.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class MyList<T> : List<T> { public void Shuffle() { Random rand = new Random(); for (int i = this.Count - 1; i >= 1; i--) { int j = rand.Next(i + 1); T tmp = this[j]; this[j] = this[i]; this[i] = tmp; } } } |
Дальнейшее создание списка и применение метода перемешивания элементов, будет реализовываться следующим образом:
|
1 2 3 4 5 6 |
MyList<int> myList = new MyList<int>(); for (int i = 0; i < 10; i++) myList.Add(i); myList.Shuffle(); |
Стоит отметить, что в языке Java у коллекций (например у ArrayList) уже есть реализованный метод с названием shuffle, перемешивающий элементы.
Поделиться в соц. сетях: