论坛 › Python交流 › 序列拼接，递归的时候有问题

15588686105 发表于 2023-9-2 21:07:11

序列拼接，递归的时候有问题

例如，AAATAAA和CCCGAAA，k=3，分别首尾3个字符一样，则拼接之后为CCCGAAATAAA
想实现递归功能，当拼接一次后发现拼接后的结果仍可再次拼接则再拼一次
# 读文件的函数
def readfasta(lines):
    illustrate = []
    seq = []
    string = ""
    num = 0
    for i in lines:
      # 判断是否为说明行
      if '>' in i or ';' in i:
            newi = i.replace('>','').replace(';','').replace('\n','')
            illustrate.append(newi)
            if num != 0:
                seq.append(string)
                string = ""
      else:
            news = i.replace('\n','')
            string += news
      num += 1
      if num == len(lines):
            seq.append(string)
    return illustrate,seq

f = open('12fasta.txt', 'r')

lines = f.readlines()

f.close()

(i, s) = readfasta(lines)
print(i,s)

k = int(input("输入K值："))

dic = {}
# 拼接函数
def getoriginal(seq,illu,k):
    x = 0
    for n,m in enumerate(seq):
      temp = m[-k:]
      for i,j in enumerate(seq):
            if i != n:
                if temp == j[:k]:
                  name = illu + " " + illu
                  newstr = m[:-k] + j
                  dic.update({name:newstr})
                  x += 1
    seq = list(dic.values())
    illu = list(dic.keys())
    print(seq,illu)
    if len(illu) == 1 or x == 0:
      return dic
    else:
      return getoriginal(seq,illu,k)


res = getoriginal(s,i,k)
print("\n",res)


测试用例如下：
>Rosalind_0498

AAATAAA

>Rosalind_2391

AAATTTT

>Rosalind_2323

TTTTCCC

>Rosalind_0442

AAATCCC

>Rosalind_5013

GGGTGGG

>Rosalind_123

AAAGAAA

陶远航 发表于 2023-9-2 21:07:28

根据你提供的代码，我注意到在递归函数getoriginal中，你将最初的序列存储在了字典dic中，并在每次拼接后更新了seq和illu。然而，你没有在递归调用时传递更新后的seq和illu，导致在递归过程中使用的仍然是原始的seq和illu，而不是拼接后的结果。

为了解决这个问题，你可以将递归调用的返回值赋值给seq和illu，以便在下一次递归中使用更新后的结果。修改后的代码如下所示：

# 拼接函数
def getoriginal(seq, illu, k):
    x = 0
    dic = {}

    for n, m in enumerate(seq):
      temp = m[-k:]
      for i, j in enumerate(seq):
            if i != n:
                if temp == j[:k]:
                  name = illu + " " + illu[ i]
                  newstr = m[:-k] + j
                  dic.update({name: newstr})
                  x += 1

    seq = list(dic.values())
    illu = list(dic.keys())
    print(seq, illu)

    if len(illu) == 1 or x == 0:
      return dic
    else:
      return getoriginal(seq, illu, k)

res = getoriginal(s, i, k)
print("\n", res)


通过这样的修改，递归函数会正确使用更新后的seq和illu进行下一次递归调用，直到满足退出条件。

希望这可以帮助到你！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

isdkz 发表于 2023-9-2 21:07:36

问题出在递归函数中，每次递归都会重新定义一个空的字典 dic ，导致之前拼接的结果丢失。解决方法是将字典 dic 作为参数传入递归函数中，并在每次递归时更新字典的值。以下是修改后的代码：

def getoriginal(seq, illu, k, dic):
    x = 0
    for n, m in enumerate(seq):
      temp = m[-k:]
      for i, j in enumerate(seq):
            if i != n:
                if temp == j[:k]:
                  name = illu + " " + illu[ i]
                  newstr = m[:-k] + j
                  dic.update({name: newstr})
                  x += 1
    seq = list(dic.values())
    illu = list(dic.keys())
    print(seq, illu)
    if len(illu) == 1 or x == 0:
      return dic
    else:
      return getoriginal(seq, illu, k, dic)


res = getoriginal(s, i, k, {})
print("\n", res)


这样修改后，每次递归时都使用同一个字典 dic ，可以保留之前拼接的结果。

15588686105 发表于 2023-9-2 21:08:50

不递归结果没问题，加上递归是死循环

15588686105 发表于 2023-9-2 21:34:18

陶远航 发表于 2023-9-2 21:07
根据你提供的代码，我注意到在递归函数getoriginal中，你将最初的序列存储在了字典dic中，并在每次拼接后更 ...

好的谢谢，这样还是死循环，原因是测试用例本身会造成死循环，拼接之后还是会一直循环是的把

陶远航 发表于 2023-9-2 21:37:40

15588686105 发表于 2023-9-2 21:34
好的谢谢，这样还是死循环，原因是测试用例本身会造成死循环，拼接之后还是会一直循环是的把

你的问题是关于序列拼接的递归函数，你想知道为什么测试用例会造成死循环。

根据你提供的测试用例，我发现其中有两个序列是相同的，即AAATAAA和AAAGAAA。这意味着无论你如何拼接它们，都会得到相同的结果，即AAATAAA或AAAGAAA。因此，递归函数会一直尝试拼接这两个序列，但永远无法达到退出条件，从而导致死循环。

为了避免这种情况，你可以在递归函数中添加一个判断条件，检查是否有重复的序列出现在seq中。如果有，就跳过拼接操作，直接返回dic。修改后的代码如下所示：

# 拼接函数
def getoriginal(seq, illu, k):
    x = 0
    dic = {}

    # 检查是否有重复的序列
    if len(seq) != len(set(seq)):
      return dic

    for n, m in enumerate(seq):
      temp = m[-k:]
      for i, j in enumerate(seq):
            if i != n:
                if temp == j[:k]:
                  name = illu + " " + illu[ i]
                  newstr = m[:-k] + j
                  dic.update({name: newstr})
                  x += 1

    seq = list(dic.values())
    illu = list(dic.keys())
    print(seq, illu)

    if len(illu) == 1 or x == 0:
      return dic
    else:
      return getoriginal(seq, illu, k)

res = getoriginal(s, i, k)
print("\n", res)

通过这样的修改，递归函数会在遇到重复序列时停止拼接，并返回最终的结果。

希望这可以帮助到你！如果还有其他问题，请随时提问。

琅琊王朝 发表于 2023-9-3 17:11:44

要实现递归功能以拼接字符串，您可以使用以下Python代码：

def recursive_splice(str_list, k):
    # 创建一个空列表，用于存储拼接后的字符串
    new_list = []
    flag = False# 判断是否发生了拼接
   
    # 遍历列表中的字符串对
    for i in range(len(str_list) - 1):
      # 提取首尾两个字符串
      first_str = str_list
      last_str = str_list
      
      # 检查首尾k个字符是否相同
      if first_str[-k:] == last_str[:k]:
            new_list.append(first_str + last_str)
            flag = True# 发生了拼接
      else:
            new_list.append(first_str)
   
    # 将最后一个字符串添加到列表中
    new_list.append(str_list[-1])
   
    # 如果发生了拼接，则递归调用函数
    if flag:
      return recursive_splice(new_list, k)
    else:
      return new_list

# 测试用例
test_cases = ["AAATAAA", "CCCGAAA"]

# 调用递归拼接函数
result = recursive_splice(test_cases, 3)

# 输出结果
print(''.join(result))


这段代码定义了一个名为`recursive_splice`的递归函数。它接受一个字符串列表和整数`k`作为输入参数。函数首先创建一个空列表`new_list`来存储拼接后的字符串。然后，它遍历字符串列表中的字符串对，并检查首尾`k`个字符是否相同。如果相同，则将拼接后的字符串添加到`new_list`中，并设置`flag`为`True`。最后，它将最后一个字符串添加到`new_list`中。如果发生了拼接（`flag`为`True`），则递归调用`recursive_splice`函数来继续拼接。否则，返回`new_list`作为结果。

在测试用例中，我们将输入字符串作为列表传递给`recursive_splice`函数，并指定`k=3`。最后，我们使用`''.join(result)`将结果列表转换为字符串，并打印输出。

希望这可以帮助您解决问题！如果您有任何其他问题，请随时提问。
此内容为ChatGPT回答，如果胡说八道，请不要理会
如果对你有帮助，请设置一个最佳答案！

15588686105 发表于 2023-9-10 17:23:02

陶远航 发表于 2023-9-2 21:37
你的问题是关于序列拼接的递归函数，你想知道为什么测试用例会造成死循环。

根据你提供的测试用例，我 ...

感谢感谢

查看完整版本: 序列拼接，递归的时候有问题