假设我们正在考虑所有非递减序列与范围(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号I实际上并不拥有所有序列的列表一起工作的功能。
背景资料
我想出了一个算法来生成我关心所有非递减序列，但是这似乎并没有产生特定成员序列的指数没有序列的整个列表物化完全相关。
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
我会阐述@ 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），因为这是（选择）函数的一般的复杂性。
我们千里迢迢来证明一个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）为好。
这一个是O(|seq| + max_num)。请注意，这仍然比幼稚快得多生成所有和搜索方法，这是在|seq|指数。
这个想法是，你算输入序列之前的序列。例如，你想知道什么是[2，4，5，6]当MAX_NUM = 6的索引。
（对于每一行，您可以使用公式，(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)
存在从{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)}（见here）。
一旦转换，只需使用你最喜欢的组合排名效用。
[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