从整数到第i个非递减数字数组的映射

Question

以非递减顺序考虑所有长度为

n

的数字0-9的数组。有

binom(9+n, n)

这样的数组。对于固定的

n

，我们可以按排序顺序考虑数组。我希望能够按此顺序直接跳到第

i

个数组，而无需首先明确枚举所有数组。

你怎么能这样做？

Answer 1

为了抽象你的公式，给定 n 个数字可以取 k 个不同的值，有 binom(k+n-1, n) 这样的序列。

有多少个序列以数字 d 开头？好吧，我们有 n-1 个剩余数字和 k-d 个不同的值，所以 binom(k-d+n-2, n-1).

您可以使用二进制搜索或只是迭代（因为只有 10 个）来找出第一个数字。然后，调整你的问题并重复。

调整是将n减1，将target rank减去从低位开始的count。您还需要将位数减少到剩余的计数（即最后一位最多使用 9）。

Answer 2

你对数组的数量是正确的。

所以我们必须按照数字的字典顺序得到组合。

然后用数组匹配组合 - 组合项之间的差异（减一）对应于数组增量。

数字 0..3 的示例（为简单起见），您需要

d=9

def cnk(n, k):
    k = min(k, n - k)
    if k <= 0:
        return 1 if k == 0 else 0
    res = 1
    for i in range(k):
        res = res * (n - i) // (i + 1)
    return res

def num2comb(n, k, m):  #combination by nymber in lex order
    res = []
    next = 1
    while k > 0:
        cn = cnk(n - 1, k - 1)
        if m < cn:
            res.append(next)
            k -= 1
        else:
            m -= cn
        n -= 1
        next += 1
    return res

nn = 3
d = 3
for i in range(cnk(nn+d, nn)):
    comb = num2comb(nn+d, nn, i)
    minv = comb[0]-1
    arr = [minv]
    for j in range(nn-1):
        t = comb[j+1]-comb[j]-1+minv
        arr.append(t)
        minv = t
    print(i, comb, arr)

控制所有指数的输出。为了您的目的设置

d=9

并获取所需索引i

的数组

0 [1, 2, 3] [0, 0, 0]
1 [1, 2, 4] [0, 0, 1]
2 [1, 2, 5] [0, 0, 2]
3 [1, 2, 6] [0, 0, 3]
4 [1, 3, 4] [0, 1, 1]
5 [1, 3, 5] [0, 1, 2]
6 [1, 3, 6] [0, 1, 3]
7 [1, 4, 5] [0, 2, 2]
8 [1, 4, 6] [0, 2, 3]
9 [1, 5, 6] [0, 3, 3]
10 [2, 3, 4] [1, 1, 1]
11 [2, 3, 5] [1, 1, 2]
12 [2, 3, 6] [1, 1, 3]
13 [2, 4, 5] [1, 2, 2]
14 [2, 4, 6] [1, 2, 3]
15 [2, 5, 6] [1, 3, 3]
16 [3, 4, 5] [2, 2, 2]
17 [3, 4, 6] [2, 2, 3]
18 [3, 5, 6] [2, 3, 3]
19 [4, 5, 6] [3, 3, 3]

作为函数：

def nondecrarr(n, i):
    comb = num2comb(n+9, n, i)
    minv = comb[0]-1
    arr = [minv]
    for j in range(n-1):
        t = comb[j+1]-comb[j]-1+minv
        arr.append(t)
        minv = t
    return arr