Erstellen von Permutationen mit Wiederholungen in Python

Question

Ich weiß über Itertools, aber es scheint, es kann nur Permutationen ohne Wiederholungen generieren.

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

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

Answer 1

Sie suchen nach dem Cartesian Product.

In der Mathematik ist ein kartesisches Produkt (oder Produktsatz) das direkte Produkt von zwei Sätzen.

In Ihrem Fall wäre dies {1, 2, 3, 4, 5, 6} x {1, 2, 3, 4, 5, 6}. itertools können Ihnen dort 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)] 

einen zufälligen Würfelwurf zu erhalten (in einem völlig ineffizient):

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

Answer 2

Sie suchen nicht für Permutationen - Sie Cartesian Product wollen. Für diese Verwendung product von itertools:

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

Answer 3

In Python 2.7 und 3.1 gibt es eine itertools.combinations_with_replacement Funktion:

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

Answer 4

Hier ist C# -Version (auch wenn seine für Python gefragt, sollte der Algorithmus sein gleich) nur als Referenz:

Unten Methode im Grunde genommen nicht. Manchmal können die Würfel geworfen werden, um zu verschiedenen Permutationen zu kommen. Für die obige Frage sollte die Größe "2" sein.

public string[] GetAllPermutationsOfDiceOfSize_2() 
     { 
      List<string> values = new List<string>(); 
      this.GetAllPermutationsOfDice_Recursive(2, "", values); 
      return values.ToArray(); 
     } 

Nach Unit-Tests entsprechen:

private void GetAllPermutationsOfDice_Recursive(int size, string currentValue, 
      List<string> values) 
     { 
      if(currentValue.Length == size) 
      { 
       values.Add(currentValue); 
       return; 
      } 
      for(int i = 1; i<=6;i++) 
      { 
       this.GetAllPermutationsOfDice_Recursive(size, currentValue + i, values); 
      } 
     } 

Um können die Würfel zweimal, das obige Verfahren wie genannt werfen

[TestMethod] 
     public void Dice_PermutationsTests() 
     { 
      var v = this.GetAllPermutationsOfDiceOfSize_2(); 
      Assert.AreEqual(36, v.Length); 
      int l = 6; 
      List<string> values = new List<string>(); 
      for(int i = 1; i<=4; i++) 
      { 
       values.Clear(); 
       this.GetAllPermutationsOfDice_Recursive(i, "", values); 
       Assert.AreEqual(l, values.Count); 
       l *= 6; 
      } 
     } 

Answer 5

Zunächst werden Sie Ich möchte den von itertools.permutations (list) zurückgegebenen Generator zuerst in eine Liste umwandeln. Dann zweitens, können Sie Set() verwenden, um Duplikate zu entfernen So etwas wie unten:

def permutate(a_list): 
    import itertools 
    return set(list(itertools.permutations(a_list)))