为什么我的 Steinhaus-Johnson-Trotter 算法实施会产生重复排列？

Question

我已经使用 JavaScript 实现了 Steinhaus-Johnson-Trotter Algorithm，这个实现只计算数字数组的所有排列。

当数组的大小 >= 4 时，算法会产生重复的结果。我明白为什么它会产生结果，但我不确定如何避免这种情况，因为创建这些重复项满足算法原则。

class Direction {
    constructor(dir) {
        if(dir === 'LEFT' || dir === 'RIGHT') {
            this.dir = dir
        }
    }
    setDir(dir) {
        if(dir === 'LEFT' || dir === 'RIGHT') {
            this.dir = dir
        }
    }
    switchDir() {
        switch(this.dir) {
            case 'LEFT':
                this.dir = 'RIGHT'
                break
            case 'RIGHT':
                this.dir = 'LEFT'
                break
        }
    }
}
var permute = function(nums) {
    if(nums.length === 1) return [nums]
    if(nums.length === 2) return [nums, [nums[1], nums[0]]]
    // I'm only worried about arrays up to length 6
    const facts = [1, 2, 6, 24, 120, 720]
    const dirs = {}
    const max = Math.max(...nums)
    nums.forEach(v => {
        dirs[v] = new Direction('LEFT')
    })
    const res = []
    const move = (n) => {
        const i = nums.indexOf(n)
        const ele = dirs[n]
        switch(ele.dir) {
            case 'LEFT':
                [nums[i], nums[i - 1]] = [nums[i - 1], nums[i]]
                break
            case 'RIGHT':
                [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]]
                break
        }
        if(n === max) {
            return
        }
        nums.forEach(v => {
            if(v > n) dirs[v].switchDir()
        })
    }
    // Number is said to mobile if it can move to its direction
    const isMobile = (n) => {
        const d = dirs[n].dir
        if(d === 'LEFT' && nums.indexOf(n) !== 0) {
            return true
        }
        if(d === 'RIGHT' && nums.indexOf(n) !== nums.length - 1) {
            return true
        }
        return false
    }
    // Finding mobiles means finding the largest number and checking if it is mobile
    const findMobile = () => {
        // If not max then lets find the next largest mobile
        var num = Number.MIN_VALUE
        nums.forEach(v => {
            if(isMobile(v) && v > num) {
                num = v
            }
        })
        return num
    }
    // Loop through the max length factorial, included up to only 6 as req
    while(res.length < facts[nums.length - 1]) {
        const next = findMobile()
        move(next)
        res.push([...nums])
        console.log(res)
    }
    return res
};

测试用例：

    Test 1:
    Input: [1,2,3]
    Result: [[1,3,2],[3,1,2],[3,2,1],[2,3,1],[2,1,3],[1,2,3]], Passed
 
    Test 2:
    Input: [5,4,6,2]
    Result: [
  [ 5, 6, 4, 2 ], [ 6, 5, 4, 2 ],
  [ 5, 6, 4, 2 ], [ 5, 4, 6, 2 ],
  [ 5, 4, 2, 6 ], [ 4, 5, 2, 6 ],
  [ 4, 5, 6, 2 ], [ 4, 6, 5, 2 ],
  [ 6, 4, 5, 2 ], [ 6, 4, 2, 5 ],
  [ 4, 6, 2, 5 ], [ 4, 2, 6, 5 ],
  [ 4, 2, 5, 6 ], [ 4, 2, 6, 5 ],
  [ 4, 6, 2, 5 ], [ 6, 4, 2, 5 ],
  [ 4, 6, 2, 5 ], [ 4, 2, 6, 5 ],
  [ 4, 2, 5, 6 ], [ 4, 5, 2, 6 ],
  [ 4, 5, 6, 2 ], [ 4, 6, 5, 2 ],
  [ 6, 4, 5, 2 ], [ 6, 5, 4, 2 ]
], Failed

如结果所示，该算法正在生成重复项，但是如前所述，重复项之间的步骤满足算法要求。

我对算法的理解：

所有元素从右到左开始：

即。 <1<2<3<4

我们找到下一个最大的“移动”数字，在本例中为 4。然后我们将它移向它的方向。

即。 <1<2<4<3

重复该过程。

如果移动的手机号码小于另一个号码，则较大的号码将调换方向。

编辑我已经解决了，涉及到不检查手机号码大小和要换号的问题

Answer 1

将步骤与这个简单的 Python 实现 (ideone link to look at results, order is similar to wiki example) 进行比较。

我没有看到方向项与代码中的元素交换在一起

def SJTperms(a, dirs):
    n = len(a)
    id = -1
    for i in range(n):
        #   can check mobility           mobile                        largest mobile
        if (0<=i+dirs[i]<n)       and (a[i] > a[i+dirs[i]])     and ((id == -1) or (a[i] > a[id])):
            id = i

    if (id == -1):  #last permutation
        return False

    for i in range(n):
        if a[i] > a[id]:
            dirs[i] = - dirs[i]

    #swap elements AND their directions
    a[id], a[id + dirs[id]] = a[id + dirs[id]], a[id]
    t = dirs[id]
    dirs[id], dirs[id + t] = dirs[id + t], dirs[id]
    return True

a = [1,2,3,4]
d = [-1]*len(a)
cont = True
while cont:
    print(a)
    #print(d)
    cont = SJTperms(a, d)

为什么我的 Steinhaus-Johnson-Trotter 算法实施会产生重复排列？

Why is my Steinhaus-Johnson-Trotter Algorithm implementation producing duplicate permutations?

javascript

arrays

algorithm

permutation