如何直接定位排序后第i个长度为n的非降序0-9数字数组？

这类长度为n、元素为0-9的非降序数组，本质是从10个数字中可重复选取n个的组合，总数为binom(n+9, n)，排序规则默认采用字典序（非降序数组的自然排列顺序）。要直接定位第i个数组，无需枚举所有，可通过逐位确定元素+组合数前缀判断实现，具体步骤如下：

核心思路 #

每个非降序数组对应一组可重复组合，我们可以从左到右逐个确定数组的元素：对当前位置，尝试从最小可选数字开始，计算「当前位选该数字时，后续所有合法数组的数量」，判断目标索引是否落在这个区间内，从而确定当前位的数字，再缩小范围处理下一位。

具体步骤 #

假设目标索引i从0开始（若用户输入的i从1开始，先执行i = i - 1转换）：

1. 初始化参数：
   • 剩余需要确定的位置数k = n
   • 当前位置允许的最小数字min_num = 0
   • 剩余目标索引remaining_i = i
   • 结果数组res = []
2. 循环n次（每次确定一位）：
   • 遍历候选数字d从min_num到9：
     • 计算组合数cnt = binom( (k-1) + (9 - d), k-1 )：这个值代表「当前位选d，剩下k-1个元素都≥d时的合法数组总数」（等价于从d~9共10-d个数字中可重复选k-1个的组合数）。
     • 如果remaining_i < cnt：说明目标数组的当前位就是d，将d加入res，更新min_num = d、k = k - 1，进入下一轮循环。
     • 否则：目标数组不在这个分支，执行remaining_i = remaining_i - cnt，继续尝试下一个更大的d。
3. 循环结束后，res即为第i个非降序数组。

组合数计算说明 #

需要实现一个高效的组合数计算函数binom(a, b)：

• 当b < 0或b > a时，返回0
• 为避免重复计算或溢出，可采用两种方式：
  • 递推式：binom(a, b) = binom(a-1, b-1) + binom(a-1, b)，可提前用动态规划预处理小范围的组合数
  • 乘积式：binom(a, b) = product_{k=1 to b} (a - b + k) / k，适合实时计算，Python中可直接用整数运算避免精度问题

示例验证 #

以n=2，i=10（0开始）为例：

1. 初始k=2，min_num=0，remaining_i=10
2. 尝试d=0：计算cnt=binom(1+9,1)=10，10 >=10，执行remaining_i=10-10=0，继续下一个d
3. 尝试d=1：计算cnt=binom(1+8,1)=9，0 <9，确定当前位为1，加入res，更新min_num=1，k=1
4. 下一轮循环，尝试d=1：计算cnt=binom(0+8,0)=1，0 <1，确定当前位为1，加入res
5. 最终结果为[1,1]，符合预期（前10个是0开头的数组，第10个是1开头的第一个数组）

内容的提问来源于stack exchange，提问作者Simd