Как генерировать перестановки массива в Python?

Question

у меня есть массив из 27 элементов, и я не хочу генерировать все перестановки массива (27!) мне нужно 5000 случайно выбранных перестановок, любой совет будет полезен ...

Answer 1

Для создания одной перестановки используйте random.shuffle и сохраните копию результата. Повторите эту операцию в цикле и каждый раз проверяйте наличие дубликатов (хотя, вероятно, их не будет). Как только у вас будет 5000 элементов в наборе результатов, остановитесь.

Чтобы указать на точку в комментарии, случайный модуль Python основан на Mersenne Twister и имеет период 2**19937-1, который значительно больше, чем 27!, поэтому он должен подходить для вашего использования.

Answer 2

import random

perm_list = []

for i in range(5000):
    temp = range(27)
    random.shuffle(temp)
    perm_list.append(temp)

print(perm_list)

10888869450418352160768000000 Я люблю большие числа! :)

И

10888869450418352160768000001 ПРЕМЬЕР !!

EDIT:

#with duplicates check as suggested in the comment

perm_list = set()
while len(perm_list)<5000:
    temp = range(27)
    random.shuffle(temp)
    perm_list.add(tuple(temp)) # `tuple` because `list`s are not hashable. right Beni?

print perm_list

ВНИМАНИЕ: Это никогда не остановится, если ГСЧ плохой!

Answer 3

itertools.permutations. Это генератор, поэтому он не создаст весь список перестановок. Вы можете пропустить случайно, пока не получите 5000.

Answer 4

# apermindex should be a number between 0 and factorial(len(alist))
def perm_given_index(alist, apermindex):
    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

Использование: perm_given_index(['a','b','c'], 3)

При этом используется код Лемера для перестановки, поскольку значения j соответствуют этому.

Answer 5

Возможно, вам понадобится функция itertools.permutations (). Должен любить этот модуль itertools!

ПРИМЕЧАНИЕ. Новое в версии 2.6

.

Answer 6

Вы можете попробовать реализовать рецепты random_permutation itertools . Для удобства я использую стороннюю библиотеку more_itertools, которая реализует для нас этот рецепт:

import more_itertools as mit

iterable = range(27)
mit.random_permutation(iterable)
# (24, 3, 18, 21, 17, 22, 14, 15, 20, 8, 4, 7, 13, 6, 25, 5, 12, 1, 9, 19, 23, 11, 16, 0, 26, 2, 10)

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

def random_permute_generator(iterable, n=10):
    """Yield a random permuation of an iterable n times."""
    for _ in range(n):
        yield mit.random_permutation(iterable)

list(random_permute_generator(range(10), n=20))
# [(2, 7, 9, 6, 5, 0, 1, 3, 4, 8),
#  (7, 3, 8, 1, 2, 6, 4, 5, 9, 0),
#  (2, 3, 1, 8, 7, 4, 9, 0, 6, 5),
#  (0, 5, 6, 8, 2, 3, 1, 9, 4, 7),
#  (0, 8, 1, 9, 4, 5, 7, 2, 3, 6),
#  (7, 2, 5, 8, 3, 4, 1, 0, 9, 6),
#  (9, 1, 4, 5, 8, 0, 6, 2, 7, 3),
#  (3, 6, 0, 2, 9, 7, 1, 4, 5, 8),
#  (8, 4, 0, 2, 7, 5, 6, 1, 9, 3),
#  (4, 9, 0, 5, 7, 1, 8, 3, 6, 2)
#  ...]

Для вашей конкретной задачи замените повторяемость и количество вызовов n соответствующими значениями, например, random_permute_generator(iterable, n=5000).

См. Также more_itertools документы для получения дополнительной информации об этом инструменте.

---

Подробнее

Для интересующихся вот настоящий рецепт.

Из рецептов itertools :

def random_permutation(iterable, r=None):
    "Random selection from itertools.permutations(iterable, r)"
    pool = tuple(iterable)
    r = len(pool) if r is None else r
    return tuple(random.sample(pool, r))