Быстрая случайно-парная перестановка

Мне нужно сгенерировать случайную парную перестановку для упорядоченного массива целых чисел (индексов). Например, для 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

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

Ofi91 18.12.2020 19:28

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

Gabriel 18.12.2020 19:33
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
2
133
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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

Другие вопросы по теме