假设我们考虑一个已排序的列表,其中包含所有值在范围
以具体例子说明,假设
所以,如果给定一个类似于
背景信息:
我已经想出了一种算法来生成我关心的所有非递减序列,但是在没有整个序列列表的情况下生成特定成员序列的索引似乎与此不完全相关。
(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
O(1)
的解决方案。 - Eric Hansen