Partial Gene Orderings

Similar species will share many of the same genes, possibly with modifications. Thus, we can compare two genomes by analyzing the orderings of their genes, then inferring which rearrangements have separated the genes. In “Enumerating Gene Orders”, we used permutations to model gene orderings. Yet two genomes will have evolved along their own separate paths, and so they won’t share all of the same genes. As a result, we should modify the notion of permutation in order to quantify the notion of partial gene orderings.

Problem
A partial permutation is an ordering of only kk objects taken from a collection containing nn objects (i.e., k≤nk≤n). For example, one partial permutation of three of the first eight positive integers is given by (5,7,2)(5,7,2).
The statistic P(n,k)P(n,k) counts the total number of partial permutations of kk objects that can be formed from a collection of nn objects. Note that P(n,n)P(n,n) is just the number of permutations of nn objects, which we found to be equal to n!=n(n−1)(n−2)⋯(3)(2)n!=n(n−1)(n−2)⋯(3)(2) in “Enumerating Gene Orders”.
Given: Positive integers nn and kk such that 100≥n>0100≥n>0 and 10≥k>010≥k>0.
Return: The total number of partial permutations P(n,k)P(n,k), modulo 1,000,000.
Sample Dataset
21 7
Sample Output
51200

解题思路

本题就是全排列的变种，也就是不完全排列。对于第一个位置其有 21 种可能，第二个位置有 20 ，依次类推第 k 个位置有 21 - k + 1 种可能，将上述结果累乘，然后取 1_000_000 模即可。

  1. n, k = map(int, input().split())
  2. res = 1
  3. for _ in range(k):
  4.     res = (res * n) % 1_000_000
  5.     n -= 1
  6. print(res)

思考：如何输出这些组合呢？也就是如何知道在第 x 位置有那些选择可能呢？

  1. from typing import List
  2. class Solution:
  3.     def partialPermutations(self, nums: List[int], k: int) -> List[List[int]]:
  4.         n = len(nums)
  5.         res = []
  6.         visited = [False] * n  # 全局标记选过下标
  7.         path = []
  8.         def backtrace() -> None:
  9.             """回溯函数：每个位置上选取值的所有可能"""
  10.             if k == len(path):  # 达到 k 个组合，加入答案中
  11.                 res.append(path[:])  # 此处必须拷贝，否则传引用是同一份 path
  12.                 return  # 不准继续添加
  13.             for j in range(n):
  14.                 if not visited[j]:  # 该下标没被选过
  15.                     # 尝试选择该下标对应数字 nums[j]
  16.                     visited[j] = True
  17.                     path.append(nums[j])  # 选择当前 s[j]
  18.                     backtrace()  # 下一个填充位置组合
  19.                     # 撤销上面选择
  20.                     visited[j] = False
  21.                     path.pop()
  22.         backtrace()
  23.         return res
  25. n, k = map(int, input().split())
  26. for lst in Solution().partialPermutations(list(range(1, n + 1)), k):
  27.     print(lst)

输出：

  1. 输入：7 3
  2. [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 2, 6] [1, 2, 7] [1, 3, 2] [1, 3, 4] [1, 3, 5] [1, 3, 6] [1, 3, 7] [1, 4, 2] [1, 4, 3] [1, 4, 5] [1, 4, 6] [1, 4, 7] [1, 5, 2] [1, 5, 3] [1, 5, 4] [1, 5, 6] [1, 5, 7] [1, 6, 2] [1, 6, 3] [1, 6, 4] [1, 6, 5] [1, 6, 7] [1, 7, 2] [1, 7, 3] [1, 7, 4] [1, 7, 5] [1, 7, 6]
  3. [2, 1, 3] [2, 1, 4] [2, 1, 5] [2, 1, 6] [2, 1, 7] [2, 3, 1] [2, 3, 4] [2, 3, 5] [2, 3, 6] [2, 3, 7] [2, 4, 1] [2, 4, 3] [2, 4, 5] [2, 4, 6] [2, 4, 7] [2, 5, 1] [2, 5, 3] [2, 5, 4] [2, 5, 6] [2, 5, 7] [2, 6, 1] [2, 6, 3] [2, 6, 4] [2, 6, 5] [2, 6, 7] [2, 7, 1] [2, 7, 3] [2, 7, 4] [2, 7, 5] [2, 7, 6] 
  4. [3, 1, 2] [3, 1, 4] [3, 1, 5] [3, 1, 6] [3, 1, 7] [3, 2, 1] [3, 2, 4] [3, 2, 5] [3, 2, 6] [3, 2, 7] [3, 4, 1] [3, 4, 2] [3, 4, 5] [3, 4, 6] [3, 4, 7] [3, 5, 1] [3, 5, 2] [3, 5, 4] [3, 5, 6] [3, 5, 7] [3, 6, 1] [3, 6, 2] [3, 6, 4] [3, 6, 5] [3, 6, 7] [3, 7, 1] [3, 7, 2] [3, 7, 4] [3, 7, 5] [3, 7, 6]
  5. [4, 1, 2] [4, 1, 3] [4, 1, 5] [4, 1, 6] [4, 1, 7] [4, 2, 1] [4, 2, 3] [4, 2, 5] [4, 2, 6] [4, 2, 7] [4, 3, 1] [4, 3, 2] [4, 3, 5] [4, 3, 6] [4, 3, 7] [4, 5, 1] [4, 5, 2] [4, 5, 3] [4, 5, 6] [4, 5, 7] [4, 6, 1] [4, 6, 2] [4, 6, 3] [4, 6, 5] [4, 6, 7] [4, 7, 1] [4, 7, 2] [4, 7, 3] [4, 7, 5] [4, 7, 6] 
  6. [5, 1, 2] [5, 1, 3] [5, 1, 4] [5, 1, 6] [5, 1, 7] [5, 2, 1] [5, 2, 3] [5, 2, 4] [5, 2, 6] [5, 2, 7] [5, 3, 1] [5, 3, 2] [5, 3, 4] [5, 3, 6] [5, 3, 7] [5, 4, 1] [5, 4, 2] [5, 4, 3] [5, 4, 6] [5, 4, 7] [5, 6, 1] [5, 6, 2] [5, 6, 3] [5, 6, 4] [5, 6, 7] [5, 7, 1] [5, 7, 2] [5, 7, 3] [5, 7, 4] [5, 7, 6] 
  7. [6, 1, 2] [6, 1, 3] [6, 1, 4] [6, 1, 5] [6, 1, 7] [6, 2, 1] [6, 2, 3] [6, 2, 4] [6, 2, 5] [6, 2, 7] [6, 3, 1] [6, 3, 2] [6, 3, 4] [6, 3, 5] [6, 3, 7] [6, 4, 1] [6, 4, 2] [6, 4, 3] [6, 4, 5] [6, 4, 7] [6, 5, 1] [6, 5, 2] [6, 5, 3] [6, 5, 4] [6, 5, 7] [6, 7, 1] [6, 7, 2] [6, 7, 3] [6, 7, 4] [6, 7, 5]
  8. [7, 1, 2] [7, 1, 3] [7, 1, 4] [7, 1, 5] [7, 1, 6] [7, 2, 1] [7, 2, 3] [7, 2, 4] [7, 2, 5] [7, 2, 6] [7, 3, 1] [7, 3, 2] [7, 3, 4] [7, 3, 5] [7, 3, 6] [7, 4, 1] [7, 4, 2] [7, 4, 3] [7, 4, 5] [7, 4, 6] [7, 5, 1] [7, 5, 2] [7, 5, 3] [7, 5, 4] [7, 5, 6] [7, 6, 1] [7, 6, 2] [7, 6, 3] [7, 6, 4] [7, 6, 5]