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

问题描述

假设我们正在考虑所有非递减序列的排序列表，其值在范围内(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

标签： pythonpython-3.xalgorithmmath

这个是O(|seq| + max_num)。请注意，这仍然比简单的 generate all 和 search 方法快得多，后者在|seq|.

这个想法是你在输入序列之前计算序列。例如，您想知道 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)

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

问题描述

解决方案

推荐阅读