文字列内の有効な文字

Question

文字列が与えられ、無効な文字が1つ以上ある場合はFalseを返す必要があります。注意点は、組み込み関数と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の再帰に注意してください。長いdna文字列はスタックオーバーフローの原因になります。

GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGAを失敗していました。この「大」でもシーケンスを検証しようとすると、 TTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACA

あなたは簡単にloop/recur一定の空間再帰のためのメカニズム

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 

---

を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)) 

---

Pythonと手に負えないラムダのための時間/多くのスペースを節約します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文字列は常によりも大きいか、長さが1に等しい知っていれば、ある

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

：あなたのような何かを言うことができます。すべて一緒にあなたのようなもので終わるかもしれない：

ここ

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の最初の文字が有効である場合、最初のチェックは、全体のシーケンスを確認するために再帰構造に続いて、決定します。

理想的には、これが再帰の制約なしに解決できる場合は、それを取ってください。反復アプローチは、（千文字程度）小さいサイズのDNA配列について

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