生成排列之Johnson-Trotter算法的java实现

import java.util.Scanner;

public class TangRongjie {
    //求最大的移动元素
    public static int maxmove(int n, int[] id, boolean[] f) {
        //k存储最大移动元素的下标
        int k = -1, max = 0;
        for(int i = 0; i < n; i++) {
            //当前元素的方向是左边，则与左边的元素比较看是否可以移动
            //若可移动则与当前可移动最大值比较，且不能越界
            if(f[i] == false) {
                if(i > 0 && id[i] > id[i - 1] && id[i] > max) {
                    k = i;
                    max = id[i];
                }
            }
            //右边
            else {
                if(i < n - 1 && id[i] >id[i + 1] && id[i] > max) {
                    k = i;
                    max = id[i];
                }
            }
        }
        return k;
    }
    //元素和方向的交换
    public static int[] swap2(int[] id, boolean[] f, int i, int j) {
        int temp = id[i];
        id[i] = id[j];
        id[j] = temp;
        boolean temp1 = f[i];
        f[i] = f[j];
        f[j] = temp1;
        return id;
    }
    //调转方向
    public static boolean[] reverseid(int[] id, int k, boolean[] f) {
        for(int i = 0; i < id.length; i++) {
            if(id[i] > id[k])
                f[i] = f[i]?false:true;
        }
        return f;
    }
    
    public static void jt(int n) {
        //方向数组，false为左，true为右
        boolean[] flag = new boolean[n];
        //数字数组
        int[] idata = new int[n];
        //k为当前可移动元素的最大值
        int k = 0;
        //初始化两个数组
        for(int i = 0; i < n; i++) {
            idata[i] = i + 1;
            flag[i] = false;
        }
        //输出第一个初始化的排列，此排列不会自动生成
        for(int i = 0; i < n; i++)
            System.out.print(idata[i]);
        System.out.println();
        //初始化k，获取第一个可移动的最大元素
        k = maxmove(n, idata, flag);
        //循环直到没有可移动的元素
        while(k != -1) {
            //可向右移动
            if(flag[k]) {
                //移动时，将元素和方向都交换
                idata = swap2(idata, flag, k, k + 1);
                //此时k所在的元素已经向右交换，k也需要对应加1
                k++;
            }
            //可向左移动
            else {
                idata = swap2(idata, flag, k, k - 1);
                k--;
            }
            //调转所有大于k的元素的方向
            flag = reverseid(idata, k, flag);
            //输出当前的一个排列
            for(int i = 0; i < n; i++)
                System.out.print(idata[i]);
            System.out.println();
            //获取下一个k
            k = maxmove(n, idata, flag);
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        //调用算法
        jt(n);
        in.close();
    }
}