数列还原

#题目的意思应该是第二列输入的n个数不重复吧？也就是包含所有的1,2,3,...,n
# _*_ coding:utf-8 _*_
import itertools

#满足 i < j 且 A[i] < A[j] 的对数
def OrderNum(list1):
    num = 0
    for i in range(len(list1)-1):
        for j in range(i+1,len(list1)):
            if list1[i] < list1[j]:
                num += 1
    return num


#n = 5
#k = 5
#listn =   [4, 0, 0, 2, 0]

nk = list(map(int,input().split()))
n = nk[0]
k = nk[1]
listn = list(map(int,input().split()))
s = ""
for i in range(1,n+1):
    if i not in listn :
        s += str(i)
# print(s)

a = []#存放0的位置
for i in range(n):
    if listn[i] == 0:
        a.append(i)

N = 0
for item in itertools.permutations(s, len(a)):
    item = [int(t) for t in item]
    #print(item)
    for i in range(len(a)):
        listn[a[i]] = item[i]
    # print(listn)
    if OrderNum(listn) == k:
        #print(listn)
        N += 1
print(N)

这个题，大概这么来做：
1、找出缺失值nums，缺失位置index，在函数findpos里

def findpos(mat, n, k):
    index = []#存储0的位置
    nums =[]#存储缺失的数字
    num = 0#缺失数字个数
    for i in range(n):
        if i+1 not in mat:
            nums.append(i+1)
            num += 1
        if mat[i] == 0:
            index.append(i)
    return index, nums, num

def func(mat,n,k):
    num = 0
    for j in range(n):
        for a in range(j+1,n):
            if mat[a]>mat[j]:
                num +=1 
    if num == k:
        return 1
    return 0
def insert(mat, index, nums, num):
    #下一步在于怎么进行坑位的选择，以及顺序对的统计
    #all_mat = []
    global count
    for i in range(num):
        mat[index[0]] = nums[i]#第一个坑位依次等于nums中的数
        # 上一步list index out of range ==》nums[1,3,5]/index[1,2,4]||是否在迭代的过程中，index,nums到最后一层已经改变了，再倒退的时候出现index出错的问题？
        index1 = index[1:]
        nums1 = nums[0:i]+nums[i+1:]
        num1 = num-1
        if num1 == 0:
            #print(mat)#--这里显示mat是已经插入正确了的
            #all_mat.append(mat)# 这里all_mat却不能正确的把每个mat有效输出
            # 那么能否直接在这里就用mat进行后续的操作？不再单独产生all_mat,对每个mat判断一次？
            #print(all_mat)
            x = func(mat,n,k)
            #print(x)
            count += x
            #print(count)
        insert(mat, index1, nums1, num1)
    return count
[n,k] = [int(a) for a in input().split()]
matA = [int(a) for a in input().split()]
[index, nums, num] = findpos(matA, n, k)
count = 0
print(insert(matA, index, nums, num))
	

		
	

'''
    思路：
    将 A 中缺失的部分补全，然后求顺序对数，等于 k 则计数 +1。
    为此，先要找到 A 缺失的是哪些数字，它们分别在什么位置。
    其次，将这些缺失的数字全排列，分别按位置填充到 A 中，
    计算当前组合的情况下 A 的顺序对数。
'''

from itertools import permutations
def number(A): # 求 A 中顺序对数
    count = 0
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            if A[i] < A[j]:
                count += 1
    return count
 
n, k = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
B = list(range(1,n+1))
X = list(set(B).difference(set(A))) # B 和 A 的差集，即缺失的数字
Y = list(permutations(X)) # 求 X 的全排列
index = []
for i in range(n):
    if A[i] == 0:
        index.append(i) # A 中 0 所在位置的索引
m = len(index)
count = 0
for x in Y:
    for i in range(m):
        A[index[i]] = x[i]
    num = number(A)
    if num == k:
        count += 1
print(count)

import itertools
import copy

def sum2(list,arr):#sum2返回每个组合的顺序对数
    sum,j=0,0
    for i in range(len(arr)):
        if arr[i]==0:
            arr[i]=list[j]
            j+=1
            for k in range(i):#分别计算左右两边组成的顺序对数
                if arr[k]!=0 and arr[k]<arr[i]:
                    sum+=1
            for k in range(i+1,len(arr)):
                if arr[k]!=0 and arr[k]>arr[i]:
                    sum+=1
    return sum

n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
sum1=0
for i in range(n):#计算已知数字的顺序对数sum1
    if a[i]!=0:
        for j in range(i+1,n):
            if a[j]!=0 and a[i]<a[j]:
                sum1+=1
number=list(range(1,n+1))
for i in a:
    if i!=0:
        number.remove(i)#将已有的数字从number中去掉
array=list(itertools.permutations(number,len(number)))#所有未知数的排列情况， itertools用于字符串/数字的全排列
result=0
for x in range(len(array)):
    total=0
    temp=list(array[x])
    temparray=copy.deepcopy(a)#由于传的是直接引用，数组a的值会改变，所以需要深度（完全复制，不共享内存）复制
    total=sum2(temp,temparray)+sum1#判断sum1+sum2是否等于k
    if total==k:
        result+=1
print(result)

抄的python语言排行第一的代码，自己加了点注释。
和自己最开始的想法差不多，缺失元素挨着往进填，不符合情况时，就换下一个元素，这样复杂度会比遍历少一点， 因为当遇到不符合的情况不会继续往下遍历，相当于遍历的树被剪枝了
但自己没想到可以这么用递归来实现，还是膜拜下大神。 #!/usr/bin/env python # coding:utf-8   def sequence(n, k, A):#n为序列长度，k为要求的排列数，A为原始序列  def right_seq(remain, zero_loc, diff_list, A):#remain还需要的顺序对数，zero_loc缺失数据位置，diff_list缺失的数据，A原始序列  if remain < 0 or (remain > 0 and len(zero_loc) <= 0):#若所需对数小于0或序列用完了，对数没达到，不符合要求，递归结束  # print "not right",remain,A  return 0  if remain == 0 and len(zero_loc) == 0:#对数为0，序列刚好用完，符合要求  # print "====right====",A  return 1  result = 0#符合要求的数量  for i in range(len(diff_list)):
            A[zero_loc[0]] = diff_list[i] # 计算新增的合法排列数  new_add = 0  for j in range(len(A)): if A[j] != 0 and (
                    (j < zero_loc[0] and A[j] < A[zero_loc[0]]) or (j > zero_loc[0] and A[j] > A[zero_loc[0]])):
                    new_add += 1  # print "A, newadd",A,new_add  result += right_seq(remain - new_add, zero_loc[1:], diff_list[:i] + diff_list[i + 1:], A)
            A[zero_loc[0]] = 0  return result # 缺失的数据  n_list = [i for i in range(0, n + 1)]
    diff_list = list(set(n_list) ^ set(A)) # print "diff_list",diff_list   # 缺失数据的位置  zero_loc = [] for i in range(n): if A[i] == 0:
            zero_loc.append(i) # print "zero_loc",zero_loc  origin_pair_num = 0  for i in range(n - 1): if A[i] != 0: for j in range(i + 1, n): if A[j] > A[i]:
                    origin_pair_num += 1#原序列顺序对数  # print "origin_pair_num",origin_pair_num   return right_seq(k - origin_pair_num, zero_loc, diff_list, A) if __name__ == '__main__':
    firstline = raw_input()
    secondline = raw_input()
    n, k = [int(i) for i in firstline.strip().split(' ')]
    A = [int(i) for i in secondline.strip().split(' ')] print sequence(n, k, A)