next_permutation()函数解释和实现

1,2,3,…,N的全排列分别表示1,2,…,N!,123…N就是最小的1，N…21就是最大的N!
C++中有一个函数next_permutation可以求解任一个序列的下一个序列，例如123…N，借用这个函数就得到123…N(N-1)
可以手写实现这个函数：1.从后往前找到第一个a[k] < a[k+1]的位置k
2.在a[k+1 …n]中找到大于a[k]的最小的数a[t]
3.交换a[k], a[t]，交换后可以发现，a[k+1 …n]是单调递减的
4.将a[k+1 …n]翻转

图示

Java 代码

import java.util.*;

class Main{
    static int N = 10010;
    static int[] a = new int[N];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 1; i <= n;i++)  a[i] = sc.nextInt();
        while(m-- > 0){   //求下m个序列，就是+m，执行m次next_permutation
            int k = n-1;
            while(a[k] > a[k+1]) k--;
            int t = n;
            while(a[t] < a[k]) t--;
            int temp = a[k];
            a[k] = a[t];
            a[t] = temp;
            for(int i = k+1;i <= (k+1+n) >> 1;i++){
                int tmp = a[i];
                a[i] = a[k+1+n-i];
                a[k+1+n-i] = tmp;
            }
        }
        for(int i = 1;i <= n;i++) System.out.print(a[i] + " ");
    }
}