Как перемешать массив, не давая элементам сместиться больше чем на заданное значение с их оригинальной позиции?

Как перемешать массив, не давая элементам сместиться больше чем на заданное значение (N) с их оригинальной позиции? Скажем, для N=1: [1, 2, 3, 4, 5] может быть перемешан в [1, 3, 2, 4, 5] или [2, 1, 3, 5, 4], но не в [5, 2, 1, 3, 4]
Нет ли случайно какого-нибудь алгоритма? Увы, нагуглить ничего не удаётся, а моя реализация не очень-то равномерная.
Тем не менее, приведу на всякий случай:
///

/// Возвращает перемешанный заданным образом массив размером size с элементами от 0 /// до size−1. В дальнейшем этот массив будет использован как список новых позиций. ///

/// Число элементов /// Максимальное смещение /// Перемешанный список индексов private int[] Shuffle(int size, int limit) { var buffer = new int[size]; for (var i = 0; i < buffer.Length; i++) { buffer[i] = i; }
for (var i = buffer.Length - 1; i >= 0; i--) { // Узнаём оригинальную позицию элемента var t = buffer[i];
// Границы для поиска относительно оригинальной позиции var a = Math.Max(t - limit, 0); var b = Math.Min(t + limit, buffer.Length - 1);
// Выбираем кандидата на обмен var n = _randomInstance.Next(a, b + 1);
// Самого на себя не меняем if (n != i) { // Возможные границы обмена для найденного элемента var ai = Math.Max(i - limit, 0); var bi = Math.Min(i + limit, buffer.Length - 1);
// Узнаём оригинальную позицию элемента var v = buffer[n];
// Если оригинальная позиция найденного вписывается в границы // вокруг i, можно заменить if (v >= ai && v <= bi) { buffer[i] = buffer[n]; buffer[n] = t; } } }
return buffer; }

Ответ

Интересно, правильно ли я думаю. Т.к. сложность нас не сильно интересует, то переформулируем задачу, сведя её к максимальному паросочетанию. Ребёр у нас будет порядка N*2*Delta. Сложность как обычно - O(N^3).
В сочетании со случайным перемешиванием через обычный random_shuffle это даёт все возможные комбинации и более-менее равномерно (для малых N/Delta проверял).
Выкладываю код полностью, с простейшей проверкой на равномерность генерации.
Интересны мнения по поводу корректности данной наркомании :)
map counter;
void operator delete (void *A){}; void operator delete[] (void *A){};
int n, k; vector < vector > g; vector mt; vector used;
bool try_kuhn (int v) { if (used[v]) return false; used[v] = true; for (size_t i=0; i int main() { int X = 6; int MAX_DELTA = 2; srand(time(0));
for (int Z=0;Z<5000;Z++){ vector first; vector firstB;
for (int i=0;i int n = X; int k = X; g.resize(X); for (int i=0;i for (int i=0;i mt.assign (k, -1); vector used1 (n); for (int i=0; i for (int i=0; i /*for (int i:first) cout << i<<" "; cout << endl;*/ int hashC = 0; int pow = 1; for (int i=0;i for (int i=0; i < X;i++) if (first[i] - i < -MAX_DELTA || first[i] - i > MAX_DELTA){ for (int z:first) cout << z<<" "; cout <<"FAIL!"<Код паросочетания просто скопировал отсюда