SWUST OJ 541: 排列的字典序问题

谁践踏了优雅 2024-04-01 09:41 64阅读 0赞

**题目描述**  
n个元素\{1,2,…, n \}有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：

0 1 2 3 4 5

123 132 213 231 312 321

任务：给定n 以及n 个元素\{1,2,…, n \}的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。

**输入**

第1 行是元素个数n(n < 15)。接下来的1 行是n个元素{
        1,2,..., n }的一个排列。

**输出**

第一行是字典序值，第2行是按字典序排列的下一个排列。

**样例输入**

8
    2 6 4 5 8 1 7 3

**样例输出**

8227
    2 6 4 5 8 3 1 7

我们可以从从开始算，因为不能有重复，以1开头的后面有7位数有1*7！，然后以2开头的后面有六位数，但第二位要小于6，即有1、3、4、5满足，有4*6！，然后以26...开头的后面有5位数，要求第三位要小于4，即有1，3满足，有2*5！，，，依次类推。。。
           
    
    看例子：
    
    tot=0；
    
    比2小的数有1个，则 tot+=1*7！；
    
    比6小的数有4个，则 tot+=4*6！；
    
    比4小的数有2个，则 tot+=2*5！；
    
    比5小的数有2个，则 tot+=2*4！；
    
    比8小的数有3个，则 tot+=3*3！；
    
    比1小的数有0个，则 tot+=0*2！；
    
    比7小的数有1个，则 tot+=1*1！；
    
    比3小的数没有；
    
    （注：在排列中，求比某个数小的数的个数时，排除之前出现过的数）

如何得到2 6 4 5 8 1 7 3的下一个排列？
        1 从尾部往前找第一个P(i-1) < P(i)的位置
                2 6 4 4 5 8 1 <-- 7 <-- 3
            最终找到1是第一个变小的数字，记录下1的位置i-1
        2 从尾部往前找到第一个大于1的数
                2 6 4 4 5 8 1 7 3 <--
            最终找到3的位置，记录位置为m
        3 交换位置i-1和m的值
                2 6 4 4 5 8 3 7 1
        4 倒序i位置后的所有数据
                2 6 4 4 5 8 3 1 7

public class DictionarySort {
        
    
        public static int factorial(int n){
        
            if (n<=1){
        
                return 1;
            }
            return n * factorial(n-1);
        }
    
        public static int order(int[] arr,int n){
        
            int sum = 0;
            for (int i = 0; i < n; i++) {
        
                int num = arr[i];
                int count = 0;
                for (int j = i+1; j < n; j++) {
        
                    if (num > arr[j]){
        
                        count++;
                    }
                }
                sum += count*factorial(n-i-1);
            }
            return sum;
        }
    
        public static int[] nextDictionary(int[] arr,int n){
        
            int min = 0;
            int max = 0;
            for (int end = arr.length - 1; end >=1 ; end--) {
        
                if (arr[end]>arr[end-1]){
        
                    min = end-1;
                    break;
                }
            }
            for (int i = arr.length-1; i>=0; i--) {
        
                if (arr[i]>arr[min]){
        
                    max = i;
                    break;
                }
            }
    
            swap(arr,min,max);
            reverse(arr,min+1, n-1);
            printArray(arr);
            System.out.println();
            return arr;
        }
    
        public static void reverse(int[] arr,int i,int j){
        
            while (i<j){
        
                int temp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = temp;
            }
        }
    
        public static void swap(int[] arr,int i,int j){
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void printArray(int[] arr){
        
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+" ");
            }
        }
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
        
                arr[i] = sc.nextInt();
            }
            System.out.println(order(arr, n));
            nextDictionary(arr, n);
        }
    }