假设我们正在考虑每个序列中值在(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(|seq| + max_num)。注意，这仍然比在|seq|中为指数级的naive generate all and search方法快得多。
其思想是在输入序列之前对序列进行计数。例如你想知道当max_num＝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)
我将详细阐述@DavidFrank关于为什么它是O(长度+max_num)的答案，并给出一个更容易理解的例子(也有点复杂)。
首先，观察：
假设F(长度，max_num)中的总级数可能性=X
然后，对于X中以1开头的所有可能性，例如[1，….]，我们在该组中有一个F(长度-1，max_num)的计数。
对于X中所有不以1开头的可能性，例如[2，….]或[3，….]，我们有一个F(长度，max_num-1)的计数。
因此，我们可以使用递归来获得O(长度*max_num)(如果我们使用记忆化，可以变成O(长度+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选择y)定义
这清楚地表明，它不可能是O(1)，至少会是O(长度+max_num)，因为这是(Choose)函数的一般复杂性。
我们一直在证明O(1)解是不可能的，除非我们将(长度+max_num)约束为常数。
# 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(长度+max_num)，因为comb之外的所有函数的复杂度也是O(长度+max_num。
通过将{c_0, c_1...c_(k−1)}映射到{c_0, c_(1+1), c_(2+2)...c_(k−1+k−1)}，存在从{1...n}(有重复)的k个子集到{1...n + 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
对于每个数字，找出该数字与最低数字之间的差值。在任何更改的数字右侧，每个更改的位置加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