Steinhaus-Johnson-Trotter算法JavaScript实现产生重复排列的问题咨询与解决记录

我最近用JavaScript实现了Steinhaus-Johnson-Trotter算法，专门用来生成数字数组的全排列。但遇到了一个问题：当数组长度≥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
};

测试用例 #

• 测试1：输入[1,2,3]，输出结果为[[1,3,2],[3,1,2],[3,2,1],[2,3,1],[2,1,3],[1,2,3]]，符合预期，测试通过。
• 测试2：输入[5,4,6,2]，输出结果出现大量重复排列，不符合全排列的唯一性要求，测试失败。

我对算法的理解 #

我理解的Steinhaus-Johnson-Trotter算法步骤是这样的：

所有元素初始方向为从右到左（即<1<2<3<4）。找到下一个最大的“可移动（mobile）”数字，例如4，然后将其向自身方向移动（即<1<2<4<3），重复此过程。如果移动的可移动数字小于另一个数字，则较大数字的方向会被反转。

问题解决（编辑补充） #

我已经找到问题所在并解决了！问题出在isMobile函数的判断逻辑上：我之前没有检查可移动数字与待交换数字的大小关系。根据算法定义，一个数字是“可移动”的，必须满足两个条件：

1. 它能向当前方向移动（不会超出数组边界）；
2. 它比相邻方向上的数字更大。

之前的isMobile只判断了第一个条件，导致一些不符合要求的数字被错误标记为可移动，进而触发了错误的移动操作，最终产生重复排列。修改isMobile函数，加入大小判断后，问题就解决了。

内容的提问来源于stack exchange，提问作者Rawley Fowler