排列/變化

Question

我想要一個C＃方法，將能夠生成排列和變化。我認爲這最好在一個例子中解釋。我正在用最好的方式來完成這個任務。這就是我在腦海中想的。

我正在尋找如何解決這個問題，也許僞代碼的建議？

ABC變得

步驟1）置換沒有重複：

ABC 
ACB 
BAC 
BCA 
CAB 
CBA 

步驟2）與變動|

ABC 
    A|BC 
    AB|C 

ACB 
    A|CB 
    AC|B 

BAC 
    B|AC 
    BA|C 

BCA 
    B|CA 
    BC|A 

CAB 
    C|AB 
    CA|B 

CBA 
    C|BA 
    CB|A 

所以，你最終與最後一組

A|BC 
    AB|C 
    A|CB 
    AC|B 
    B|AC 
    BA|C 
    B|CA 
    BC|A 
    C|AB 
    CA|B 
    C|BA 
    CB|A 

更新的：只是一個快速的實現我寫了，我知道這是可怕的，任何意見歡迎。

 var perms = Permuter.Permute(new Char[] {'a', 'b', 'c'}).ToList(); 
     DisplayResult(perms); 

     foreach (var permutation in perms.ToList()) 
     { 
      var p = permutation.ToList(); 

      int splitPos = 1; 
      do 
      { 
       for (int i = 0; i < splitPos; i++) 
       { 
        Console.Write(p[i]); 
       } 

       Console.Write("|"); 

       for (int j = splitPos; j < p.Count; j++) 
       { 
        Console.Write(p[j]); 
       } 

       Console.WriteLine(""); 
       splitPos++; 
      } while (splitPos < p.Count); 
     } 

Answer 1

首先，生成排列。字典順序是最簡單的實現;見Wikipedia和Knuth的The Art of Computer Programming。下面是用Python（source）一個實現：

def permutations_of(seq): 
    yield seq 
    seqlen = len(seq) 
    while True: 
     j = seqlen - 2 
     while j >= 0 and seq[j] >= seq[j+1]: 
      j -= 1 

     if j < 0: break 

     i= seqlen - 1 
     while i > j and seq[i] < seq[j]: 
      i -= 1 

     seq[j],seq[i] = seq[i],seq[j] 
     seq[j+1:] = seq[-1:j:-1] 
     yield seq 

您也可以使用Steinhaus–Johnson–Trotter algorithm，這是一個有點快。

要生成變體，請遍歷字符串以及字符串中的每個可能位置，在該位置插入|。

Answer 2

尋找教育的目的，只是變得有趣的permtations和集和東西，試圖瞭解如何把這些東西放在一起。

有很多不同的方式來做排列，其中很多都是造就了。這裏有一個草圖讓你思考。

考慮將問題限制爲從0到31找到整數集合的一個子集的所有排列。因此，您可以選擇集合{2,3,5}並生成排列（2,3,5） ，（2,5，3），（3,2,5），（3,5,2），（5,2,3）和（5,3,2）。怎麼做？

定義一個不變的結構包含一個單一的32位整數。使結構實現IEnumerable<int>並讓它枚舉與其中設置的所有位相對應的數字。還可以製作一個「刪除」的方法，讓您返回不同的結構，刪除給定位。

現在你可以做一個遞歸算法是這樣的：

• 是集空？然後有一個排列，即空序列。

• 該集合是否爲空？然後對於集合中的每個項目：使沒有該項目的原始集合集合，遞歸地從較小集合中產生所有序列，並將該項目附加到每個這些序列。

也就是說，假設集合是{2,3,5}。你是做什麼？對於每個項目2,3,5：

Remove the item 2. That leaves 3 and 5. Permute 3, 5. How? 
    Remove item 3. That leaves 5. Permute that. 
     Remove item 5. That leaves nothing. Permute that. 
      The result is the empty sequence. 
     Append 5 to the empty sequence. That's (5). 
    Append 3. That's (5, 3). 
    Remove 5. That leaves 3. Permute that. 
     Remove 3. That leaves nothing. Permute that. 
      The result is the empty sequence. 
     Append 3 to the empty sequence. That's (3). 
    Append 5. That's (3, 5). 
Append 2 to each of those results. That's (2, 5, 3) and (2, 3, 5). 
Remove 3. That leaves 2 and 5. Permute that.... 

把它轉換成代碼將有點棘手，但相當誘惑。