Ищем ограниченный алгоритм перетасовки

Вы правы, это сложно! Во-первых, нам нужно установить еще несколько правил, чтобы гарантировать, что мы не создадим искусственно неслучайные результаты:

• Элементы можно оставить в той позиции, с которой они начинались. Это необходимая часть любой честной перетасовки, а также гарантирует, что наша перетасовка будет работать при N=0.
• Когда N больше, чем расстояние элемента от начала или конца массива, его можно переместить на другую сторону. Мы могли бы настроить алгоритм, чтобы запретить это, но это нарушило бы требование «равномерности» — элементы, расположенные ближе к краям, с большей вероятностью останутся на месте, чем элементы, расположенные ближе к середине.

Теперь мы действительно можем решить проблему.

1. Создайте массив случайных значений в диапазоне i + [-N, N], где i — текущий индекс в массиве. Нормализация значений за пределами массива (например, -1 должно стать length-1, а length должно стать 0).
2. Look for pairs of duplicate values (collisions) in the array, and recompute them. You have a few options:
   • Recompute both values until they don't collide with each other, they could both still collide with other values.
   • Перевычисляйте только одно, пока оно не перестанет сталкиваться с другим, первое значение все еще может сталкиваться, но второе должно теперь быть уникальным, что может означать меньше вызовов ГСЧ.
   • Определите набор доступных индексов для каждого столкновения (например, в [3, 1, 1, 0] доступен индекс 2), выберите случайное значение из этого набора и установите одно из значений массива для выбранного результата. Это позволяет избежать необходимости зацикливаться до тех пор, пока коллизия не будет разрешена, но более сложно кодировать и есть риск столкнуться с ситуацией, когда множество пусто.
3. Как бы вы ни обращались к отдельным коллизиям, повторяйте процесс, пока каждое значение в массиве не станет уникальным.
4. Теперь переместите каждый элемент исходного массива в индекс, указанный в сгенерированном нами массиве.

Я не уверен, как лучше всего реализовать № 2, я бы посоветовал вам сравнить его. Если вы не хотите тратить время на тестирование, я бы выбрал первый вариант. Остальные — это оптимизации, которые могут работать быстрее, но на самом деле могут оказаться медленнее.

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

Я придумал одно возможное решение, хотя насколько оно «наивно», я не уверен. Особенно по краям, особенно дальний край.

1. создать массив флагов (логический) длиной N (представляющий элементы, которые были заменены местами)

2. Для проверки каждого индекса, если он уже был заменен (согласно первому элементу в массиве флагов), если это так, перейдите к следующему (см. ниже)

3. поверните массив флагов, удалив первый элемент (представляющий этот элемент), и добавьте в конец новый элемент «не заменен». ВНИМАНИЕ: это можно сделать с помощью поиска массива модулей, чтобы избежать фактического перемещения содержимого массива, особенно для больших N

4. Петля...

   • pick a number from 0 to N (or less than N, if N plus current index is larger that array being shuffled.
   • Если 0, элемент меняет местами сам с собой, переходит к следующему.
   • В противном случае, если этот элемент помечен как замененный, повторите цикл и повторите попытку. Обратите внимание, что в массиве флагов всегда есть 2 элемента, которые можно выбрать, сам и последний элемент (если он не находится близко к концу перетасовываемого массива).

5. Поменять местами текущий элемент с выбранным непереставленным элементом, пометить выбранный элемент как замененный в массиве флагов. Перейти к следующему элементу