Wie man Permutationen generiert, ohne wiederholende Ergebnisse, aber mit einer festen Anzahl von Zeichen zu erzeugen Python

Question

Ich versuche eine Möglichkeit zu finden, alle möglichen Permutationen eines Strings zu erzeugen, der ein paar sich wiederholende Zeichen hat, aber wiederholte Tupel nicht erzeugt.

Momentan verwende ich itertools.permutations(). Es funktioniert, aber ich muss die Wiederholung entfernen und ich kann nichtset() verwenden, um die Wiederholung zu entfernen.

Welche Art von Ergebnissen erwarte ich? Nun, zum Beispiel möchte ich alle Kombinationen für DDRR bekommen, die Sache mit itertools.permutations() ist, dass ich DDRR etwa vier Mal bekommen würde, vorausgesetzt, dass itertools sieht die s, als ob sie anders waren, gleich mit R s.

Mit list(itertools.permutations('DDRR')) ich:

[('D', 'D', 'R', 'R'), ('D', 'D', 'R', 'R'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('D', 'D', 'R', 'R'), ('D', 'D', 'R', 'R'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'R', 'D', 'D'), ('R', 'R', 'D', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'R', 'D', 'D'), ('R', 'R', 'D', 'D')] 

Das ideale Ergebnis, das ich will, ist:

[('D', 'R', 'R', 'D'), ('R', 'D', 'R', 'D'), ('R', 'R', 'D', 'D'), ('D', 'R', 'D', 'R'), ('D', 'D', 'R', 'R'), ('R', 'D', 'D', 'R')] 

Answer 1

Dies würde eine Standardmethode sein Permutationen eines Satzes mit doppelten Elemente zu erstellen: zählen die Anzahl der Vorkommen jedes Elements (z. B. mit einem assoziativen Array oder einem Wörterbuch), durchlaufen Sie die Elemente im Wörterbuch und fügen Sie jedes Element an die Permutation an, und rekursieren Sie mit dem Rest des Wörterbuchs. Es wird jedoch nie für sehr lange Eingabe-Arrays schnell sein; aber dann wird wahrscheinlich nichts.

(Code-Beispiel in JavaScript, ich Python nicht sprechen;. Übersetzen sollte leicht genug sein)

function permute(set) { 
 
    var alphabet = {}; 
 
    for (var s in set) { 
 
     if (!alphabet[set[s]]) alphabet[set[s]] = 1; 
 
     else ++alphabet[set[s]]; 
 
    }        // alphabet = {'a':5, 'b':2, 'r':2, 'c':1, 'd':1} 
 
    perm("", set.length); 
 

 
    function perm(part, level) { 
 
     for (var a in alphabet) { // every letter in alphabet 
 
      if (alphabet[a]) {  // one or more of this letter available 
 
       --alphabet[a];  // decrement letter count 
 
       if (level > 1) perm(part + a, level - 1); // recurse with rest 
 
       else document.write(part + a + "<br>"); // deepest recursion level 
 
       ++alphabet[a];  // restore letter count 
 
      } 
 
     } 
 
    } 
 
} 
 
permute(['a','b','r','a','c','a','d','a','b','r','a']); // 83,160 unique permutations 
 
                 // instead of 39,916,800 non- 
 
                 // unique ones plus filtering

Answer 2

soll Im Allgemeinen wird jede Permutation Algorithmus n!/(n-r)! Ergebnisse erzeugen, aber Sie können entscheiden, einen Algorithmus zu implementieren, der nach Wiederholung sucht, die Spaß machen sollte.

Mal sehen, ob das hilft.

def __permutate(self, objectToPermute): 
    in_list = [] 

    for i in range(self.__cur, len(objectToPermute)): 
     in_list.append(self.__swap(self.__cur, i, objectToPermute)) 

    ''' At initial call, self.__cur = 0 
     and self.__permSize would be the r in the permutation formula ''' 
    if self.__cur < self.__permSize - 1: 
     self.__cur += 1 

     for obj in in_list: 
      self.__permutate(obj) 

     self.__cur -= 1 


    if self.__cur == self.__permSize -1: 
     for obj in in_list: 
      #this does the job 
      if self.norepeat and obj in self.__perm_obj: 
       continue 
      self.__perm_obj.append(obj[:self.__permSize]) 

Sie haben bemerkt, muss ich diese aus einer Klasse zog ich vor langer Zeit geschrieben hatte, es ist ein Permutation Algorithmus Ich mag den Melon Algorithmus nennen (nicht dagegen, dass).

Was dieser Teil des Codes tut, ist einfach rekursiv ein Objekt zu vertauschen, eine Swap-Funktion wurde verwendet, wie es in der Klasse vorhanden war, aber Sie können dies einfach codieren ... Jetzt zum Hauptpunkt, Um Wiederholung zu vermeiden Sie müssen sicherstellen, dass das Attribut self.norepeat = True und jedes wiederholte Objekt übersprungen wird. Wenn Sie die Klasse in voller Höhe benötigt werden, werde ich froh sein, zu teilen

I'ud ein Feedback mehr brauchen, um zu wissen, ob Sie bekommen, was ich sage

Answer 3

Wenn die Zeichenfolge ein enthalten Viele wiederholte Zeichen, dann können Sie einen kombinationsbasierten Algorithmus verwenden, um Ihre Permutationen zu generieren.

Grundsätzlich funktioniert dies, indem man einen Buchstaben wählt und alle Stellen findet, wo die Duplikate dieses Buchstabens gehen können. Mit jeder dieser Möglichkeiten findest du alle Orte, an denen der nächste Buchstabe steht, und so weiter.

Code:

from collections import Counter 
from itertools import combinations 

def perms_without_reps(s): 
    partitions = list(Counter(s).items()) 
    k = len(partitions) 
    def _helper(idxset, i): 
     if len(idxset) == 0: 
      yield() 
      return 
     for pos in combinations(idxset, partitions[i][1]): 
      for res in _helper(idxset - set(pos), i+1): 
       yield (pos,) + res 

    n = len(s) 
    for poses in _helper(set(range(n)), 0): 
     out = [None] * n 
     for i, pos in enumerate(poses): 
      for idx in pos: 
       out[idx] = partitions[i][0] 
     yield out 

Run es etwa so:

for p in perms_without_reps('DDRR'): 
    print p 

Zwei wichtige Hinweise:

• Dies erzeugt keine Ausgabe in einer bestimmten Art und Weise sortiert. Wenn Sie eine sortierte Ausgabe wünschen, fügen Sie eine permutations.sort() vor k = hinzu, ersetzen Sie _helper(idxset - set(pos), i+1) durch _helper(sorted(set(idxset) - set(pos)), i+1) und ersetzen Sie _helper(set(range(n)), 0) durch _helper(list(range(n)), 0). Dies wird die Funktion etwas langsamer machen.
• Diese Funktion funktioniert sehr gut, wenn Sie eine große, unsymmetrische Anzahl von Wiederholungen haben. Zum Beispiel wird jede permutationsbasierte Methode für die Eingabe 'A'*100 + 'B'*2 (AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB) nur ewig dauern, während diese Methode fast sofort mit den 5151 einzigartigen Permutationen endet.