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 代码