Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Помоги составить алгоритм восстановления максимально похожей строки(с инделями) в моем…

  1. User

    Помоги составить алгоритм восстановления максимально похожей строки(с инделями) в моем случае, : def my_max(arr): rule=["ccc","c--","-c-","--c","cc-","c-c","-cc"] c_r=rule[0] m=arr[0] for i,e in enumerate(arr): if e>m: m=e c_r=rule[i] return m,c_r

    def LCSbackTrack(v,w,z): s=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] b_t=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] for i in range(1,len(v)+1): for j in range(1,len(w)+1): for k in range(1,(len(z)+1)): ma=0 if v[i-1]==w[j-1] and w[j-1]==z[k-1]: ma=1 s[i][j][k],b_t[i][j][k]=my_max([ s[i-1][j-1][k-1]+ma, s[i-1][j][k], s[i][j-1][k], s[i][j][k-1], s[i-1][j-1][k], s[i-1][j][k-1], s[i][j-1][k-1] ]) return s[i][j][k], b_t

    def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]): if i==0 or j==0 or k==0: return res if b_t[i][j][k]=="ccc": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+=z[k-1] outputLCS(b_t,v,w,z,i-1,j-1,k-1,res) elif b_t[i][j][k]=="c--": res[0]+=v[i-1] res[1]+='-' res[2]+='-' outputLCS(b_t,v,w,z,i-1,j,k,res) elif b_t[i][j][k]=="-c-": res[0]+='-' res[1]+=w[j-1] res[2]+='-' outputLCS(b_t,v,w,z,i,j-1,k,res) elif b_t[i][j][k]=="--c": res[0]+='-' res[1]+='-' res[2]+=z[k-1] outputLCS(b_t,v,w,z,i,j,k-1,res) elif b_t[i][j][k]=="cc-": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+='-' outputLCS(b_t,v,w,z,i-1,j-1,k,res) elif b_t[i][j][k]=="c-c": res[0]+=v[i-1] res[1]+='-' res[2]+=z[k-1] outputLCS(b_t,v,w,z,i-1,j,k-1,res) elif b_t[i][j][k]=="-cc": res[0]+='-' res[1]+=w[j-1] res[2]+=z[k-1] outputLCS(b_t,v,w,z,i,j-1,k-1,res)

    s1="ATATCCG" s2="TCCGA" s3="ATGTACTG" res=LCSbackTrack(s1,s2,s3) r=outputLCS(res[1],s1,s2,s3,len(s1),len(s2),len(s3)) print(r)

  2. Assistant

    Алгоритм восстановления максимально похожей строки с инделами в данном случае выглядит следующим образом:

    1. Определение функции my_max(arr), которая принимает на вход массив arr и возвращает максимальное значение элемента и соответствующее правило из заданного набора правил rule. В данном случае используется правило "ccc" для первого элемента массива arr.

    2. Определение функции LCSbackTrack(v, w, z), которая принимает на вход три последовательности v, w, z и возвращает матрицу s и матрицу b_t. Матрица s хранит значения максимальной похожести строки между всеми возможными подстроками последовательностей v, w и z. Матрица b_t хранит информацию о том, каким правилом было получено максимальное значение в матрице s.

    3. Внутри функции LCSbackTrack используется вложенный цикл для перебора всех возможных комбинаций элементов из последовательностей v, w и z. Для каждой комбинации вычисляется значение ma, равное 1, если все элементы равны между собой, иначе ma равно 0. Затем с помощью функции my_max выбирается максимальное значение из следующих вариантов:

    • значение в матрице s с индексами (i-1, j-1, k-1) и прибавленное значение ma
    • значение в матрице s с индексами (i-1, j, k)
    • значение в матрице s с индексами (i, j-1, k)
    • значение в матрице s с индексами (i, j, k-1)
    • значение в матрице s с индексами (i-1, j-1, k)
    • значение в матрице s с индексами (i-1, j, k-1)
    • значение в матрице s с индексами (i, j-1, k-1)
    1. Функция LCSbackTrack возвращает значение s[i][j][k] и матрицу b_t.

    2. Определение функции outputLCS(b_t, v, w, z, i, j, k, res=["","",""]), которая принимает на вход матрицу b_t, последовательности v, w, z и текущие индексы i, j, k, а также список res, содержащий текущее состояние восстановленной максимально похожей строки. Функция рекурсивно вызывает саму себя, пока не достигнет одного из базовых случаев: i=0, j=0 или k=0. В каждом рекурсивном вызове функция проверяет значение b_t[i][j][k] и соответствующим образом обновляет элементы списка res.

    3. Функция outputLCS возвращает список res.

    4. Исходные строки s1, s2 и s3 задаются значениями "ATATCCG", "TCCGA" и "ATGTACTG" соответственно.

    5. Вызывается функция LCSbackTrack с аргументами s1, s2 и s3. Результат сохраняется в переменной res.

    6. Вызывается функция outputLCS с аргументами res[1], s1, s2, s3, len(s1), len(s2), len(s3) и пустым списком res.

    7. Результат выводится на экран с помощью функции print().

  3. User

    почини мне функцию outputLCS

  4. Assistant

    Исправленный код функции outputLCS:

    def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]):
        if i==0 or j==0 or k==0:
            return res
        if b_t[i][j][k]=="ccc":
            res[0]+=v[i-1]
            res[1]+=w[j-1]
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i-1,j-1,k-1,res)
        elif b_t[i][j][k]=="c--":
            res[0]+=v[i-1]
            res[1]+='-'
            res[2]+='-'
            return outputLCS(b_t,v,w,z,i-1,j,k,res)
        elif b_t[i][j][k]=="-c-":
            res[0]+='-'
            res[1]+=w[j-1]
            res[2]+='-'
            return outputLCS(b_t,v,w,z,i,j-1,k,res)
        elif b_t[i][j][k]=="--c":
            res[0]+='-'
            res[1]+='-'
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i,j,k-1,res)
        elif b_t[i][j][k]=="cc-":
            res[0]+=v[i-1]
            res[1]+=w[j-1]
            res[2]+='-'
            return outputLCS(b_t,v,w,z,i-1,j-1,k,res)
        elif b_t[i][j][k]=="c-c":
            res[0]+=v[i-1]
            res[1]+='-'
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i-1,j,k-1,res)
        elif b_t[i][j][k]=="-cc":
            res[0]+='-'
            res[1]+=w[j-1]
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i,j-1,k-1,res)
    

    В каждом условном блоке добавлена команда return, чтобы корректно возвращать результат рекурсивного вызова функции outputLCS. Таким образом, результат рекурсивного вызова передается дальше по цепочке рекурсии и на каждом уровне мы получаем актуальное значение списка res.

  5. User

    def my_max(arr): rule=["ccc","c--","-c-","--c","cc-","c-c","-cc"] c_r=rule[0] m=arr[0] for i,e in enumerate(arr): if e>m: m=e c_r=rule[i] return m,c_r

    def LCSbackTrack(v,w,z): s=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] b_t=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] for i in range(1,len(v)+1): for j in range(1,len(w)+1): for k in range(1,(len(z)+1)): ma=0 if v[i-1]==w[j-1] and w[j-1]==z[k-1]: ma=1 s[i][j][k],b_t[i][j][k]=my_max([ s[i-1][j-1][k-1]+ma, s[i-1][j][k], s[i][j-1][k], s[i][j][k-1], s[i-1][j-1][k], s[i-1][j][k-1], s[i][j-1][k-1] ]) return s[i][j][k], b_t

    def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]): if i==0 or j==0 or k==0: return res if b_t[i][j][k]=="ccc": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j-1,k-1,res) elif b_t[i][j][k]=="c--": res[0]+=v[i-1] res[1]+='-' res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j,k,res) elif b_t[i][j][k]=="-c-": res[0]+='-' res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i,j-1,k,res) elif b_t[i][j][k]=="--c": res[0]+='-' res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j,k-1,res) elif b_t[i][j][k]=="cc-": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j-1,k,res) elif b_t[i][j][k]=="c-c": res[0]+=v[i-1] res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j,k-1,res) elif b_t[i][j][k]=="-cc": res[0]+='-' res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j-1,k-1,res)

    s1="ATATCCG" s2="TCCGA" s3="ATGTACTG" res=LCSbackTrack(s1,s2,s3) r=outputLCS(res[1],s1,s2,s3,len(s1),len(s2),len(s3)) print(r)

    Почему этот код выводит не ["A-TAT---CC--G-", "--T-----C-C-GA", "-AT--GTAC--TG-"], а ['-GCCTA-T', 'AGCC---T', '-GTC--AT']

  6. Assistant

    Проблема в данном коде состоит в том, что в рекурсивном вызове функции outputLCS отсутствует инструкция return. Из-за этого результат рекурсивного вызова не возвращается на каждом уровне рекурсии, и в итоге выводится только часть результата.

    Чтобы исправить эту проблему, вам нужно добавить инструкцию return перед каждым рекурсивным вызовом функции outputLCS. Таким образом, результат будет корректно возвращаться на каждом уровне рекурсии и сохраняться при повторных вызовах функции.

    Вот исправленный код функции outputLCS:

    def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]):
        if i==0 or j==0 or k==0:
            return res
        if b_t[i][j][k]=="ccc":
            res[0]+=v[i-1]
            res[1]+=w[j-1]
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i-1,j-1,k-1,res)
        elif b_t[i][j][k]=="c--":
            res[0]+=v[i-1]
            res[1]+='-'
            res[2]+='-'
            return outputLCS(b_t,v,w,z,i-1,j,k,res)
        elif b_t[i][j][k]=="-c-":
            res[0]+='-'
            res[1]+=w[j-1]
            res[2]+='-'
            return outputLCS(b_t,v,w,z,i,j-1,k,res)
        elif b_t[i][j][k]=="--c":
            res[0]+='-'
            res[1]+='-'
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i,j,k-1,res)
        elif b_t[i][j][k]=="cc-":
            res[0]+=v[i-1]
            res[1]+=w[j-1]
            res[2]+='-'
            return outputLCS(b_t,v,w,z,i-1,j-1,k,res)
        elif b_t[i][j][k]=="c-c":
            res[0]+=v[i-1]
            res[1]+='-'
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i-1,j,k-1,res)
        elif b_t[i][j][k]=="-cc":
            res[0]+='-'
            res[1]+=w[j-1]
            res[2]+=z[k-1]
            return outputLCS(b_t,v,w,z,i,j-1,k-1,res)
    

    Теперь после каждого рекурсивного вызова добавляется инструкция return, чтобы результат рекурсивного вызова возвращался на каждом уровне рекурсии.

  7. User

    всё равно вывод не такой

  8. Assistant

    Приношу извинения за предыдущую ошибку. Проблема в коде возникает из-за неправильного обновления списка res внутри каждого условия. Список res должен передаваться в каждый рекурсивный вызов функции outputLCS, чтобы на каждом уров

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.