时间戳

首页 > 解决方案 > 如何使用递归找到列表的增加子序列？

python - 如何使用递归找到列表的增加子序列？

问题描述

给定一个列表，我想编写一个函数来返回列表中所有递增的子序列。顺序无关紧要。

例如 inc_subseqs([1, 3, 2]) -> [[], [1], [1, 2], [1, 3], [2], [3]]

我找到了一种方法：

def insert_into_all(item, nested_list):
    """Assuming that nested_list is a list of lists, return a new list
    consisting of all the lists in nested_list, but with item added to
    the front of each.

    >>> nl = [[], [1, 2], [3]]
    >>> insert_into_all(0, nl)
    [[0], [0, 1, 2], [0, 3]]
    """
    return [[item] + el for el in nested_list]

def inc_subseqs(s):
    """Assuming that S is a list, return a nested list of all subsequences
    of S (a list of lists) for which the elements of the subsequence
    are strictly nondecreasing. The subsequences can appear in any order.

    >>> seqs = inc_subseqs([1, 3, 2])
    >>> sorted(seqs)
    [[], [1], [1, 2], [1, 3], [2], [3]]
    >>> inc_subseqs([])
    [[]]
    >>> seqs2 = inc_subseqs([1, 1, 2])
    >>> sorted(seqs2)
    [[], [1], [1], [1, 1], [1, 1, 2], [1, 2], [1, 2], [2]]
    """
    def subseq_helper(s, prev):
        if not s:
            return [[]]
        elif s[0] < prev:
            return subseq_helper(s[1:], prev)
        else:
            a = subseq_helper(s[1:], s[0])  # with first
            b = subseq_helper(s[1:], prev)  # without first
            return insert_into_all(s[0], a) + b
    return subseq_helper(s, 0)

但是，我不知道 else 部分的subseq_helper工作原理和算法的一般流程？

标签： pythonlist

解决方案

else 部分的工作原理如下：

假设初始序列，s = s[0] s[1] s[2] s[3] ... s[n]。可以从任意数量的 s[i] 的顺序组合创建 seq 的子序列，这些组合可以从 s[0] s[1] s[2] s[3] ... s[n] 中挑选，
例如 s [0] s[1], s[0] s[1] s[4], s[0] s[7], s[1] s[2] s[6], s[2] s[3 ] s[5] 等。所有这些子序列的集合可以按照我们的意图被分成两部分（或两个子集）：一个子集 A 具有所有以 s[0] 开头的子序列（在其他单词，包括 s[0])，以及不以 s[0] 开头的剩余子集 B（没有 s[0]，只需在剩余的 s[1:] 中选择）。

回到问题，选择具有非递减约束的 s 的所有子序列。在子集A中，每个子序列都以 s[0] 开头，并且 s[1:] 的其余子序列不得有任何小于 s[0] 的成员（非递减）。这导致 a = subseq_helper(s[1:], s[0])。为了让它们以 s[0] 开头，我们应用函数 insert_into_all，所以现在我们得到A。不包括 s[0] 的另一组子序列，即子集B不需要与 s[0] 进行比较，因为 s[0] 被排除在外，但必须与 prev 进行比较才能不减少. 这就是为什么 b = subseq_helper(s[1:], prev) ，我们有B，即 = b 。因此，else 部分返回 A + B 即 insert_to_all(s[0],a) + b

elif 部分：给定一个特定数字 prev，我们想要找到（或创建）s[0] s[1] ... s[n] 的子序列，条件是 s[0] 不能小于 prev（我们希望它不从上一个减少）。如果 s[0] 小于 prev，我们跳过 s[0]，并使用 s[1:]（剩余的）。因此，返回 subseq_helper(s[1:], prev)。

推荐阅读