Случайное потребление набора элементов, проиндексированных от 1 до N

Question

В этой задаче у меня есть набор элементов, которые проиндексированы от 1 до n . Каждый элемент на самом деле соответствует узлу графа, и я пытаюсь вычислить случайные однозначные соответствия между узлами. Для простоты я пренебрегаю деталями реальной проблемы. Мне нужно написать алгоритм быстро , чтобы случайным образом потребляли эти элементы (узлы) и выполняли эту операцию несколько раз , чтобы вычислить различные сопоставления. Цель здесь - создать рандомизированные входные данные для другого алгоритма, и каждое вычисленное сопоставление в конце этого будет еще одним входом для этого алгоритма. элементы в форме массива, генерируют случайные целые числа и используют их в качестве индексов массива для применения операций подкачки. Таким образом, каждая случайная копия может быть создана за O (n), но на практике он использует много операций копирования и обмена. Производительность очень важна, и я ищу более быстрые способы (алгоритмы и структуры данных) для достижения этой цели. Ему просто нужно удовлетворить два условия :

1. Он должен иметь возможность потреблять случайный элемент.
2. Это должен иметь возможность использовать элемент по данному индексу.

Я попытался написать как можно яснее. Если у вас есть какие-либо вопросы, не стесняйтесь спрашивать, и я буду рад уточнить. Заранее спасибо.

Примечание: Сопоставление - это операция, при которой вы соединяете вершины на графе, если между ними существует ребро.

Answer 1

Перемешать массив индексов (например, с перемешиванием Фишера-Йейтса)

ia = [3,1,4,2]

Обойти индексный массив и «использовать» элемент набора с текущим индексом

for x in ia:
   consume(Set[indexed by x])

Итак, для этого Например, вы получите заказ Set[3], Set[1], Set[4], Set[2]

Нет замены элементов, изменяется только массив целых чисел