Создание перестановок с повторениями

Я знаю об itertools, но, похоже, он может генерировать только перестановки без повторений.

Например, я хотел бы сгенерировать все возможные броски кубиков для 2 кубиков. Итак, мне нужны все перестановки размера 2 из [1, 2, 3, 4, 5, 6], включая повторения: (1, 1), (1, 2), (2, 1) ... и т. Д.

Если возможно, я не хочу реализовывать это с нуля


person Bwmat    schedule 23.06.2010    source источник


Ответы (6)


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

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

В вашем случае это будет {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)
person miku    schedule 23.06.2010
comment
Это крайне неэффективный способ получить 2 броска кубика ... Два вызова random.randint были бы проще и эффективнее. - person Eric O Lebigot; 23.06.2010
comment
Случайные броски кубиков будут намного быстрее, если вы не создадите все возможные пары: [random.randint (1,6) for i in xrange (2)] - person liori; 23.06.2010
comment
На самом деле я не пытался генерировать случайные броски, просто чтобы перечислить все возможные броски. - person Bwmat; 23.06.2010

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

from itertools import product
for roll in product([1, 2, 3, 4, 5, 6], repeat = 2):
    print(roll)
person Mark Byers    schedule 23.06.2010

В 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)]
person SilentGhost    schedule 23.06.2010
comment
Это решение проигрывает комбинациям (2, 1), (3, 2), (3, 1) и подобным ... В общем, оно не учитывает все комбинации, в которых второй результат ниже, чем первый. - person holroy; 16.11.2015

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

Дано

import itertools as it


seq = range(1, 7)
r = 2

Код

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

Подробности

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

  • с заменой: произвести все перестановки n r через product
  • без замены: фильтр из последнего

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

[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 ( см. выше)
person pylang    schedule 05.10.2019

Думаю, я нашел решение, используя только lambdas, map и reduce.

product_function = lambda n: reduce(lambda x, y: x+y, map(lambda i: list(map(lambda j: (i, j), np.arange(n))), np.arange(n)), [])

По сути, я сопоставляю первую лямбда-функцию, которая задает строку, выполняет итерацию столбцов.

list(map(lambda j: (i, j), np.arange(n)))

затем это используется как результат новой лямбда-функции

lambda i:list(map(lambda j: (i, j), np.arange(n)))

который отображается во всех возможных строках

map(lambda i: list(map(lambda j: (i, j), np.arange(n))), np.arange(m))

а затем сводим все получившиеся списки в один.

даже лучше

Также можно использовать два разных числа.

prod= lambda n, m: reduce(lambda x, y: x+y, map(lambda i: list(map(lambda j: (i, j), np.arange(m))), np.arange(n)), [])
person Euler_Salter    schedule 29.05.2020

Во-первых, вам нужно сначала превратить генератор, возвращаемый itertools.permutations (list), в список. Затем, во-вторых, вы можете использовать set () для удаления дубликатов, как показано ниже:

def permutate(a_list):
    import itertools
    return set(list(itertools.permutations(a_list)))
person Eric_HL_DoCode    schedule 10.02.2016
comment
Это не включает дубликаты. - person Björn Lindqvist; 24.03.2017
comment
OP явно хочет дубликатов - person Levi Lesches; 05.03.2018