在Steinhaus-Johnson-Trotter算法中輸出交換列表的算法是什麼？

根據this page，可以輸出一個置換列表，其中每個新置換隻是與先前置換不同的單個相鄰的置換。這是詳盡的，它經歷了所有的排列。在Steinhaus-Johnson-Trotter算法中輸出交換列表的算法是什麼？

我很難從描述中理解算法。我想寫一個算法來輸出每個排列之間所需的交換。

2012-08-06 Eyal

每次交換完成後，只需將它輸出，以及... – 2012-08-06 07:08:22

由於決定需要交換的下一個元素是由排列的當前狀態定義的，因此生成下一個交換並不比生成下一個排列更簡單。

如果我不得不生成任何一個，我的目標是實現Even's speedup。那裏描述的算法應該很容易翻譯成大多數編程語言。然後，您可以輸出排列，並標記交換，如果你想要。下面的Python代碼將做到這一點：

class Elt(object): 
    def __init__(self, dir, name): 
     self.dir = dir 
     self.name = name 

n = 6 
p = [Elt(0 if i == 0 else -1, i + 1) for i in range(n)] 
while(True): 
    print(' '.join(str(i.name) for i in p)) 
    oldpos = None 
    for i in range(n): 
     if p[i].dir != 0 and (oldpos is None or p[oldpos].name < p[i].name): 
      oldpos = i 
    if oldpos is None: 
     break 
    mover = p[oldpos] 
    newpos = oldpos + mover.dir 
    p[oldpos] = p[newpos] 
    p[newpos] = mover 
    print(' '*(oldpos + newpos) + 'X') 
    if mover.dir == -1 and (newpos == 0 or p[newpos - 1].name > mover.name): 
     mover.dir = 0 
    if mover.dir == 1 and (newpos == (n - 1) or p[newpos + 1].name > mover.name): 
     mover.dir = 0 
    for i in range(newpos): 
     if p[i].name > mover.name: 
      p[i].dir = 1 
    for i in range(newpos, n): 
     if p[i].name > mover.name: 
      p[i].dir = -1

來源

2012-08-06 08:48:38 MvG

看起來不錯！我假設你測試了它？我沒有方便的Python編譯器。我希望有一種方法可以在沒有這些循環的情況下進行。是否有一種算法可以進行單次交換，可能不是相鄰的，但運行速度更快？ – Eyal 2012-08-07 08:39:04

Python被解釋，而不是編譯。你也可以[在線執行]（http://codepad.org/c0zHJs2e）。如何迭代排列非常依賴於語言;一些語言或庫爲此提供工具。例如。在C++中，您可以使用['next_permutation']（http://www.sgi.com/tech/stl/next_permutation.html）遍歷置換。如果您的授權允許，您可以看到GNU gcc libstdC++實現[實現這個]（http://gcc.gnu.org/onlinedocs/gcc-4.7.1/libstdc++/api/a01462_source.html#l03679）。 – MvG 2012-08-07 10:10:50

我最近的評論並不是對你的評論的確切回覆，我注意到：'next_permutation'按字典順序進行迭代，所以後續的排列可能會不止一個非相鄰的交換。請注意，對於SJT算法，[Wikipedia states]（http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm#Even.27s_speedup）即「更復雜的空洞版本相同的程序允許它在每種情況下在每個排列的恆定時間內執行;然而，從程序中消除循環所需的修改使其在實踐中變得更慢。「 – MvG 2012-08-07 10:57:21

一個簡單的解釋這個算法中，非常久遠的Java代碼，可以發現here

來源

2015-02-12 08:34:50

在Steinhaus-Johnson-Trotter算法中輸出交換列表的算法是什麼？

回答

相關問題