Информатика

Перетасовка списка или массива

Несколько методов с использованием псевдослучайных чисел.

Псевдослучайные числа — это числа, генерируемые детерминированными процессами, вычисляющими кажущиеся случайными числа. Часто они используются для оптимизации тех или иных алгоритмов; например, тестирование на простоту можно сделать намного проще, используя рандомизированные алгоритмы. Одним из применений псевдослучайных чисел является рандомизация списка. Перетасовка — это процесс случайного перемещения элементов списка или массива; сами элементы остаются прежними, но меняется их положение.

Это называется перестановкой исходного списка. Каждый элемент может находиться в другой позиции в перестановке, хотя это не всегда так. Например, перестановка списка [1, 2, 3, 4] может быть [1, 3, 2, 4]; хотя некоторые элементы находятся на том же месте, некоторые сместились со своих предыдущих позиций, как второй элемент. Перетасовка этого списка приведет к перестановке, а повторная перетасовка приведет к другой перестановке.

Свойства операции перетасовки

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

Поскольку перетасовка списка не является обратимой операцией, мы не можем отменить операцию перетасовки, используя другую перетасовку; нет обратного перемешивания. Таким образом, оператор равенства не обязательно выполняется при многократном перемешивании. Тогда мы можем сказать, что многократное применение оператора тасования не гарантирует, что мы когда-нибудь снова увидим тот же порядок элементов.

На самом деле, хотя статистически это очень маловероятно, вполне возможно, что мы никогда больше не увидим прежнее расположение и порядок, несмотря на перетасовку бесконечное количество раз. Давайте предположим, что у нас есть генератор случайных чисел с заполнением, что означает, что мы получаем одни и те же случайные числа каждый раз, когда запускаем алгоритм перетасовки. Если мы позволим перетасовать в степени n, представим перетасовку n раз.

Это свойство может иметь место.

Точно так же мы могли бы получать одни и те же элементы каждый раз после перетасовки каждый раз, хотя это почти так же маловероятно. Вероятность получения любого одного расположения элементов после перетасовки списка уникальных элементов будет на единицу выше факториала N, где факториал представляет общее количество возможных расположений этого списка, и N — количество элементов в списке.

Мы можем использовать это для проверки статистической правильности алгоритма. Если мы проведем определенное количество перетасовок и обнаружим, что вероятность каждой перетасовки приближается к этой вероятности, то наша перетасовка статистически верна.

Приложения перетасовки

Это полезно в играх, обработке текста, геномике и комбинаторике. Перемешанные списки букв в слове превращают слово в анаграмму. Например, лунный наблюдатель — это анаграмма для астронома. Известно, что в Гарри Поттере я — Лорд Волан-де-Морт был анаграммой Тома Марволо Риддла.

Перетасовка может использоваться в алгоритмах рассадки или планирования, чтобы гарантировать, что определенные люди не находятся рядом друг с другом. Алгоритмы сопоставления могут использовать перетасовку, чтобы гарантировать, что пары похожих людей не объединятся в команду или группу. Перетасовка ДНК берет сегменты ДНК и перемешивает их, создавая новые сегменты. Из-за этого должны быть эффективные и простые алгоритмы для реализации процедуры перетасовки.

Возможные решения

Реализовать наивный алгоритм легко, но более интересное и быстрое решение может занять больше времени. Я пытался решить задачу Leetcode, реализующую перетасовку на массиве с несколькими возможными реализациями.

Учитывая массив целых чисел nums, разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятными в результате перетасовки.

Реализуйте класс Solution:

Solution(int[] nums) Инициализирует объект целочисленным массивом nums.

int[] reset() Сбрасывает массив до исходной конфигурации и возвращает его.

int[] shuffle() Возвращает случайное перетасовывание массива.

Решение 1. Перетасовка индексов (линейное время)

Наивное решение, которое я называю перетасовкой индексов, состоит в том, чтобы просмотреть каждый элемент один за другим и выбрать случайный индекс для обмена. Хотя это рандомизирует массив и является наиболее очевидным решением, оно также является наиболее неэффективным и ненужным. Нет необходимости перемешивать каждый элемент, и статистическая достоверность перетасовки все еще может быть получена с помощью алгоритмов, которым не нужно посещать каждый элемент. Решение будет иметь временную сложность O(N), что делает его более сложным по времени. Давайте попробуем реализовать наивное решение на Python.

from random import randrange

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums[:]

    def reset(self) -> List[int]:
        self.nums = self.original[:]
        return self.nums

    def shuffle(self) -> List[int]:
        N = len(self.nums)
        for i in range(N):
            idx = randrange(0, N)
            tmp = self.nums[i]
            self.nums[i] = self.nums[idx]
            self.nums[idx] = tmp
        return self.nums

Это имело время выполнения 173 мс и находилось в 55,8% процентиля решений, опережая более половины решений Python.

Решение 2. Перетасовка Фишера-Йейтса (линейное время)

В этом алгоритме мы кладем все числа в мешочек и рисуем каждое по одному. Мы можем использовать набор или другой список как своего рода мешок и просто удалять каждый элемент один за другим. Так играют в лотереи и другие азартные игры. Мы можем реализовать это как перетасовку на месте, сохраняя перетасованные элементы в конце массива, а неперетасованные — в начале. «Такой же алгоритм использует random.shuffle в стандартной библиотеке Python.

from random import randrange

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums[:]

    def reset(self) -> List[int]:
        self.nums = self.original[:]
        return self.nums

    def shuffle(self) -> List[int]:
        N = len(self.nums)
        for i in range(N-1):
            idx = randrange(i, N)
            tmp = self.nums[i]
            self.nums[i] = self.nums[idx]
            self.nums[idx] = tmp
        return self.nums

Это выполняется за 166 мс и находится в процентиле решений 73,78%, поэтому это немного лучше, чем перетасовка индексов. Обратите внимание, что это очень похоже на перетасовку индексов, за исключением того, что наш случайный индекс выбирается из диапазона от i до N, а не от 0 до N. Наихудшим случаем этого алгоритма будет O(N). это эквивалентно перетасовке индексов.

Решение 3. Частичное перемешивание (постоянное время)

Что, если бы нам не нужно было посещать каждый индекс, чтобы по большей части перетасовать весь список? Что, если мы перемешаем только определенную часть списка? На самом деле, что, если мы перемешаем только постоянное количество элементов? Это основа частичного перемешивания; он посещает только определенные элементы и оставляет нетронутыми другие.

Мы выбираем константу K, которая представляет количество раз, когда мы выбираем случайный индекс для перетасовки. На каждой итерации из всех индексов случайным образом выбираются два индекса, и элементы меняются местами, как и в предыдущих перетасовках. Однако мы делаем это только определенное количество раз, обеспечивая постоянное время работы; таким образом, сложность в наихудшем случае будет O (1).

Этот алгоритм не обязательно будет идеальным перетасовкой; однако в среднем он должен давать относительно рандомизированный перетасованный список с достаточно высоким значением K. Количество перетасовок может быть выражено как отношение K к N.

Если K достаточно велико, то для хорошего генератора псевдослучайных чисел перетасовка будет близкой к идеальной. Каждый элемент должен быть перетасован или, по крайней мере, большинство из них. Если K = N, перетасовка становится индексной или перетасовкой Фишера-Йейтса со случайными индексами.

from random import randrange

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums[:]
        self.K = 100

    def reset(self) -> List[int]:
        self.nums = self.original[:]
        return self.nums

    def shuffle(self) -> List[int]:
        N = len(self.nums)
        for i in range(self.K):
            while (i := randrange(0, N)) == (j := randrange(0, N)):
                continue # pick indices until we get two different indices
            tmp = self.nums[i]
            self.nums[i] = self.nums[j]
            self.nums[j] = tmp
        return self.nums

Хотя теоретически этот алгоритм работает, у меня возникли трудности с прохождением некоторых тестовых случаев Leetcode, поскольку вероятности для каждой перестановки в случайном порядке не равны, и многие из них гораздо более вероятны, чем другие. Это перетасовка хорошо работает для небольших списков чисел, но для больших списков это не сработает, так как не все элементы будут перетасованы правильно.

Лучший алгоритм?

На данный момент алгоритм Фишера-Йейтса превосходит другие с большим отрывом, алгоритм с постоянным временем не обеспечивает полной случайности, а наивный алгоритм занимает немного больше времени. Алгоритм Фишера-Йейтса асимптотически оптимален, то есть это лучший алгоритм как для временной, так и для пространственной сложности. В то время как алгоритмы постоянного времени для перетасовки могут работать с небольшими списками, для больших списков это единственный способ точно перетасовать список.