math - 順列のSteinhaus–Johnson–Trotterアルゴリズムでスワップのリストを出力するアルゴリズムは何ですか？

Question

このページによると、新しい順列はそれぞれ、前の順列とは異なる単一の隣接するスワップのみである順列のリストを出力することが可能です。そして、これは網羅的であり、すべての順列を通過します。

説明からアルゴリズムを理解するのに苦労しています。各順列の間に必要なスワップを出力するアルゴリズムを書きたいと思います。

Answer 1

スワップが必要な次の要素の決定は、順列の現在の状態によって定義されるため、次のスワップを生成することは、次の順列を生成することほど簡単ではありません。

どちらかを生成する必要がある場合は、 Even の 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

Answer 2

このアルゴリズムの簡単な説明と Java コードは、ここにあります。