时间戳

首页 > 解决方案 > 在具有非递减数字的数字序列中找到 N 的索引（不重构序列）

algorithm - 在具有非递减数字的数字序列中找到 N 的索引（不重构序列）

问题描述

考虑所有具有非递减顺序数字的非负整数的序列，即从左到右排序的数字（ OEIS 中的A009994）。此序列从 0 开始，包括 29、33 和 112 等数字，但不包括 30、31、32 或 105。

现在，给定一个数字不递减的数字 N，我需要找到它在序列中的位置。或者，我需要找出有多少具有非递减数字的数字小于 N。

如果我们简单地生成序列中的每个数字直到找到 N，这可以在 O(N) 时间内完成。此外，我们可以将序列预先计算到某个最大数字，然后使用二分搜索在 O(日志 N)。但是由于在我的程序中，对于不同的 N 值，这种计算需要重复数千次（在内部循环中），如果我有一个更有效的算法甚至是一个封闭的公式来计算 index，那就太好了。

万一这很重要，在我的程序中 N 是以 7 为基数的四位数字，即 0 <= N <= 6666 7。

我的程序中 N的最大索引是 C(7+4-1, 4) - 1 = 10！/4！/6！- 1 = 209。

编辑：由于一些贡献者强调涉及重建序列的解决方案实际上有多好，我想指出内存使用也很重要。我认识到上述解决方案并不可怕，但它们确实看起来很浪费。寻找排列索引的问题有点相似，有一个简单的解决方案，不需要重构序列。

标签： algorithmcombinatoricsnumber-theory

解决方案

我发现了一个封闭公式解决方案，它扩展了 A009994 是按字典顺序重复的组合序列这一概念。

该解决方案由以下 Python 代码总结：

>>> from math import factorial as fact
>>> C = lambda n, k: n>=k and fact(n) // fact(k) // fact(n-k) or 0
>>> I = lambda a, b, c, d: C(10, 4) - C(9-a, 4) - C(8-b, 3) - C(7-c, 2) - C(6-d, 1) - 1
>>> I(0, 0, 0, 0)
0
>>> I(2, 2, 3, 5)
147
>>> I(6, 6, 6, 6)
209

解释

S让我们考虑3 位 ( =3) 数字的序列，K其中数字以 10 为底从左到右排序 ( B=10)

任何数字N都S可以通过其中出现的每个数字的计数来唯一标识，例如，如果我们有 1 次出现数字“2”和 2 次出现数字“3”，则N必须是“233”。

知道所有可用的数字后，我们可以使用星号和条形符号来表示N。在 base 10 中，我们有 10 位可用，因此我们需要B-1=9 条来分隔插槽：

|||||||||

对于N= 233，将星星放在它们的插槽中，我们有：

||*|**||||||

现在我们有一个B-1+ K=12 个对象的列表（9 条 + 3 颗星）。列表中星星的位置（从 0 开始）为：(2, 4, 5)。

简而言之，要将 any 转换N为它的星条形 3 元组表示，我们只需将每个数字添加N到它本身的N位置：

233 -> (2+0, 3+1, 3+2) -> (2, 4, 5)   (formula I)

同样，这个 3 元组唯一地标识以 10 为基数的任何 3 位数字，并且数字已排序。相反，为了生成任何经过排序的 3 位数字，我们可以从 12 个位置 {0, 1, 2, ..., 10, 11} 的集合中选择三个不同的项目。与所有可能的 3 元组的集合之间存在一一对应关系S，这些T元组具有从 0 到 11 的不同数字。

这种表示的优点是不会发生重复，因为两颗星不能在同一位置。这意味着这T只是12 个项目的 3-组合的集合。

也很容易看出，按T字典顺序排序等同于按S数字排序。

从这一点来说，我们可以使用教科书的公式进行组合。如问题中所述，这就是我用来查找 的长度的方法S。我不知道的是，在按升序排序的所有可能组合列表中查找组合位置的公式是：

I = C(n, k) - C(n-p1, k) - C(n-p2, k-1) - ... - C(n-pk, 1)  (formula II)

在哪里：

  • C 是二项式系数：C(n, k) = n! / (k! * (nk)!)
  • n 是可用项目的总数（在我们的例子中 n=B-1+K=12）
  • k是每个组合中的项目数（k=K=3）
  • p1, p2, ..., pk 是选择的项目（即我们的 3 元组的项目）

最后，将公式 I 代入公式 II，我们有：

I = C(n, k) - C(n-d1, k) - C(n-d2+1, k-1) - ... - C(n-dk+k-1, 1)

其中 d1, d2, ..., dk 是 N 的位数

注意：当N最高位B-1=9 时，该公式将包括 C(n, k) 其中 n < k，根据上面的定义，其中包括未定义的负数的阶乘。出于这个原因，我们必须用零替换这些项，因为在这种情况下，n 个元素的 k 组合集合是空的。

这是该问题的一般解决方案。

推荐阅读