Случайная выборка из N различных перестановок списка

Question

Предположим, у меня есть список Python произвольной длины k. Теперь предположим, что мне нужна случайная выборка из n, (где n <= k!) <strong>различных перестановок этого списка. Я испытал желание попробовать:

import random
import itertools

k = 6
n = 10

mylist = list(range(0, k))

j = random.sample(list(itertools.permutations(mylist)), n)

for i in j:
  print(i)

Но, естественно, этот код становится необычайно медленным, когда k становится слишком большим. Учитывая, что число перестановок, которые я могу искать n, будет относительно небольшим по сравнению с общим числом перестановок, вычисление всех перестановок не требуется. Тем не менее, важно, чтобы ни одна из перестановок в окончательном списке не была дубликатами.

Как бы вы достигли этого более эффективно? Помните, mylist может быть списком чего угодно, я просто использовал list(range(0, k)) для простоты.

Answer 1

Вы можете генерировать перестановки и отслеживать те, которые вы уже сгенерировали. Чтобы сделать его более универсальным, я сделал функцию генератора:

import random

k = 6
n = 10

mylist = list(range(0, k))

def perm_generator(seq):
    seen = set()
    length = len(seq)
    while True:
        perm = tuple(random.sample(seq, length))
        if perm not in seen:
            seen.add(perm)
            yield perm

rand_perms = perm_generator(mylist)

j = [next(rand_perms) for _ in range(n)]

for i in j:
    print(i)

Answer 2

Наивная реализация

Ниже наивная реализация, которую я сделал (хорошо реализованная @ Tomothy32, чистый PSL с использованием генератора):

import numpy as np

mylist = np.array(mylist)
perms = set()
for i in range(n):                          # (1) Draw N samples from permutations Universe U (#U = k!)
    while True:                             # (2) Endless loop
        perm = np.random.permutation(k)     # (3) Generate a random permutation form U
        key = tuple(perm)
        if key not in perms:                # (4) Check if permutation already has been drawn (hash table)
            perms.update(key)               # (5) Insert into set
            break                           # (6) Break the endless loop
    print(i, mylist[perm])

Используется numpy.random.permutation, который случайным образом переставляет последовательность.

Ключевая идея:

• для генерации новой случайной перестановки (индекс случайной перестановки);
• , чтобы проверить, существует ли уже перестановка, и сохранить ее (как tuple из int, поскольку она должна хешироваться) для предотвращения дублирования;
• Затем для перестановки исходного списка с использованием перестановки индекса.

Эта наивная версия напрямую не страдает от факторной сложности O(k!) из itertools.permutations функции, которая генерирует все k! перестановок перед выборкой из нее.

О сложности

Есть что-то интересное в конструкции и сложности алгоритма ...

Если мы хотим быть уверенными в том, что цикл может закончиться, мы должны применить N <= k!, но это не гарантируется. Кроме того, для оценки сложности требуется знать, сколько раз бесконечный цикл будет фактически зацикливаться до того, как будет найден новый случайный кортеж и прервет его.

Ограничение

Давайте инкапсулируем функцию, написанную @ Tomothy32:

import math
def get_perms(seq, N=10):
    rand_perms = perm_generator(mylist)
    return [next(rand_perms) for _ in range(N)]

Например, этот вызов работает для очень маленьких k<7:

get_perms(list(range(k)), math.factorial(k))

Но произойдет сбой до O(k!) сложности (время и память), когда k возрастет, потому что он сводится к случайному поиску уникального недостающего ключа, когда найдены все другие k!-1 ключи.

Всегда смотри на светлую сторону ...

С другой стороны, кажется, что метод может генерировать разумное количество перестановочных кортежей за разумное время, когда N<<<k!. Например, можно нарисовать более N=5000 кортежей длиной k, где 10 < k < 1000 менее чем за одну секунду.

Когда k и N остаются маленькими и N<<<k!, тогда алгоритм кажется сложным:

• Константа против k;
• Линейный против N.

Это как-то ценно.