algorithm - 没有重复的子序列数

Question

我有一个特定长度的数组(比如 8)1,2,2,3,3,4,5,6

我希望找到这个长度数组的子序列数(比如 4)。这是 8 选择 4 (8C4) = 70。

但是，在上面的 70 个子序列列表中，我不想计算具有重复元素的序列，例如1223 1224 1334 2233 应该删除。

我有一个单一元素被复制的解决方案(即数组是 1,2,2,3,4,5,6,7)这里的重复项是 2C2*6C2 = 15，要求的答案是 55

是否有适用于中等大数组大小和 len(最大十万)的通用公式/算法。对于一般情况，答案以模格式计算。

Answer 1

这是一个简单的动态规划问题。

保留当前数量的 ways 数组，以当前选择子序列中的 i 元素。遍历值和计数，如果 c 是特定值有多少的计数，则以 i 结束的方式的数量是方式在没有此值的情况下执行此操作，加上完成 i-1 的方法已经乘以选择此值的方法数。

这是有效的 Python 代码:

def count_distinct_subseq (seq, k, modulo=None):
    count = {}
    for s in seq:
        if s in count:
            count[s] = count[s] + 1
        else:
            count[s] = 1

    # # of ways to currently have i chosen.
    ways = [0 for i in range(k+1)]
    ways[0] = 1

    for s, c in count.iteritems():
        for i in range(k, 0, -1):
            ways[i] = ways[i] + ways[i-1] * c
            if modulo is not None:
                ways[i] = ways[i] % modulo

    return ways[k]

print(count_distinct_subseq([1, 2, 2, 3, 4, 5, 6, 7], 4))

传递第三个参数以对较小的参数取模进行计算。