Permutationen mit Wiederholungen erzeugen

87

Ich kenne itertools, aber es scheint, dass es nur Permutationen ohne Wiederholungen erzeugen kann.

Zum Beispiel möchte ich alle möglichen Würfelwürfe für 2 Würfel generieren. Ich brauche also alle Permutationen der Größe 2 von [1, 2, 3, 4, 5, 6] einschließlich Wiederholungen: (1, 1), (1, 2), (2, 1) ... usw.

Wenn möglich, möchte ich dies nicht von Grund auf neu implementieren

Bwmat
quelle

Antworten:

149

Sie suchen das kartesische Produkt .

In der Mathematik ist ein kartesisches Produkt (oder eine Produktmenge) das direkte Produkt zweier Mengen.

In Ihrem Fall wäre dies {1, 2, 3, 4, 5, 6}x {1, 2, 3, 4, 5, 6}. itertoolskann dir da helfen:

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

So erhalten Sie einen zufälligen Würfelwurf (auf völlig ineffiziente Weise ):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)
miku
quelle
8
Dies ist eine äußerst ineffiziente Methode, um zwei Würfelwürfe zu erhalten. Zwei Aufrufe random.randintwären einfacher und effizienter.
Eric O Lebigot
Zufällige Würfelwürfe sind viel schneller, wenn Sie nicht alle möglichen Paare generieren: [random.randint (1,6) für i in xrange (2)]
liori
13
Ich habe eigentlich nicht versucht, zufällige Rollen zu generieren, nur um alle möglichen Rollen aufzulisten.
Bwmat
29

Sie suchen keine Permutationen - Sie möchten das kartesische Produkt . Verwenden Sie dazu das Produkt von itertools:

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

In Python 2.7 und 3.1 gibt es eine itertools.combinations_with_replacementFunktion:

>>> 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
quelle
13
Diese Lösung löst auf den Kombinationen aus (2, 1), (3, 2), (3, 1)und ähnlich ... In der Regel lässt sie alle Kombinationen, wo die zweite Rolle niedriger als die erste ist.
Holroy
1

In diesem Fall ist ein Listenverständnis nicht besonders erforderlich.

Gegeben

import itertools as it


seq = range(1, 7)
r = 2

Code

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

Einzelheiten

Es ist offensichtlich, dass kartesische Produkte Teilmengen von Permutationen erzeugen können. Daraus folgt jedoch:

  • mit ersatz: alle permutationen n r via erzeugenproduct
  • ersatzlos: Filter von letzterem

Permutationen mit Ersatz, n r

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

Permutationen ohne Ersatz, n!

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

Folglich könnten alle kombinatorischen Funktionen implementiert werden aus product:

Pylang
quelle
-1

Ich glaube, ich habe eine Lösung nur lambdasmit mapund gefunden 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)), [])

Im Wesentlichen ordne ich eine erste Lambda-Funktion zu, die bei einer gegebenen Zeile die Spalten iteriert

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

dann wird dies als Ausgabe einer neuen Lambda-Funktion verwendet

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

welches über alle möglichen Zeilen abgebildet wird

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

und dann reduzieren wir alle resultierenden Listen zu einer.

noch besser

Kann auch zwei verschiedene Nummern verwenden.

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
quelle
-2

Zunächst möchten Sie den von itertools.permutations (Liste) zurückgegebenen Generator zuerst in eine Liste umwandeln. Zweitens können Sie set () verwenden, um Duplikate zu entfernen.

def permutate(a_list):
    import itertools
    return set(list(itertools.permutations(a_list)))
Eric_HL_DoCode
quelle
1
Das schließt keine Duplikate ein.
Björn Lindqvist
1
OP will ausdrücklich Duplikate
Levi Lesches