鱼C论坛

 找回密码
 立即注册
查看: 1829|回复: 7

[已解决]序列拼接,递归的时候有问题

[复制链接]
发表于 2023-9-2 21:07:11 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
例如,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[n] + " " + 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)

测试用例如下:
>Rosalind_0498

AAATAAA

>Rosalind_2391

AAATTTT

>Rosalind_2323

TTTTCCC

>Rosalind_0442

AAATCCC

>Rosalind_5013

GGGTGGG

>Rosalind_123

AAAGAAA
最佳答案
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[n] + " " + 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)
通过这样的修改,递归函数会在遇到重复序列时停止拼接,并返回最终的结果。

希望这可以帮助到你!如果还有其他问题,请随时提问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-9-2 21:07:28 | 显示全部楼层
根据你提供的代码,我注意到在递归函数getoriginal中,你将最初的序列存储在了字典dic中,并在每次拼接后更新了seqillu。然而,你没有在递归调用时传递更新后的seqillu,导致在递归过程中使用的仍然是原始的seqillu,而不是拼接后的结果。

为了解决这个问题,你可以将递归调用的返回值赋值给seqillu,以便在下一次递归中使用更新后的结果。修改后的代码如下所示:
# 拼接函数
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[n] + " " + 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)

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

希望这可以帮助到你!如果还有其他问题,请随时提问。
如果问题已经解决,请设置最佳答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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[n] + " " + 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 ,可以保留之前拼接的结果。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-9-2 21:08:50 | 显示全部楼层
不递归结果没问题,加上递归是死循环
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

好的谢谢,这样还是死循环,原因是测试用例本身会造成死循环,拼接之后还是会一直循环是的把
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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[n] + " " + 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)
通过这样的修改,递归函数会在遇到重复序列时停止拼接,并返回最终的结果。

希望这可以帮助到你!如果还有其他问题,请随时提问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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[i]        last_str = str_list[i+1]                # 检查首尾k个字符是否相同        if first_str[-k:] == last_str[:k]:            new_list.append(first_str + last_str[k:])            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回答,如果胡说八道,请不要理会
如果对你有帮助,请设置一个最佳答案!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-9-10 17:23:02 | 显示全部楼层
陶远航 发表于 2023-9-2 21:37
你的问题是关于序列拼接的递归函数,你想知道为什么测试用例会造成死循环。

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

感谢感谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 21:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表