Как перемешать массив или список — Программирование на C, C# и Java

При выполнении некоторых задач требуется перемешать случайным образом (перетасовать) массив или список с данными. Для решения данной проблемы существуют специальные алгоритмы. Рассмотрим один один из таких алгоритмов под названием Тасование Фишера-Йетса.

Алгоритм Фишера — Йетса (Современная версия)

Тасование Фишера-Йетса (Fisher–Yates shuffle) используется для выполнения случайных перестановок множества элементов. Например, массивов или списков.

На псевдокоде алгоритм можно представить следующим образом:

Чтобы перемешать массив a из n элементов (индексы элементов от 0 до n - 1):
  для всех i от n − 1 до 1 выполнить
       j ← случайное число 0 ≤ j ≤ i
       обменять местами a[j] и a[i]

Чтобы перемешать массив a из n элементов (индексы элементов от 0 до n - 1):

для всех i от n − 1 до 1 выполнить

j ← случайное число 0 ≤ j ≤ i

обменять местами a[j] и a[i]

Ниже будут приведены реализации данного алгоритма на языках Си и C#.

Перемешать массив на Си

Перемешать элементы массива, состоящего из целых чисел, на языке программирования Си можно с помощью следующей функции shuffle (реализованной ниже). Пример программы:

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

#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# можно с помощью следующего метода, реализующего алгоритм Фишера — Йетса:

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

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#:

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

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#, используя обобщенный тип данных.

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

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;

}

Для более удобного использования метода перемешивания элементов, можно создать потомка класса коллекции (например списка) и реализовать в классе-потомке данный метод.

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

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;

}

Дальнейшее создание списка и применение метода перемешивания элементов, будет реализовываться следующим образом:

MyList<int> myList = new MyList<int>();

for (int i = 0; i < 10; i++)
    myList.Add(i);

myList.Shuffle();

MyList<int> myList = new MyList<int>();

for (int i = 0; i < 10; i++)

myList.Add(i);

myList.Shuffle();

Стоит отметить, что в языке Java у коллекций (например у ArrayList) уже есть реализованный метод с названием shuffle, перемешивающий элементы.

4.5/5 - (16 голосов)

C, c#, List, Алгоритм, Код, Коллекция, Массивы, Реализация, Списки

Поделиться в соц. сетях:

Алгоритм Фишера — Йетса (Современная версия)

Перемешать массив на Си

Перемешать массив на C#

Как перемешать список на C#

Добавить комментарий Отменить ответ