Случайные выборы из генератора перестановок?

Question

Как случайным образом выбрать все результаты, один за другим (без повторов) из itertools.permutations(k)? Или это: как построить генератор случайных перестановок? Что-то вроде shuffle(permutations(k)). Я использую Python 2.6.

Да, shuffle(r) можно использовать, если r = list(permutations(k)), но такой список будет занимать слишком много времени и памяти, когда len(k) поднимется выше 10.

Спасибо.

Answer 1

это дает n-ю перестановку списка

def perm_given_index(alist, apermindex):
    alist = alist[:]
    for i in range(len(alist)-1):
        apermindex, j = divmod(apermindex, len(alist)-i)
        alist[i], alist[i+j] = alist[i+j], alist[i]
    return alist

, где apermindex находится между 0 и factorial(len(alist))

Answer 2

Невозможно выполнить то, о чем вы просили, не написав собственную версию permutations.

. Учтите следующее:

• У нас есть объект-генератор, содержащий результатpermutations.
• Мы написали нашу собственную функцию, чтобы сообщить нам длину генератора.
• Затем мы произвольно выбираем записи между началом списка и концом.

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

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

Answer 3

Я не знаю, как Python реализует свой алгоритм перемешивания, но следующие шкалы в линейном времени, поэтому я не понимаю, почему длина 10 такая большая проблема (если я не понимаю ваш вопрос?):

• начать со списка элементов;
• по очереди пройти по каждому индексу в списке, поменяв его местами по этому индексу для элемента со случайным индексом (включая сам элемент)в оставшейся части списка.

Для другой перестановки просто запустите тот же алгоритм еще раз.

Answer 4

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

Реализуйте его в python, используя yield для эффективной последовательной генерации.Тем не менее, если вы хотите случайный выбор без повторений, вам придется сгенерировать список или использовать алгоритм, опубликованный Dan и запомнить номера, которые вы уже выбрали.

Answer 5

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

import numpy as np
from math import factorial

for i in range(factorial(len(biglist))):
    permut = np.random.permutation(biglist).tolist()
    ...