如何用Steinhaus-Johnson-Trotter算法生成指定排列的下一个排列？

你的代码核心问题在于方向数组没有持久化，且未根据目标排列的生成历史初始化正确的方向状态：

1. 静态的nextPermutation方法每次调用都会新建方向数组并重置为全左（-1），完全丢失了SJT算法需要持续跟踪的方向状态。
2. 对于非初始排列（如4213），初始全左的方向数组是错误的——在SJT序列中，4213对应的方向数组中，元素4的方向应为向右（1），而非向左。

这导致你的代码错误地将3识别为最大可移动元素，交换后得到4231（这是4213的前一个排列），而非预期的2413。

修正后的代码 #

public class SJTAlgorithm {

    private int[] dir;
    private int[] currentPerm;

    // 构造函数：从初始排列1,2,...,n开始
    public SJTAlgorithm(int n) {
        dir = new int[n];
        currentPerm = new int[n];
        for (int i = 0; i < n; i++) {
            currentPerm[i] = i + 1;
            dir[i] = -1; // 初始方向全向左
        }
    }

    // 构造函数：从指定排列开始，自动计算正确的方向数组
    public SJTAlgorithm(int[] permutation) {
        currentPerm = permutation.clone();
        int n = permutation.length;
        dir = new int[n];

        // 通过模拟从初始排列生成到目标排列的过程，获取正确方向状态
        SJTAlgorithm tempSJT = new SJTAlgorithm(n);
        boolean found = false;
        while (!found) {
            if (arraysEqual(tempSJT.currentPerm, permutation)) {
                System.arraycopy(tempSJT.dir, 0, dir, 0, n);
                found = true;
            } else {
                int[] next = tempSJT.nextPermutation();
                if (next == null) {
                    throw new IllegalArgumentException("输入排列不是有效的全排列");
                }
            }
        }
    }

    private static boolean arraysEqual(int[] a, int[] b) {
        if (a.length != b.length) return false;
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }

    // 判断指定位置的元素是否可移动
    private boolean isMobile(int index) {
        int nextIndex = index + dir[index];
        return nextIndex >= 0 && nextIndex < currentPerm.length && currentPerm[index] > currentPerm[nextIndex];
    }

    // 找到最大的可移动元素的索引
    private int getMobileIndex() {
        int mobilePrev = 0, mobileIndex = -1;
        for (int i = 0; i < currentPerm.length; i++) {
            if (isMobile(i) && currentPerm[i] > mobilePrev) {
                mobilePrev = currentPerm[i];
                mobileIndex = i;
            }
        }
        return mobileIndex;
    }

    // 生成下一个排列
    public int[] nextPermutation() {
        int n = currentPerm.length;
        int mobileIndex = getMobileIndex();
        
        if (mobileIndex == -1) { // 无可用移动元素，已到最后一个排列
            return null;
        }

        int mobileValue = currentPerm[mobileIndex];
        // 交换可移动元素与方向指向的相邻元素
        int swapIndex = mobileIndex + dir[mobileIndex];
        int temp = currentPerm[mobileIndex];
        currentPerm[mobileIndex] = currentPerm[swapIndex];
        currentPerm[swapIndex] = temp;

        // 反转所有比移动元素大的元素的方向
        for (int i = 0; i < n; i++) {
            if (currentPerm[i] > mobileValue) {
                dir[i] = -dir[i];
            }
        }

        return currentPerm.clone();
    }

    // 获取当前排列
    public int[] getCurrentPerm() {
        return currentPerm.clone();
    }

    public static void main(String[] args) {
        int[] targetPerm = {4, 2, 1, 3};
        SJTAlgorithm sjt = new SJTAlgorithm(targetPerm);
        int[] nextPerm = sjt.nextPermutation();

        if (nextPerm != null) {
            System.out.println("Next permutation:");
            for (int num : nextPerm) {
                System.out.print(num + " ");
            }
            // 输出结果：2 4 1 3
        } else {
            System.out.println("已到达最后一个排列，无下一个排列。");
        }
    }
}

关键修正点 #

1. 状态持久化：将排列数组currentPerm和方向数组dir作为类成员变量，每次调用nextPermutation时保留状态，不再重置。
2. 支持指定排列初始化：新增构造函数，通过模拟从初始排列生成到目标排列的过程，自动获取正确的方向数组状态，解决非初始排列的方向初始化问题。
3. 方法非静态化：将isMobile、getMobileIndex等方法改为非静态，直接使用类成员变量的状态，避免静态方法的无状态问题。
4. 明确移动元素值：使用交换前的移动元素值mobileValue来判断需要反转方向的元素，逻辑更清晰，避免混淆。

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