再帰関数で数え続ける方法は?

2010-01-10 python recursion

親文字列内の部分文字列のインスタンスの数を検索する再帰関数を作成しました。

カウントを維持する方法は、関数のスコープ外のグローバル変数としてcountを宣言/初期化することです。問題は、関数が最初に実行されたときにのみ正しい結果が得られることです。これは、 count != 0が最初にcount != 0ためです。関数内にある場合は、再帰的に呼び出されるたびに0に設定されます。

count=0
def countSubStringMatchRecursive(target,key):
    index=find(target,key)
    global count
    targetstring=target
    if index>=0:
        count=count+1
        target=target[index+len(key):]
        countSubStringMatchRecursive(target,key)
    else :
        pass
    return "No. of instances of", key, 'in', targetstring, 'is', count

注: 再帰関数の解決策を探しています。具体的には、うまく機能する反復関数があります。

編集:ありがとうございます、これは宿題の一部だったので、文字列モジュールのみを使用していました

Answers

コードを変更する1つの方法は、次のようにローカル関数を使用することです。

def countSubStringMatchRecursive(target,key):
    def countit(target,key,count):
        index=find(target,key)
        if index>=0:
            target=target[index+len(key):]
            count += countit(target,key,count) + 1
        return count
    return "No. of instances of", key, 'in', target, 'is', countit(target,key,0)

別の方法として、 countSubStringMatchRecursiveと呼ばれるcountSubStringMatchRecursive関数に、 countSubStringMatchRecursive0設定されている3番目のオプションパラメーターを指定することもできます。これにより、カウントを追跡できます。これは、count変数を外部の世界に公開しますが、これは望ましくないかもしれませんが、グローバル変数よりも悪いわけではないので、あなたの場合は問題にならないと思います。

また、コードを変更して、最後の再帰呼び出しを、returnステートメントを外部に提供する呼び出しにする必要があります。この例を参照してください(テストされていません):

def countSubStringMatchRecursive(target, key, count = 0):
    index = find(target, key)
    targetstring = target
    if index >= 0:
        count += 1
        target = target[index+len(key):]
        countSubStringMatchRecursive(target, key, count)
    else:
        return "No. of instances of", key, 'in', targetstring, 'is', count

編集:元の文字列を再帰に沿って移動し続けるには、4番目のパラメーターが必要になることに気付きました。これはおそらく最適なソリューションではありません。グレッグヒューギルのソリューションを使用することをお勧めします。外部とのやり取りと「ビジネスロジック」が明確に分離されているため、コードの再利用性が高まります。

再帰関数は、一致が見つかるたびに文字列の残りの内容をコピーするため、O(n ^ 2)のパフォーマンスがあります。これは、反復解O(n)よりも遅く、不必要に遅くなります。

関数のオプションのパラメーターとして検索の開始インデックスを渡すことで、コードを簡単に書き換えて高速化すると同時に、コードを簡略化して機能を拡張できます。

def countSubStringMatchRecursive(target, key, start_index = 0):
    index = target.find(key, start_index)
    if index >= 0:
        return countSubStringMatchRecursive(target, key, index + len(key)) + 1
    return 0

target_string = 'an apple and a banana'
key = 'an'
count = countSubStringMatchRecursive(target_string,  key)
print "Number of instances of %r in %r is %d" % (key, target_string, count)

出力:

Number of instances of 'an' in 'an apple and a banana' is 4

更新:文字列モジュールの検索機能を本当に使用したい場合は、次の1行を変更するだけで実行できます。

index = find(target, key, start_index)

これはどう?

def count_it(target, key):
    index = target.find(key)
    if index >= 0:
        return 1 + count_it(target[index+len(key):], key)
    else:
        return 0


print count_it("aaa bbb aaa ccc aaa", "aaa")

出力:

3

これはグレッグ・ヒューギルの答えに似たものです。ただし、代わりに、関数を呼び出すたびに現在のカウントを渡し、一致するものがなくなるとカウントを返します。 Pythonでは違いはないと思いますが、末尾呼び出し再帰を実装する言語では、これにより、 do_countへの連続する各呼び出しを呼び出しスタック上で最適化することができます。つまり、 do_count呼び出すたびに呼び出しスタックが大きくなることはありません。

def count_sub_strings(target, key):
    def do_count(target, key, count):
        index = target.find(key)
        if index >= 0:
            target = target[index + len(key):]
            return do_count(target, key, count + 1)
        else:
            return count
    return "No. of instances of %s in %s is %s" % (key, target, do_count(target, key, 0))

テストされていません ...

コード:

def countSubStringMatchRecursive(target, key, count=0):
    #### index = find(target, key) # HUH?
    index = target.find(key)
    if index >= 0:
        count += 1
        target = target[index+len(key):]
        count = countSubStringMatchRecursive(target, key, count)
    return count

for test in ['', 'bar', 'foo', 'foofoo', 'foo foo foo fo']:
   print countSubStringMatchRecursive(test, 'foo'), test.count(key), repr(test)

出力:

0 0 ''
0 0 'bar'
1 1 'foo'
2 2 'foofoo'
3 3 'foo foo foo fo'

これは単なる娯楽または宿題だと思います...再帰関数は対応するPython反復ソリューションよりも遅くなければなりません。これは当然、 target.count(key)を使用するよりも遅くなります。あなたのバージョンにあった問題... ...しかし、PEP-008を読んでください:-)

文字列モジュールに関するコメント

from string import find省略したとコメントしました。どのバージョンのPythonを使用していますか?使用している本またはチュートリアルの最終更新日はいつですか?

文字列モジュールの最初から(コンピューターには<your Python install directory>/Lib/string.pyとして配置されます。私は2.6バージョンから引用しています):

"" "文字列操作のコレクション(ほとんどは使用されなくなりました)。

警告:ここに表示されるコードのほとんどは、今日では通常使用されていません。 Python 1.6から、これらの関数の多くは次のように実装されています。 標準文字列オブジェクトのメソッド。彼らは以前に実装されていました stropと呼ばれる組み込みモジュールですが、strop自体は廃止されました。

等 「」

そして、これはfind機能用のファイルのコードです(コメントが取り除かれています):

def find(s, *args):
    return s.find(*args)

使用してstring.find(target, key)の代わりにtarget.find(key)廃棄物です。

余談ですが、提示されたすべての解決策(元のQからすべてのAsまで)は、具体的に述べられたものとは異なる問題を解決しています(特定の問題ステートメントのバグであると思いますが、修正する価値があります;-) 。検討してください:

>>> 'banana'.count('ana')
1
>>> sum('banana'[x:x+3]=='ana' for x in range(len('banana')))
2

最初の式は、「バナナ」内の「アナ」の重複しない出現をカウントしています。 2つ目はすべての出現回数を数えます 。「バナナ」のインデックス1と3に合計2つの出現回数があり、重複しています。だから問題のステートメントを与えられ、私は引用します:

いいえを見つけます。のインスタンスの 親文字列の部分文字列。

「重複しない」についての言及がない場合、重複する発生カウントする必要があるようです。もちろん、これは簡単に修正できます。一度気づくと、重複するオカレンスをスキップするlen(key)で進めるのではなく、毎回1つずつ進める必要があります。

したがって、たとえば:

import string

def countit(target, key, startfrom=0):
    where = string.find(target, key, startfrom)
    if where < 0: return 0
    return 1 + countit(target, key, where+1)

print countit('banana', 'ana')

2出力し、両方の(重複する)オカレンスをカウントします。

def countSubStringMatchRecursive(target, key):
    index = string.find(target, key)
    if index == -1:
        return 0
    else:
        return 1 + countSubStringMatchRecursive(target[index + len(key):], key)

私はこのコースをOpenCoursewareでやっています。素晴らしいです。とにかく、これは私がやったことです。上のadamseからインスピレーションを受けました。

def countSubStringMatchRecursive(target, key, counter = 0):
    if find(target,key) == 0:
        countSubStringMatchRecursive(target[1:], key, counter + 1)
    elif find(target,key) > 0:
        countSubStringMatchRecursive(target[1:], key, counter)
    elif find(target,key) == -1:
        print counter

重複するオカレンスを考慮し、 MITからの元の定義を維持することは、これが私が入手できるよりシンプルでコンパクトなコードです。

コード:

from string import *
def countSubStringMatchRecursive(target, key):
    index = find(target, key)
    if index > -1:
        return countSubStringMatchRecursive(target[index + 1:], key) + 1
    return 0


def test(target, key):
    instances = countSubStringMatchRecursive(target, key)
    if instances == 0:
        print "No instance of %r in %r" % (key, target)
    else:
        print "Number of instances of %r in %r: %d" % (key, target, instances)

test("atgacatgcacaagtatgcat","ggcc")
test("atgacatgcacaagtatgcat","atgc")
test("banana", "ana")

出力:

「atgacatgcacaagtatgcat」に「ggcc」のインスタンスはありません

「atgacatgcacaagtatgcat」内の「atgc」のインスタンス数:2

「banana」内の「ana」のインスタンス数:2

steps = 0
def addPersistence(number, steps):
    steps += 1
    if len(str(number))==1:
        print(str(number) + "\nDone---------------------------------------------------")
        print("TOTAL STEPS " + str(steps-1))

    digits = [int(i) for i in str(number)]

    result = 0
    for j in digits:
        result += j


    if len(str(number)) != 1:
        print(number)
        addPersistence(result, steps)

これは、私のプロジェクトの1つからコピーした例です。この関数は、数値の永続性を追加することを決定します(数値の桁を追加して、数値が1になるまで繰り返します)が、確実に再利用でき、このような関数を使用できます(これはPython 3コードです) 、それをPython 2に変更したい場合でも機能します):

count=0
def countSubStringMatchRecursive(target,key,count):
    index=find(target,key)
    targetstring=target
    if index>=0:
        count+=1
        target=target[index+len(key):]
        countSubStringMatchRecursive(target,key,count)
    else :
        pass
    print("STEPS: "+str(count))

私のコードに気付くかもしれませんが、そのコードは少し異なります。どうして?その答えは、その関数を使用して数値が1になるのに必要なステップ数は、最後の呼び出しがその前の呼び出しの複製であるため、関数に含まれていないということです。

Related