算法列出串的獨特排列重複的字母

Question

例如，字符串「AAABBB」將有排列： 「ABAABB」， 「BBAABA」， 「ABABAB」， 等

什麼是好的算法產生排列？ （它的時間複雜度是多少？）

Answer 1

這不是完整的答案，只是一個想法。

如果你的字符串有固定數量的只有兩個字母，我會去二叉樹和良好的遞歸函數。 每個節點都是包含帶有父母名稱和後綴A或B前綴的名稱的對象，而且它的名稱中包含A和B字母的編號。

節點構造函數從父類獲取父類的名稱和A和B的編號，因此只需將A或B的數字和一個字母添加到名稱即可。

如果分別有三個以上的A（如果是A節點）或B，或者它們的總和等於起始字符串的長度，它不會構造下一個節點。

現在你可以收集2棵樹（他們的名字）的葉子，並有你需要的所有排列組合。

斯卡拉或某種功能語言（具有類似物體的特徵）對於實現這種算法來說是完美的。希望這可以幫助或者引發一些想法。

Answer 2

對於多集，您可以通過位置遞歸解決（JavaScript代碼）：

function f(multiset,counters,result){ 
 
    if (counters.every(x => x === 0)){ 
 
    console.log(result); 
 
    return; 
 
    } 
 

 
    for (var i=0; i<counters.length; i++){ 
 
    if (counters[i] > 0){ 
 
     _counters = counters.slice(); 
 
     _counters[i]--; 
 
     f(multiset,_counters,result + multiset[i]); 
 
    } 
 
    } 
 
} 
 

 
f(['A','B'],[3,3],'');

Answer 3

既然你真的想產生的排列，而不是隻計數他們，最好的您可以希望的複雜性是O（size_of_output）。

這是java中的一個很好的解決方案，它可以很快滿足綁定和運行的需求，同時消耗的空間可以忽略不計。它首先對字母進行排序以找到詞位最小的排列，然後按照詞法順序生成所有排列。

它被稱爲班智​​達算法：https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

import java.util.Arrays; 
import java.util.function.Consumer; 


public class UniquePermutations 
{ 
    static void generateUniquePermutations(String s, Consumer<String> consumer) 
    { 
     char[] array = s.toCharArray(); 
     Arrays.sort(array); 
     for (;;) 
     { 
      consumer.accept(String.valueOf(array)); 

      int changePos=array.length-2; 
      while (changePos>=0 && array[changePos]>=array[changePos+1]) 
       --changePos; 

      if (changePos<0) 
       break; //all done 

      int swapPos=changePos+1; 
      while(swapPos+1 < array.length && array[swapPos+1]>array[changePos]) 
       ++swapPos; 

      char t = array[changePos]; 
      array[changePos] = array[swapPos]; 
      array[swapPos] = t; 

      for (int i=changePos+1, j = array.length-1; i < j; ++i,--j) 
      { 
       t = array[i]; 
       array[i] = array[j]; 
       array[j] = t; 
      } 
     } 
    } 

    public static void main (String[] args) throws java.lang.Exception 
    { 
     StringBuilder line = new StringBuilder(); 
     generateUniquePermutations("banana", s->{ 
      if (line.length() > 0) 
      { 
       if (line.length() + s.length() >= 75) 
       { 
        System.out.println(line.toString()); 
        line.setLength(0); 
       } 
       else 
        line.append(" "); 
      } 
      line.append(s); 
     }); 
     System.out.println(line); 
    } 
} 

這裏是輸出：

aaabnn aaanbn aaannb aabann aabnan aabnna aanabn aananb aanban aanbna 
aannab aannba abaann abanan abanna abnaan abnana abnnaa anaabn anaanb 
anaban anabna ananab ananba anbaan anbana anbnaa annaab annaba annbaa 
baaann baanan baanna banaan banana bannaa bnaaan bnaana bnanaa bnnaaa 
naaabn naaanb naaban naabna naanab naanba nabaan nabana nabnaa nanaab 
nanaba nanbaa nbaaan nbaana nbanaa nbnaaa nnaaab nnaaba nnabaa nnbaaa