使用顺序规则生成 N 个元素的所有可能序列

Question

我有一个函数get_appendable_values(sequence)，它接受一个序列（甚至是空的）并返回可附加到该序列（作为最后一个元素）的所有值的列表。我需要根据此函数中定义的规则并从空序列开始，生成 4 个元素的所有可能序列。

例子 ：

假设 的实现get_appendable_values是：

def get_appendable_values(sequence):
    '''Dummy rules'''
    if len(sequence) == 2:
        return [4, 12]
    if sequence[-1] == 4:
        return [7]
    return [0, 9]

预期输出：

[[0, 0, 4, 7],
[0, 0, 12, 0],
[0, 0, 12, 9],
[0, 9, 4, 7],
[0, 9, 12, 0],
[0, 9, 12, 9],
[9, 0, 4, 7],
[9, 0, 12, 0],
[9, 0, 12, 9],
[9, 9, 4, 7],
[9, 9, 12, 0],
[9, 9, 12, 9]]

我感觉递归是关键，但我无法弄清楚。

Answer 1

是的，递归是关键。要生成大小为 4 的序列，首先生成大小为 3 的所有序列，并向它们添加所有可能的结尾。同样，要生成大小为 3 的序列，您需要大小为 2 的所有序列...依此类推，直到大小为 0。

def get_appendable_values(sequence):
    '''Dummy rules'''
    if len(sequence) == 2:
        return [4, 12]
    #need a len check here to avoid IndexError when `sequence` is empty
    if len(sequence) > 0 and sequence[-1] == 4:
        return [7]
    return [0, 9]

def generate_sequences(size):
    if size == 0:
        yield []
    else:
        for left_part in generate_sequences(size-1):
            for right_part in get_appendable_values(left_part):
                yield left_part + [right_part]

for seq in generate_sequences(4):
    print(seq)

结果：

[0, 0, 4, 7]
[0, 0, 12, 0]
[0, 0, 12, 9]
[0, 9, 4, 7]
[0, 9, 12, 0]
[0, 9, 12, 9]
[9, 0, 4, 7]
[9, 0, 12, 0]
[9, 0, 12, 9]
[9, 9, 4, 7]
[9, 9, 12, 0]
[9, 9, 12, 9]