如何生成排列而不產生重複的結果，但具有固定數量的字符Python

Question

我想找出一種方法來產生一個字符串有一個重複的字符，但不產生重複的元組的所有可能的排列組合。

現在我正在使用itertools.permutations()。它的作品，但我需要刪除重複和我不能使用set()刪除重複。

我期待什麼樣的結果？那麼，例如，我想要得到DDRR的所有組合，itertools.permutations()的東西是我會得到DDRR大約四次，因爲itertools看到D s就好像它們不同，與R相同。

隨着list(itertools.permutations('DDRR'))我得到：

[('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')] 

理想的結果，我想要的是：

[('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

這將創建一組具有重複元素的排列的標準方式：張數每個元素的使用（使用例如關聯數組或字典），循環遍歷字典中的元素，每次將元素附加到置換，並與字典的其餘部分遞歸。儘管如此，對於很長的輸入數組，它永遠不會很快。但那麼沒有可能會。

（代碼示例中的JavaScript，我不說話的Python;翻譯應該很容易）

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

一般每置換算法應該產生n!/(n-r)!成果，但你可以決定實現一個算法來檢查應該很有趣的重複。

讓我們看看這是否有幫助。

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

你一定注意到了，我拉了這一點，我早就寫了一類的，這是一個置換算法我喜歡叫瓜算法（不介意）。

這段代碼所做的只是簡單地遞歸排列一個對象，使用交換函數，因爲它是在類中存在的，但是您可以輕鬆地將其編碼出來......現在爲了避免重複所有你必須做的是確保屬性self.norepeat = True和每個重複的對象都會被跳過。如果你將需要全面的課，我會很高興分享

I'ud將需要一個反饋，以便知道你會得到什麼，我說

Answer 3

如果字符串包含很多重複的字符，那麼你可以使用基於組合的算法來生成你的排列。

基本上，這是通過選擇一封信，並找到所有的地方，該信件的重複可以去的地方。有了這些可能性，您可以找到下一封信的所有地方，等等。

代碼：

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 

運行它，就像這樣：

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

兩個重要注意事項：

• 這不會產生任何特定的方式進行排序輸出。如果要分類輸出，請在k =之前添加permutations.sort()，用_helper(sorted(set(idxset) - set(pos)), i+1)替換_helper(idxset - set(pos), i+1)，並用_helper(list(range(n)), 0)替換_helper(set(range(n)), 0)。這會使功能稍微慢一些。
• 如果您有大量不平衡的重複次數，此功能可以很好地工作。例如，任何基於排列的方法都將永遠佔用輸入'A'*100 + 'B'*2（AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB），而此方法將以5151個獨特排列幾乎立即完成。