计算 python 中的子序列

Question

计数子序列

如果满足以下两个条件，则称一个数字序列是好的：

序列中的所有元素都是唯一的。
如果序列中的最小元素是a，序列中的最大元素是 b，那么 [a, b] 范围内的所有数字都出现在序列中。例如，(4, 2, 5, 1, 3) 是一个好的序列，而 (2, 2, 1) 或 (3, 7) 则不是。数组 arr 的子序列是可以通过删除一些元素或不删除元素而不改变剩余元素的顺序从数组 arr 派生的序列。

给定一个包含 n 个整数的数组，找出不同的好子序列的数量。如果两个子序列包含至少一个不同的索引，则它们被认为是不同的。例如，对于序列 (2, 2, 1)，由索引 1 和 2 形成的 (2, 1) 和由索引 0 和 2 形成的 (2, 1) 都被认为是不同的子序列。示例考虑数组 arr = [13, 11, 4, 12, 5, 4]。我们可以形成以下良好的子序列： • 长度为 1 的子序列：[13]、[11]、[4]、[12]、[5]、[4]、

• 长度为 2 的子序列：[13, 12]、[11, 12]、[4, 5]、[5, 4]

• 长度为 3 的子序列：[13, 11, 12] 因此，答案是 6+4 + 1 = 11。函数说明在下面的编辑器中完成函数countGoodSubsequences。 countGoodSubsequences 具有以下参数： int arr[n]：给定的整数数组 Returns long int: 可以从数组中导出的好子序列的数量，

这是我的代码：

import itertools
def is_good_sequence(array):
    minimum = min(array)
    maximum = max(array)
    good_sequence_list = list(range(minimum, maximum+1))
    checked = []
    if sorted(array) != good_sequence_list:
        return False

    for i in array:
        if i in checked:
            return False
        else:
            checked.append(i)

    return True


def countGoodSubsequences(arr):
    good_sequences = []
    for i in range(1, len(arr)+1):
        t = list(itertools.permutations(arr, i))
        for j in t:
            if is_good_sequence(j):
                good_sequences.append(j)
    return good_sequences

但是它不是 return 例外答案

Answer 1

为了解决您的问题，您可以使用 set 中的构建来获取唯一编号，并使用 sorted 中的构建来获取连续编号。

numbers =  [13, 11, 4, 12, 5, 4]

unique_numbers = sorted(set(numbers))
gaps = [
    i for i in range(1, len(unique_numbers)) 
    if unique_numbers[i] - unique_numbers[i-1] > 1
]

consecuteves = []
i0 = i1 = 0
for i1 in gaps:
    consecuteves.append(tuple(unique_numbers[i0:i1]))
    i0 = i1
consecuteves.append(tuple(unique_numbers[i1:len(unique_numbers)]))
consecuteves

从这一点开始，您可以使用递归函数将连续的数字分成更小的块。

可能的递归看起来像这样

def split(consecutive):
    result = []
    c1 = consecutive[:-1]
    c2 = consecutive[1:]
    if len(consecutive) > 1:
        result.extend([c1, c2])
    if len(consecutive) > 2:
        sub_1 = split(c1)
        sub_2 = split(c2)
        if sub_1:
            result.extend(sub_1)
        if sub_2:
            result.extend(sub_2)
    return result

所以你可以得到你的块如下：

result = set()
for consecutive in consecuteves:
    result.update(split(consecutive))
sorted(result, key=lambda s: (len(s), s))

但是要注意，如果只需要好序列的个数，就不需要像我上面那样创建了，直接计算连续数sub-sequences的个数就可以了。我把这个组合练习留给你。

因为我喜欢数学谜语，所以我得到了你的答案：

from collections import defaultdict

def frequency_count(sequence):
    frequency = defaultdict(int)
    for n in sequence:
        frequency[n] += 1
    return sorted(frequency.items())

def split(frequency):
    sequence = [n for n, m in frequency]
    gaps = [i for i in range(1, len(sequence)) if sequence[i] - sequence[i-1] > 1]
    i0 = i1 = 0
    for i1 in gaps:
        yield frequency[i0:i1]
    yield frequency[i1:len(frequency)]

def count_unique_consecutive(n):
    return n*(n+1)//2

def _count_subsets(frequency):
    for i, (n, m) in enumerate(frequency):
        if m > 1:
            f_new = frequency.copy()
            f_new[i] = (n, 1)
            n_single = _count_subsets(f_new)
            n_left = count_unique_consecutive(i)
            n_right = _count_subsets(frequency[i+1:])
            return m*n_single - (m-1)*n_left - (m-1)*n_right
    return count_unique_consecutive(len(frequency))

def count_subsets(sequence):
    frequency = frequency_count(sequence)
    consecutive = split(frequency)
    return sum(map(_count_subsets, consecutive))

count_subsets([1,2,2,2,3,8,9,10])

组合部分，计算连续序列中的子集，基本上是帕斯卡三角形的第二条对角线。我留给你去理解为什么。计算频率是使用默认字典完成的。为了处理多重性，您需要乘以出现多重值的可能子集的数量。这是通过将整个连续范围相乘并减去不与 multi-count 数字重叠的左右子集来完成的，因此它们只计数一次。

计算 python 中的子序列

Counting subsequences in python

python

arrays

sorting

counting

subsequence