문자열에 유효한 문자

Question

문자열이 주어졌으며 하나 이상의 잘못된 문자가 있으면 False를 반환하고, 그렇지 않으면 True를 반환해야합니다. 주의해야 할 것은 내장 함수와 str 연산 (예 : in, +, indexing, len)과 재귀 만 가능하다는 것입니다. 내가 지금까지 가지고하는 것은 작동하지 않습니다 :

def is_valid_sequence(dna): 
""" (str) -> bool 

Return True if and only if the DNA sequence is valid 
(A, T, C, and G) 
:param dna: string sequence 
:return: true or false 
>>> is_valid_sequence('ATTAC') 
True 
>>> is_valid_sequence('FBSSS') 
False 
""" 
valid_seq = 0 

if len(dna) == 1 and dna in ['A', 'T', 'C', 'G']: 
     valid_seq += 1 
else: 
    return is_valid_sequence(dna[1:]) 

물론,이 코드 때문에 재귀 작동하지 않고 바로 다음 재귀 반복 한 후 닦아 가져옵니다 valid_seq 변수에 1을 추가.

Answer 1

즉, 훨씬 더,이주의

의

def is_valid_sequence (dna): 
    # base case 
    if len (dna) == 0: 
    return True 
    # check if first character is valid 
    elif dna [0] not in ['A', 'T', 'C', 'G']: 
    return False 
    # otherwise, recurse on the rest of the characters 
    else: 
    return is_valid_sequence (dna [1:]) 

print (is_valid_sequence ('AATGCGA')) # True 
print (is_valid_sequence ('AATXGCGA')) # False 

---

단어 실제 구현을이다

python tho에서 재귀를주의하십시오 - 긴 dna 문자열은 스택 오버플로를 유발합니다.

GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGA를 실패이 "큰"심지어 순서를 확인하려고 TTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACA

쉽게 일정한 공간 재귀

def recur (*args): 
    return (recur, args) 

def loop (f): 
    acc = f() 
    while type (acc) is tuple and acc [0] == recur: 
    acc = f (*acc [1]) 
    return acc 

def is_valid_sequence (dna): 
    # stack-safe loop/recur implementation 
    # initialize loop state variable `s` to value of `dna` 
    return loop (lambda s = dna: 
    # base case 
    True if len (s) == 0 else 
    # check if first character valid 
    False if s [0] not in ['A', 'T', 'C', 'G'] else 
    # else recurse on the rest of the characters 
    recur (s [1:])) 

# does not overflow stack 
print (is_valid_sequence ('GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACA')) 
# True 

---

에 대한 loop/recur 메커니즘을 Clojure의 스타일을 사용하여 is_valid_sequence을 구현하여이를 방지 할 수

계속 개선

loop/recur 구현 조정에 대한 추가 기회를 우리의 함수의 성능을 제공합니다. 우리가 수행 한 문자열을 dna[0] 및 dna[1:]으로 슬라이스하면 새로운 문자가 메모리에으로 생성됩니다. 이는 우리가 작성한 첫 번째 함수에서 사용 된 재귀 API 때문에 필요합니다.

loop/recur 인터페이스를 사용하면 출력 계산에 적합한 데이터 유형을 사용할 수 있습니다.이 경우 간단한 정수 인덱스가 사용합니다. dna 우리의 람다 내에서 액세스 할 수 및 큰 입력

def is_valid_sequence (dna): 
    # only create this array once 
    valid_chars = ['A', 'T', 'C', 'G'] 
    # initialize loop state variable `i` with 0 
    return loop (lambda i = 0: 
    True if len (dna) == i else 
    False if dna [i] not in valid_chars else 
    recur (i + 1)) 

---

에 대한

파이썬과 어려운 람다를 시간/공간을 많이 절약 할 수 dna[1:] 슬라이스를 할 필요가 없습니다 - 어휘 범위 지정은 나머지 처리한다

기존의 if/elif/else 구문 대신 람다에서 순수한 표현식을 사용하게 된 것을 보았습니다. 이것은 단순한 프로그램에서는 문제가 아니지만 좀 더 복잡한 프로그램은 python에서 이런 식으로 표현하기 어려울 수 있습니다.

이 위의 프로그램과 동일하게 작동하지만 대신시키는에 대해`* 진짜 * 검증 함수를 호출 단지 * 래퍼 * 기능, 수 is_valid_sequence` 어떻게 람다

def is_valid_sequence (dna): 
    valid_chars = ['A', 'T', 'C', 'G'] 
    # plain old function; replaces lambda 
    def myloop (i = 0): 
    if len (dna) == 0: 
     return True 
    elif dna [i] not in valid_chars: 
     return False 
    else: 
     return recur (i + 1) 
    # use plain old function instead of lambda 
    return loop (myloop) 

Answer 2

다른 사람들이 말했듯이 재귀 함수는 재귀의 끝 부분에 도달 할 때 반환하지 않습니다. 당신은 말할 수 뭔가 같은 : 당신이 당신의 dna 문자열의 길이가 하나 항상보다 크거나 같은 알고있는 경우이다

if len(dna) == 1 and dna in ['A','T','G','C']: 
    return True 

. 모두 함께이 같은 끝낼 수있는 다음 dna의 첫 번째 문자가 전체 순서를 확인하기 위해 재귀 구조 다음에, 유효한 경우 여기

def is_vaild_sequence(dna): 
    if dna[0] not in ['A','T','G','C']: 
     return False 
    if len(dna) == 1: 
     return True 
    return is_vaild_sequence(dna[1:]) 

, 첫 번째 체크를 결정합니다.

재귀의 제약없이 해결할 수 있다면 이상적입니다. 반복적 인 접근 방식 (천 자 정도) 작은 크기의 DNA 염기 서열에 대한

for i in range(0,len(dna)): 
    if dna[i] not in ['A','T','G','C']: 
     return False 
return True