Быстрая случайно-парная перестановка
Мне нужно сгенерировать случайную парную перестановку для упорядоченного массива целых чисел (индексов). Например, для N=10 входной массив выглядит так:
[0 1 2 3 4 5 6 7 8 9]
Допустимой случайной парной перестановкой будет:
[7 8 6 5 9 3 2 0 1 4]
Обратите внимание, что индексы являются случайными парами, то есть: если элемент 0 (входной массив) связан с 7 (0-я позиция в переставленном массиве), то элемент 7 (входной массив) связан с 0 (7-я позиция в переставленном массиве). массив) и др. Ни один элемент входного массива не может быть связан сам с собой, т. е. это недопустимая перестановка:
[7 1 6 5 9 3 2 0 8 4]
Потому что элементы 1 и 8 находятся в своих «индексных» позициях. Это связано с перестановкой расстройства, тема уже несколько раз освещалась в SO:
- Генерация случайного беспорядка списка
- Перемешайте список, чтобы ни один элемент не оставался на одном месте
- перетасовка питона, чтобы позиция никогда не повторялась
Я не уверен, как (если) я мог бы использовать любой из перечисленных там ответов в свою пользу. Код ниже делает то, что мне нужно, но он становится очень медленным для больших значений N. Мне нужно выполнить эту операцию тысячи раз для N ~ 1500, то есть этот метод бесполезен.
Я уверен, что должен быть более умный способ сделать это.
N = 10
idxs = np.arange(N)
# Generate a shuffled array
input_idxs = idxs.copy()
np.random.shuffle(input_idxs)
# Empty array to store the final randomly paired indexes
shuffled_idxs = np.zeros(N, dtype=int)
used_idxs = []
for i in idxs:
if i not in used_idxs:
for j in input_idxs:
if j not in used_idxs:
if j != i:
shuffled_idxs[i] = j
shuffled_idxs[j] = i
used_idxs.append(i)
used_idxs.append(j)
break
Я думаю, вы могли бы думать об этом таким образом. Суть в том, что случайные замены должны выполняться парами.
Ответы 1
Спаривание свопов будет означать, что N всегда четное число. Если это так, то вы можете взять выборку из половины индексов и соединить их с перетасованным списком оставшихся индексов:
import random
def randomPairs(N):
result = [None] * N
A = random.sample(range(N),N//2)
B = random.sample(list(set(range(N))-set(A)),N//2)
for a,b in zip(A,B):
result[a] = b
result[b] = a
return result
for _ in range(10):
print(randomPairs(6))
[4, 3, 5, 1, 0, 2]
[5, 4, 3, 2, 1, 0]
[5, 3, 4, 1, 2, 0]
[2, 3, 0, 1, 5, 4]
[3, 2, 1, 0, 5, 4]
[2, 3, 0, 1, 5, 4]
[4, 2, 1, 5, 0, 3]
[3, 4, 5, 0, 1, 2]
[2, 3, 0, 1, 5, 4]
[1, 0, 3, 2, 5, 4]
Производительность
# 1000 shuffles of 1500 elements in pairs
def test1():
for _ in range(1000):
randomPairs(1500)
from timeit import timeit
count = 1
t = timeit(test1,number=count)
print(t) # 1.12 seconds
[EDIT] немного более быстрым решением было бы перетасовать все индексы и соединить каждую другую позицию со следующей в перетасованном списке:
import random
def randomPairs(N):
result = [None] * N
A = random.sample(range(N),N)
for a,b in zip(A[::2],A[1::2]):
result[a] = b
result[b] = a
return result
Просто чтобы убедиться, что я правильно понимаю: ваша цель - случайным образом поменять местами элементы в вашем списке с требованиями, чтобы каждое число менялось местами только один раз, верно?