数列还原

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Main {
    /**
    *如果给我们一个序列（不含有任何未知的元素），我们可以通过两次循环获取有多少个顺序对。
    *但是如果插入一个未知元素，顺序对变化了多少呢？等于这个元素与前面元素的新增的顺序对，和后面比较的新增的顺序对。
    *如果插入多个呢？可以逐次插入，让每次只有一个位置插入元素，其他未知临时忽略就可以了。这样就能递归解决问题。
    *一个序列的总的顺序对，等于插入前的对数，加上逐次插入未知产生的对数。
    *总的合法排列就等于未知数排列的合法排列数。
    */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arrInput = br.readLine().trim().split(" ");
        int n = Integer.parseInt(arrInput[0]);
        int k = Integer.parseInt(arrInput[1]);
        int[] arrNum = new int[n];
        int knownedSeqPair = 0;
        ArrayList<Integer> listIndex = new ArrayList<Integer>();//记住模糊位置的索引
        ArrayList<Integer> listBlur = new ArrayList<Integer>();//记住模糊数字
        HashSet<Integer> setBook = new HashSet<Integer>();//找到模糊数字的工具
        arrInput = br.readLine().trim().split(" ");
        for (int i=0; i<arrInput.length; i++) {
            arrNum[i] = Integer.parseInt(arrInput[i]);
            if (arrNum[i] == 0) {//模糊的记住位置,用于擦除数据
                listIndex.add(i);
            } else {//不模糊的记住数据本身，用于找到模糊的数据
                setBook.add(arrNum[i]);
            }
        }
        for (int i=1; i<=n; i++) {//查找模糊的数字
            if (false == setBook.contains(i)) {
                listBlur.add(i);
            }
        }
        for (int i=0; i<arrNum.length; i++) {
            if (arrNum[i] != 0) {//不能是模糊数字
                for (int j=i+1; j<arrNum.length; j++) {
                    if (arrNum[j] != 0 && arrNum[i] < arrNum[j]) {//不能是模糊数字
                        knownedSeqPair++;
                    }
                }
            }
        }
        System.out.println(Main.getSeqNum(arrNum, listBlur, listIndex, knownedSeqPair, 0, k));
    }
    public static int getSeqNum(int[] arrNum, ArrayList<Integer> listBlur, ArrayList<Integer> listIndex, int knownedSeqPair, int n, int k) {
        int result = 0;
        if (n == listBlur.size()) {//子排列已经出现
            int sumSeqNum = knownedSeqPair;
            int i = 0;
            int j = 0;
            for (i=0; i<listBlur.size(); i++) {//计算新增的排列
                for (j=0; j<arrNum.length && arrNum[j] != 0; j++) {//前半部分
                    if (arrNum[j] < listBlur.get(i)) {
                        sumSeqNum++;
                    }
                }
                if (j < arrNum.length) {//插入，为下次会比较，判断是为了应对根本没有未知的情况
                    arrNum[j++] = listBlur.get(i);
                }
                for (; j<arrNum.length; j++) {//比较后面
                    if (arrNum[j] != 0 && arrNum[j] > listBlur.get(i)) {
                        sumSeqNum++;
                    }
                }
            }
            for (i=0; i<listIndex.size(); i++) {//擦除模糊数字的排列，用于下次
                arrNum[listIndex.get(i)] = 0;
            }
            if (sumSeqNum == k) {
                result = 1;
            }
        } else {
            for (int i=n; i<listBlur.size(); i++) {//其实等于n是因为不交换（自交换）也是一种情况。
                Collections.swap(listBlur, n, i);
                result += Main.getSeqNum(arrNum, listBlur, listIndex, knownedSeqPair, n+1, k);
                Collections.swap(listBlur, n, i);
            }
        }
        return result;
    }
}

1. 计算缺失的数字及其位置
2. 对缺失的数字进行全排列，然后填充到对应位置

3. 计算填充之后的数组的k值

    // 计算合法数量
   private static int legalCount(int[] nums, int k){
        boolean[] used = new boolean[nums.length+1];
        List<Integer> leftNum = new ArrayList<>(),
                leftIndex = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0) {
                used[nums[i]] = true;
            }else{
                leftIndex.add(i);
            }
        }
   
        for(int i=1;i<used.length;i++){
            if(!used[i])
                leftNum.add(i);
        }
   
        List<List<Integer>> list = getOrder(leftNum);
        int count = 0;
        for(List<Integer> l : list){
            for(int i=0;i<leftIndex.size();i++){
                nums[leftIndex.get(i)] = l.get(i);
            }
            if(calculateCount(nums, k))
                count++;
        }
        return count;
    }
    // 排列组合
    private static List<List<Integer>> getOrder(List<Integer> nums){
        if(nums.size() == 1){
            List<Integer> temp = new ArrayList<>();
            temp.add(nums.get(0));
            List<List<Integer>> l = new ArrayList<>();
            l.add(temp);
            return l;
        }
        List<List<Integer>> result = new ArrayList<>();
        for(int i=0;i<nums.size();i++){
            int num = nums.get(i);
            nums.remove(i);
            List<List<Integer>> list = getOrder(nums);
            for(List<Integer> l : list){
                l.add(num);
                result.add(l);
            }
            nums.add(i, num);
        }
        return result;
    }
    // 计算顺序对是否满足要求
    private static boolean calculateCount(int[] nums, int aim){
        int count = 0;
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]!=0 && nums[i]> nums[j]){
                    count++;
                    if(count>aim)
                        return false;
                }
   
            }
        }
        return count == aim;
    }
   

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] array = new int[n];
            boolean[] flag = new boolean[n];
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
                if (array[i] != 0) flag[array[i]-1] = true;
            }
            //找出缺失数字
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++)
                if (!flag[i]) list.add(i+1);
            //得到缺失数字全排列
            ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
            getPermutation(listAll, list, 0);

            //原始数组的顺序对
            int orderPairCount = getOrderPairByArray(array);
            int res = 0;
            //依次求出产生的全排列和原始数组一起的顺序对
            for (ArrayList<Integer> arrayList: listAll) {
                int count = orderPairCount;
                int[] temp = Arrays.copyOf(array, array.length);
                count += getOrderPairByNew(temp, arrayList);
                if (count == k) res++;
            }
            System.out.println(res);
        }
    }

    private static int getOrderPairByNew(int[] array, ArrayList<Integer> list) {
        int count = 0;
        int j = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0) {
                array[i] = list.get(j++);
                for (int k = 0; k < i; k++)
                    if (array[k] < array[i]) count++;
                for (int k = i+1; k < array.length; k++)
                    if (array[i] < array[k]) count++;
            }
        }
        return count;
    }

    private static int getOrderPairByArray(int[] array) {
        int count = 0;
        for (int i = 0; i <array.length; i++) {
            for (int j = i + 1; j < array.length && array[i] != 0; j++)
                if (array[j] != 0 && array[i] < array[j])
                    count++;
        }
        return count;
    }

    private static void getPermutation(ArrayList<ArrayList<Integer>> listAll,
                                       ArrayList<Integer> list, int start) {
        if (start == list.size() - 1)
            listAll.add(new ArrayList<>(list));
        else {
            for (int i = start; i < list.size(); i++) {
                Collections.swap(list, start, i);
                getPermutation(listAll, list, start + 1);
                Collections.swap(list, start, i);
            }
        }
    }
}  

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;


public class Main {     public static int calc(int[] arr, int k) {         int ans = 0;         for (int i = 0; i < k - 1; i++) {             for (int j = i + 1; j < k; j++) {                 if (arr[i] > 0 && arr[i] < arr[j]) {                     ans++;                 }             }         }         return ans;     }     //计算全排列     public static void calperm(List<ArrayList<Integer>> perm,List<Integer> missNumList, int n){         if(n == missNumList.size()){             perm.add(new ArrayList<Integer>(missNumList));         }else{             for(int i=n;i<missNumList.size();i++){                 Collections.swap(missNumList, i, n);                 calperm(perm,missNumList,n+1);                 Collections.swap(missNumList, i, n);             }         }     }     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n, k;         n = sc.nextInt();         k = sc.nextInt();         int[] li = new int[n];         boolean[] appear = new boolean[n];         int[] missIdx = new int[15];         int[] missNum = new int[15];         int missCnt = 0;         int[][] smaller = new int[n][n+1];         int[][] larger = new int[n][n+1];         // 保存输入，并记录缺失数据下标，及标记已出现的数字         for (int i = 0; i < n; i++) {             li[i] = sc.nextInt();             if (li[i] == 0) {                 missIdx[missCnt++] = i;             } else {                 appear[li[i] - 1] = true;             }         }         // 找出所有缺失的数字         missCnt = 0;         for (int i = 0; i < n; i++) {             if (!appear[i]) {                 missNum[missCnt++] = i + 1;             }         }         // 统计现有数字的顺序对         int given = calc(li, li.length);         // 统计缺失数字放在不同位置上，所产生的顺序对（small+larger）         for (int i = 0; i < missCnt; i++) {             int small = 0, large = 0;             for (int j = 0; j < n; j++) {                 if (li[j] == 0) {                     smaller[j][missNum[i]] = small;                 } else if (li[j] < missNum[i]) {                     small++;                 }             }             for (int j = n - 1; j >= 0; j--) {                 if (li[j] == 0) {                     larger[j][missNum[i]] = large;                 } else if (li[j] > missNum[i]) {                     large++;                 }             }         }         int ans = 0;         List<ArrayList<Integer>> missNumPerm = new ArrayList<ArrayList<Integer>>();         List<Integer> missNumList = new ArrayList<Integer>();         for(int i=0;i<missCnt;i++){             missNumList.add(missNum[i]);         }         calperm(missNumPerm,missNumList,0);         for(ArrayList<Integer> missN:missNumPerm){             Integer[] mNum = new Integer[missN.size()];             missN.toArray(mNum);             int inner = calc(Arrays.stream(mNum).mapToInt(Integer::valueOf).toArray(),missN.size());             for(int i=0;i<missCnt;i++){                 inner += smaller[missIdx[i]][mNum[i]];                 inner+=larger[missIdx[i]][mNum[i]];             }             if(inner+given==k) ++ans;         }         System.out.println(ans);     }
}

	

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        int a[]=new int [n];
        int map[]=new int[n+1];
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
            map[a[i]]=1;
        }
        ArrayList<Integer>tag=new ArrayList<Integer>();
        for(int i=1;i<=n;i++){
            if(map[i]==0)
                tag.add(i);
        }
        ArrayList<ArrayList<Integer>>pers=permutation(tag,0);

        int count=0;
        for(int i=0;i<n;i++){
            if(a[i]!=0){
                for(int j=i+1;j<n;j++){
                    if(a[j]!=0&&a[i]<a[j])
                        count++;
                }
            }
        }
        int Res=0;
        for(ArrayList<Integer>temp:pers){
            int val=count;
            int []tempA=Arrays.copyOf(a,n);
            val+=calvalue(temp,tempA);
            if(val==k)
                Res++;
        }
        System.out.println(Res);
    }

   static ArrayList<ArrayList<Integer>>permus=new ArrayList<ArrayList<Integer>>();

    public static ArrayList<ArrayList<Integer>> permutation(ArrayList<Integer>a,int t){
        ArrayList<Integer> te=new ArrayList<Integer>();    
        int n=a.size();
        if(t>n)
            return null;
        if(t==n-1){
            permus.add(te);

        }

        for(int i=0;i<n;i++)
            te.add(a.get(i));


        for(int i=t;i<n;i++){
            int temp=a.get(t);
            a.set(t, a.get(i));
            a.set(i, temp);

            permutation(a,t+1);
            int temp1=a.get(t);
            a.set(t, a.get(i));
            a.set(i, temp1);

        } 
        return permus;
    }

    public static int calvalue(List<Integer>list,int [] A){
        int val=0;
        int j=0;
        for(int i=0;i<A.length;i++){
            if(A[i]==0){
                A[i]=list.get(j++);
                for(int k=0;k<i;k++)
                    if(A[k]!=0&&A[k]<A[i])
                        val++;
                for(int p=i+1;p<A.length;p++)
                    if(A[p]!=0&&A[p]>A[i])
                        val++;
            }

        }

        return val;
    }
}