修改生成排列的堆的算法

Heap's algorithm是一種系統的方式來循環通過 N元素的所有排列「一次一個交換」。對於奇數N，它特別整潔，因爲最終的排列似乎只有一個交換與第一個排列不同。修改生成排列的堆的算法

但是，對於偶數N，此繞回不會發生。例如，對於 N = 4，排列的順序是：

因此，沒有人具有環繞甚至爲N的交換算法？如果不是，那麼對於N = 4呢？

來源

2014-04-24 bobuhito

通過

檢查，一個可能的序列，其滿足約束將是：

在每一步中有應該只是兩塊交換元件。

對於較大的N，我會建議您嘗試執行Steinhaus–Johnson–Trotter algorithm，我相信這些排列會使用相鄰元素的交換來生成這些排列，並且會讓您從初始位置離開。基於rosetta code

Python代碼：

N=4 
def s_permutations(seq): 
    def s_perm(seq): 
     if not seq: 
      return [[]] 
     else: 
      new_items = [] 
      for i, item in enumerate(s_perm(seq[:-1])): 
       if i % 2: 
        new_items += [item[:i] + seq[-1:] + item[i:] 
            for i in range(len(item) + 1)] 
       else: 
        new_items += [item[:i] + seq[-1:] + item[i:] 
            for i in range(len(item), -1, -1)] 
      return new_items 

    return [(tuple(item), -1 if i % 2 else 1) 
      for i, item in enumerate(s_perm(seq))] 

for x,sgn in s_permutations(range(1,N+1)): 
    print ''.join(map(str,x))

來源

2014-04-24 19:27:27

對於一個固定的小數如N = 4，您可以預先計算您陣列的所有索引排列，並使用索引的每個排列來遍歷數據，以得出數據的所有排列，例如在僞碼

originalData[] = { 1111, 2222, 3333, 4444 } 
indexPermuations[0] = { 0, 1, 2, 3 } 
indexPermuations[1] = { 0, 1, 3, 2 } 
// Etc for all 16 permutations of 4 indices 

foreach (ip in indexPermutations) 
{ 
    for (i = 0 to 3) 
    { 
     dataPermuation[ip][i] = originalData[indexPermutation[ip][i]]; 
    } 
}

來源

2014-04-24 19:07:26

修改生成排列的堆的算法

回答

相關問題