How can I generate the next permutation using the Steinhaus–Johnson–Trotter algorithm?

Question

How can I take a permutation i and generate the (i+1)th permutation with the Steinhaus-Johnson-Trotter (SJT) algorithm? There are solutions to generate all of the permutations using the SJT algorithm, but since the permutations follow a pattern, I want to generate the next permutation.

I attempted to write such an algorithm. However, for the permutation 4213, the next permutation is supposed to be 2413, but this program gives the previous permutation 4231 instead. How I can generate the next permutation i+1, given i?

public class SJTAlgorithm {


    private int[] dir;

    // Constructor to initialize the directions
    public SJTAlgorithm(int n) {
        dir = new int[n];
        // Initially, all directions are set to -1 (left).
        for (int i = 0; i < n; i++) {
            dir[i] = -1;
        }
    }
    // Function to check if an integer is mobile
    private static boolean isMobile(int[] permutation, int[] dir, int index) {
        int nextIndex = index + dir[index];
        // An integer is mobile if the next index is within bounds and
        // the adjacent integer in the direction it's moving is smaller.
        return nextIndex >= 0 && nextIndex < permutation.length && permutation[index] > permutation[nextIndex];
    }

    // Function to find the largest mobile integer
    private static int getMobileIndex(int[] permutation, int[] dir) {
        int mobilePrev = 0, mobileIndex = -1;
        for (int i = 0; i < permutation.length; i++) {
            if (isMobile(permutation, dir, i) && permutation[i] > mobilePrev) {
                mobilePrev = permutation[i];
                mobileIndex = i;
            }
        }
        return mobileIndex;
    }

    // Function to find the next permutation
    public static int[] nextPermutation(int[] permutation) {
        int n = permutation.length;
        int[] dir = new int[n];

        // Initially, all directions are set to -1 (left).
        for (int i = 0; i < n; i++) {
            dir[i] = -1;
        }

        // Find the largest mobile integer in the permutation.
        int mobileIndex = getMobileIndex(permutation, dir);
        if (mobileIndex == -1) { // No mobile integer means this is the last permutation.
            return null;
        }

        // Swap the mobile integer with the adjacent integer in its current direction.
        int swapIndex = mobileIndex + dir[mobileIndex];
        int temp = permutation[mobileIndex];
        permutation[mobileIndex] = permutation[swapIndex];
        permutation[swapIndex] = temp;

        // Change the direction of all integers larger than the current mobile integer.
        for (int i = 0; i < n; i++) {
            if (permutation[i] > permutation[swapIndex]) {
                dir[i] = -dir[i];
            }
        }

        return permutation;
    }

    // Main function to test the algorithm
    public static void main(String[] args) {
        int[] permutation = {4, 2, 1, 3};
        SJTAlgorithm sjt = new SJTAlgorithm(permutation.length); // Initialize the SJTAlgorithm instance
        int[] nextPerm = sjt.nextPermutation(permutation);

        if (nextPerm != null) {
            System.out.println("Next permutation:");
            for (int num : nextPerm) {
                System.out.print(num + " ");
            }
        } else {
            System.out.println("No next permutation available (last permutation reached).");
        }
    }
}

[![enter image description here][1]][1]

  [1]: https://i.sstatic.net/TajXb.jpg

Answer 1

Upon further inspection, it is not possible to generate the next permutation i+1 given a permutation i. This is because the program has no way of knowing what the directions of the permutation i numbers are by itself.