Вопрос-Ответ

How can I get "permutations with repetitions/replacement" from a list (Cartesian product of a list with itself)?

Как я могу получить "перестановки с повторениями / заменой" из списка (декартово произведение списка на самого себя)?

Предположим, у меня есть список die_faces = [1, 2, 3, 4, 5, 6]. Я хочу сгенерировать все 36 возможных результатов для броска двух кубиков: (1, 1), (1, 2), (2, 1) и т.д. Если я попытаюсь использовать permutations из itertools стандартной библиотеки:

>>> import itertools
>>> die_faces = [1, 2, 3, 4, 5, 6]
>>> list(itertools.permutations(die_faces, 2))
[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5)]

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

Переведено автоматически
Ответ 1

Вы ищете декартово произведение.


В математике декартово произведение (или набор продуктов) является прямым произведением двух наборов.


В вашем случае это было бы {1, 2, 3, 4, 5, 6} x {1, 2, 3, 4, 5, 6}. itertools могу вам здесь помочь:

import itertools
x = [1, 2, 3, 4, 5, 6]
[p for p in itertools.product(x, repeat=2)]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3),
(2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6),
(4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3),
(5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

Чтобы получить случайный бросок кости (совершенно неэффективным способом):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)
Ответ 2

Вы не ищете перестановки - вам нужно декартово произведение. Для этого используйте product из itertools:

from itertools import product
for roll in product([1, 2, 3, 4, 5, 6], repeat = 2):
print(roll)
Ответ 3

В python 2.7 и 3.1 есть itertools.combinations_with_replacement функция:

>>> list(itertools.combinations_with_replacement([1, 2, 3, 4, 5, 6], 2))
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4),
(2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6),
(5, 5), (5, 6), (6, 6)]
Ответ 4

В этом случае понимание списка особенно не требуется.

Дано

import itertools as it


seq = range(1, 7)
r = 2

Код

list(it.product(seq, repeat=r))

Подробные сведения

Неочевидно, что декартово произведение может генерировать подмножества перестановок. Однако из этого следует, что:


  • с заменой: произвести все перестановки nr через product

  • без замены: фильтровать из последнего

Перестановки с заменой, nr

[x for x in it.product(seq, repeat=r)]

Перестановок без замены, n!

[x for x in it.product(seq, repeat=r) if len(set(x)) == r]
# Equivalent
list(it.permutations(seq, r))

Следовательно, все комбинаторные функции могут быть реализованы из product:


  • combinations_with_replacement реализовано из product

  • combinations реализовано из permutations, которое может быть реализовано с помощью product (см. Выше)

python