为所有非递减序列列表开发索引方案

Question

假设我们考虑一个已排序的列表，其中包含所有值在范围 (1, max_num) 内且每个序列有 num_slots 个元素的非递减序列。如何以 O(1) 的时间复杂度找到某个给定成员序列的索引？我实际上并没有提前获得整个列表，我只是想找到所有序列存在的列表中某个成员序列的索引。

以具体例子说明，假设 max_num = 3，num_slots = 4。那么有15个序列（或通常情况下，有 (max_num + num_slots - 1) choose (num_slots) 个序列）：

[[1, 1, 1, 1],
 [1, 1, 1, 2],
 [1, 1, 1, 3],
 [1, 1, 2, 2],
 [1, 1, 2, 3],
 [1, 1, 3, 3],
 [1, 2, 2, 2],
 [1, 2, 2, 3],
 [1, 2, 3, 3],
 [1, 3, 3, 3],
 [2, 2, 2, 2],
 [2, 2, 2, 3],
 [2, 2, 3, 3],
 [2, 3, 3, 3],
 [3, 3, 3, 3]]

所以，如果给定一个类似于[1, 2, 2, 3]的序列和信息max_num = 3，我正在尝试编写一个函数，返回其正确的索引7。我实际上没有所有序列的列表可供使用。

背景信息：

我已经想出了一种算法来生成我关心的所有非递减序列，但是在没有整个序列列表的情况下生成特定成员序列的索引似乎与此不完全相关。

def gen(max_num, num_slots, l = None): 
    if l is None: 
        l = [[1] * num_slots] 
    cur = l[-1].copy() 
    for i in reversed(range(num_slots)): 
        if cur[i] < max_num: 
            cur[i] += 1 
            for j in range(i+1, num_slots): 
                cur[j] = cur[i] 
            l.append(cur) 
            return gen(max_num, num_slots, l) 
    return l

- Eric Hansen

---

你可以直接执行 seq_index = sequences.index(sequence)。 - postoronnim

@postoronnim 抱歉，我应该明确我想要一个 O(1) 的解决方案。 - Eric Hansen

你不需要生成这个序列，这是一个纯数学问题，很可能可以用递归来解决：如果你查看所有以2或更大数字开头的4元素列表，你会发现它们都是相同的，其中所有元素都是4元素列表中的最大值为2（当你将所有数字减1时）。 - Rocky Li

@RockyLi，抱歉我不是很明白。我同意序列生成并不必要，只是提到它似乎有些相关。 - Eric Hansen

给定一个已排序的列表... - 你是实际上得到了那个列表，还是只是应该找到如果构建了那个列表，特定元素将具有的索引？在几乎任何情况下，这样的列表都是巨大的内存浪费。即使您想要遍历所有这些序列（通常是不好的想法），也没有理由事先实现一个列表。 - user2357112

@user2357112 对不起，我的问题表述得很糟糕，让我来修正一下 - 我没有提前准备好列表，也不是必须的。 - Eric Hansen

Answer 1

这个算法的时间复杂度为O(|seq| + max_num)。需要注意的是，这个算法仍比朴素的生成所有序列并搜索的方法快得多，后者在|seq|方面呈指数级增长。

其思路是先统计输入序列之前有多少个符合条件的序列。例如，当最大数为6时，你想知道[2, 4, 5, 6]的索引是多少。

• 统计 [1, *, *, *]
• 统计 [2, 2, *, *]
• 统计 [2, 3, *, *]
• (注意：不能统计 [2, 4, *, *]，因为这样会包括在输入之后的 [2, 4, 6, 6]。在给定索引处，应该一直计数到输入的前一个数字)
• 统计 [2, 4, 4, *]
• 统计 [2, 4, 5, 5]

(对于每一行，你可以使用公式(max_num + num_slots - 1) choose (num_slots)，并将它们相加)

def combinations(slots, available):
    return choose(slots + available - 1, slots)

def find_index(seq, max_num):
    res = 0
    for digit_index in xrange(len(seq)):
        prev = seq[digit_index - 1] if digit_index > 0 else 1
        for digit in xrange(prev, seq[digit_index]):
            res += combinations(len(seq) - digit_index - 1, max_num - digit + 1)
    return res


print find_index([1, 2, 2, 3], 3)

- David Frank

---

这是一个聪明的解决方案，但我认为你的 O 不正确。你不能在 O(1) 中计算 choose。我怀疑它应该是类似于 O(max_num*(|seq|+max_num)) 的东西。考虑找到像 [1, 1000, 2000] 和 [1,2,3, ..., 1000] 这样的东西的位置。另一方面，OP 要求的 O(1) 显然是不可能的，因为读取整个 seq 需要 O(|seq|) 的时间。 - SergGr

Answer 2

我会详细阐述@DavidFrank的答案，解释为什么时间复杂度是O(length+max_num)，并举一个更易理解但稍微复杂一些的例子。

首先，我们观察以下事实：

假设在F(length, max_num)中，总共有X种可能性。

对于所有以1开头的可能性，例如[1, ....]，我们在这个组中有F(length-1, max_num)次计数。

对于所有不以1开头的可能性，例如[2, ....]或[3, ....]，我们有F(length, max_num-1)次计数。

因此，我们可以使用递归来得到O(length*max_num)（如果使用记忆化，则可以变为O(length+max_num)）的时间复杂度。

# This calculate the total number of X of possible entry given (length, max_num)
def calc_sum(length, max_num):
    if max_num == 1:
        return 1
    elif length == 1:
        return max_num
    else:
        total = calc_sum(length-1, max_num) + calc_sum(length, max_num-1)
        return total

现在我们检查结果，看看是否可以将其转换为O(1)：

# This is clearly not going to make it O(1), so now we need some generalizations to NOT run this recursion.
import numpy as np
arr = np.zeros((6,6))
for i in range(6):
    for j in range(6):
        arr[i, j] = calc_sum(i+1, j+1)
print(arr)

结果是：

这里填写结果

[[  1.   2.   3.   4.   5.   6.]
 [  1.   3.   6.  10.  15.  21.]
 [  1.   4.  10.  20.  35.  56.]
 [  1.   5.  15.  35.  70. 126.]
 [  1.   6.  21.  56. 126. 252.]
 [  1.   7.  28.  84. 210. 462.]]

这是一个帕斯卡三角形，如果你向右上方对角线看。帕斯卡三角形的对角线由(x choose y)定义。

这表明它不可能是O(1)，至少会是O(length+max_num)，因为这是(Choose)函数的一般复杂度。

我们已经证明了除非我们将(length + max_num)限制为常数，否则不可能有O(1)的解决方案。

# We can expand by solving it now:
from scipy.special import comb # this is choose function.

def get_index(my_list, max_num):
    my_list = np.array(my_list)
    if len(my_list) == 1:
        return my_list[0] - 1
    elif my_list[0] == 1:
        return get_index(my_list[1:], max_num)
    elif my_list[0] != 1:
        return get_index(my_list - 1, max_num - 1) + comb(len(my_list)-2+max_num, max_num-1)

get_index([1,2,2,3],3) # 7

使用comb()函数后的最终函数的聚合复杂度仍为O(length + max_num)，因为comb之外的所有内容的复杂度也是O(length + max_num)。

- Rocky Li

Answer 3

从具有重复的{1...n}的k-子集到不重复的{1...n + k − 1}的k-子集存在双射，方法是将{c_0, c_1...c_(k−1)}映射到{c_0, c_(1+1), c_(2+2)...c_(k−1+k−1)}（参见这里）。

转换后，只需使用您喜欢的组合排名实用程序即可。

[3, 3, 3, 3]  -->  [3, 4, 5, 6]
[2, 3, 3, 3]  -->  [2, 4, 5, 6]
[2, 2, 3, 3]  -->  [2, 3, 5, 6]
[2, 2, 2, 3]  -->  [2, 3, 4, 6]
[2, 2, 2, 2]  -->  [2, 3, 4, 5]
[1, 3, 3, 3]  -->  [1, 4, 5, 6]
[1, 2, 3, 3]  -->  [1, 3, 5, 6]
[1, 2, 2, 3]  -->  [1, 3, 4, 6]
[1, 2, 2, 2]  -->  [1, 3, 4, 5]
[1, 1, 3, 3]  -->  [1, 2, 5, 6]
[1, 1, 2, 3]  -->  [1, 2, 4, 6]
[1, 1, 2, 2]  -->  [1, 2, 4, 5]
[1, 1, 1, 3]  -->  [1, 2, 3, 6]
[1, 1, 1, 2]  -->  [1, 2, 3, 5]
[1, 1, 1, 1]  -->  [1, 2, 3, 4]

import pyncomb

def convert(m, S):
  return (m + len(S) - 1, [ x-1 + i for x,i in zip(S, list(xrange(len(S)))) ])

def rank(m, S):
  k, s = convert(m, S)
  return pyncomb.ksubsetcolex.rank(k, s)

print rank(3, [1,2,2,3])
# 7

- גלעד ברקן

Answer 4

对于每个数字，找到它与最小数字之间的差。对于任何更改的数字右侧的每个更改位置，加1。

idx = 0;
for i in range(0,num_slots):
    d = SEQ[i]
    idx += d-min_num
    if (d > min_num):
        idx += num_slots-1 - i

例如：
[1,1,1,3] 是 0 + 0 + 0 + (2+0) 或者 2
[1,2,3,3] 是 0 + (1+2) + (2+1) + (2+0) 或者 8
[3,3,3,3] 是 (2+3) + (2+2) + (2+1) + (2+0) 或者 14

- AShelly

---

这是O(num_slots)。 - AShelly

这看起来很有前途！它似乎适用于 4 个插槽和 3 作为最大数字的情况。然而，对于许多其他情况，例如最大数字为 2 而不是 3，它似乎不起作用（除非我没有正确编码）。 - Eric Hansen

与max_num和num_slots有关的任何限制吗？如果不添加位置奖励，最大2/插槽4可以正常工作。但是，如果max更大，则会在位置上变得非线性。 - AShelly