Generowanie permutacji z powtórzeniami

87

Wiem o itertools, ale wygląda na to, że może generować tylko permutacje bez powtórzeń.

Na przykład chciałbym wygenerować wszystkie możliwe rzuty kośćmi dla 2 kości. Więc potrzebuję wszystkich permutacji rozmiaru 2 z [1, 2, 3, 4, 5, 6], w tym powtórzeń: (1, 1), (1, 2), (2, 1) ... itd.

Jeśli to możliwe, nie chcę wdrażać tego od zera

Bwmat
źródło

Odpowiedzi:

150

Szukasz produktu kartezjańskiego .

W matematyce iloczyn kartezjański (lub zbiór produktów) jest bezpośrednim iloczynem dwóch zbiorów.

W twoim przypadku byłoby to {1, 2, 3, 4, 5, 6}x {1, 2, 3, 4, 5, 6}. itertoolsmoże Ci w tym pomóc:

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)]

Aby uzyskać losowy rzut kostką (w całkowicie nieefektywny sposób ):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)
miku
źródło
8
Jest to niezwykle nieefektywny sposób na wykonanie 2 rzutów kośćmi… Dwa wezwania random.randintbyłyby prostsze i wydajniejsze.
Eric O Lebigot
Losowe rzuty kośćmi będą znacznie szybsze, jeśli nie wygenerujesz wszystkich możliwych par: [random.randint (1,6) for i in xrange (2)]
liori
13
Właściwie nie próbowałem generować losowych rzutów, tylko po to, aby wymienić wszystkie możliwe rzuty.
Bwmat
29

Nie szukasz permutacji - chcesz produktu kartezjańskiego . W tym celu użyj produktu itertools:

from itertools import product
for roll in product([1, 2, 3, 4, 5, 6], repeat = 2):
    print(roll)
Mark Byers
źródło
7

W Pythonie 2.7 i 3.1 jest itertools.combinations_with_replacementfunkcja:

>>> 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)]
SilentGhost
źródło
13
Rozwiązanie to traci się na kombinacji (2, 1), (3, 2), (3, 1)i podobne ... W ogóle to pomija wszystkie kombinacje, gdzie druga rolka jest niższy niż pierwszy.
holroy
1

W takim przypadku rozumienie listy nie jest szczególnie potrzebne.

Dany

import itertools as it


seq = range(1, 7)
r = 2

Kod

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

Detale

Oczywiście iloczyn kartezjański może generować podzbiory permutacji. Wynika z tego jednak, że:

  • z zamianą: produkuje wszystkie permutacje n r przezproduct
  • bez wymiany: filtr z tego ostatniego

Permutacje z zamianą, n r

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

Permutacje bez zamiany, n!

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

W konsekwencji wszystkie funkcje kombinatoryczne mogą być implementowane z product:

pylang
źródło
-1

Myślę, że znalazłem rozwiązanie używając tylko lambdas, mapi 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)), [])

Zasadniczo mapuję pierwszą funkcję lambda, która podając wiersz, iteruje kolumny

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

to jest używane jako dane wyjściowe nowej funkcji lambda

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

który jest mapowany na wszystkie możliwe wiersze

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

a następnie redukujemy wszystkie otrzymane listy do jednej.

nawet lepiej

Można również użyć dwóch różnych liczb.

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)), [])
Euler_Salter
źródło
-2

Najpierw będziesz chciał zamienić generator zwracany przez itertools.permutations (list) na listę. Następnie możesz użyć set (), aby usunąć duplikaty. Coś jak poniżej:

def permutate(a_list):
    import itertools
    return set(list(itertools.permutations(a_list)))
Eric_HL_DoCode
źródło
1
Nie obejmuje to duplikatów.
Björn Lindqvist
1
OP wyraźnie chce duplikatów
Levi Lesches