Python列表切片生成DNA多空位变体的嵌套列表处理问题

• 目前已掌握Python基础语法，近期课程学习内容覆盖列表操作、字符串处理、列表切片相关知识点。
• 课程习题要求仅使用列表切片实现功能，不得调用特殊内置函数：编写名为generate_n_gaps的函数，接收三个参数：由A/T/C/G四种字符任意组合构成的任意长度dna字符串、空位标识GAP='_'、整数参数n，返回插入最多n个额外空位的所有无重复dna变体组成的列表。

题目给出的示例输入输出如下：

In [1]: generate_n_gaps( 'T', 2 )
Out[1]: ['T', '_T', 'T_', '__T', '_T_', 'T__']

In [2]: generate_n_gaps( 'CA', 2 )
Out[2]: ['CA', '_CA', 'C_A', 'CA_', '__CA', '_C_A', '_CA_', 'C__A', 'C_A_', 'CA__']

In [3]: generate_n_gaps( 'C_A', 2)
Out[3]: ['C_A', '_C_A', 'C__A', 'C_A_', '__C_A', '_C__A', '_C_A_', 'C___A', 'C__A_', 'C_A__']

函数定义要求如下：

def generate_n_gaps( dna, n = 1 ):

目前已经完成单空位插入的辅助函数generate_gaps，通过迭代调用辅助函数的方式生成多空位插入结果，已编写代码如下：

def generate_n_gaps( dna, n = 1 ):
    last=generate_gaps(dna) 
    a=len(last)
    for i in range(a):
        b=generate_gaps(last[i])
        last.append(b)
    return last


def generate_gaps( dna ):
    comb=[]
    for i in range(0 , len(dna)+1):
        partial=''
        partial=dna[:i]+GAP+dna[i:]
        comb.append(partial)
    last=[]
    for i in comb:
        if i not in last:
            last.append(i)    
    return last

现有代码可以生成符合要求的变体内容，但返回列表结构混乱，存在嵌套子列表问题，例如调用generate_n_gaps('T', 2)时返回结果为：

In [1]: generate_n_gaps( 'T', 2 )
Out[1]: ['_T', 'T_', ['__T', '_T_'], ['_T_', 'T__']]

需要解决的问题：合并所有嵌套子列表、移除主列表内的嵌套列表结构，结构整理完成后可自行处理结果去重。

问题根源 #

出现嵌套列表的核心原因是使用list.append()添加子结果：append会将传入的参数作为单个整体元素存入列表，如果传入值是列表，就会直接形成嵌套结构。

修正方案 #

1. 替换添加方法：追加批量生成的序列时，用list.extend()替代append，extend会遍历传入的可迭代对象，将其中的元素逐个追加到主列表，从根源避免嵌套产生。
2. 调整迭代逻辑：原代码只遍历了第一次生成的单空位结果，没有覆盖多轮插入的场景，且初始结果缺失原始dna序列（插入0个空位的情况），需要调整为逐轮迭代的结构：每一轮基于上一轮生成的k空位序列，生成k+1空位的新序列，逐轮去重后加入总结果集。

修正后的完整可运行代码如下：

GAP = '_'

def generate_gaps(dna):
    comb = []
    for i in range(len(dna) + 1):
        # 仅用切片实现空位插入
        partial = dna[:i] + GAP + dna[i:]
        comb.append(partial)
    # 单轮插入结果去重
    single_gap_res = []
    for s in comb:
        if s not in single_gap_res:
            single_gap_res.append(s)
    return single_gap_res

def generate_n_gaps(dna, n=1):
    # 初始结果包含原始序列，对应插入0个空位的情况
    final_res = [dna]
    current_level = [dna]
    for _ in range(n):
        next_level = []
        for seq in current_level:
            # 用extend逐元素追加，不会产生嵌套
            next_level.extend(generate_gaps(seq))
        # 本轮结果去重后加入总结果
        for s in next_level:
            if s not in final_res:
                final_res.append(s)
        # 下一轮基于本轮生成的序列继续插入空位
        current_level = next_level
    return final_res

上述代码运行后返回结果和题目给出的示例完全一致，无嵌套结构，全程仅使用列表切片实现字符串拼接，没有调用特殊内置函数，符合题目要求。

内容的提问来源于stack exchange，提问作者Nicholas Boscolo