アルゴリズム:再帰知識とテーマ整理-python

再帰
再帰はbaseに達するまで繰り返し呼び出します.考え方は数学の帰納法に似ている.書き方によって異なる時間で複雑に読むことに注意してください.たとえば,フィボナッチ数列を計算すると,式f(n)=f(n−1)+f(n−2)f(n)=f(n−1)+f(n−2)f(n)=f(n−1)+f(n−2)のように直接書くと,時間的代価が大きい.
万科目第1部例題
フィボナッチ数列
最も基本的な再帰

def f(n):
    assert(n>=0)
    result = [0, 1]
    for i in range(2, n+1):
        result.append(result[-2] + result[-1])
    return result

数式
23=((5*2+1)*2+1)113=(((11+1)+1)*2*2*2+1)学習:baseとreturn

def draweq(a,b):
    if a == b:
        return str(a)
    if b % 2 == 1:
        return '(' + draweq(a,b-1) + ' + 1' +')'
    if b < 2*a:
        return  '(' + draweq(a,b-1) + ' + 1' + ')'
    return   draweq(a,b/2) + ' * 2' 

このポイントは、baseが何なのか、b>=aなので、baseはb=aで、次に何を返すのか、印刷式なので、baseの場合は文字列で、実際には毎回1つの式を返すので、欠けている部分は括弧で、+1と*2があります.状況に応じて、対応する式を出力します.これがネストされたプロセスです.
印刷物差し
学習:ほんの少しの工事の感じ印刷尺度:目盛りを描く必要があり、目盛りを描くには線を描く必要があります.したがって、異なる関数が必要です.

def draw_line(length,label =''):
    line = '-'*length
    if label:
        line += ' '+ label
    print(line)
def draw_intervals(length):
    if length > 0:
        draw_intervals(length-1)
        draw_line(length)
        draw_intervals(length-1)
def draw_ruler(inches,length):
    draw_line(length,'0')
    for i in range(1,inches+1):
        draw_intervals(length-1)
        draw_line(length,str(i))

再帰的な運用は目盛りに
ハノータ
数学の帰納法の感覚.n=1、startからendに移動する限り.n=kと仮定すると、私はやり方を知っています.n=k+1の場合,k部分をbyに移動し,残りの1をendに移動し,最後にkをbyからendに移動する.
対応:baseがn=1の場合、他は私が再帰する部分です.

def hano(n,start,by,end):
    if n == 1:
        print('move from',start,'to',end)
    else:
        hano(n-1,start,end,by)
        hano(1,start,by,end)
        hano(n-1,by,start,end)

万門課程第二部分例題
1.集合のサブセット
遍歴的なやり方

def subsets(nums):
    result = [[]]
    for num in nums:
        for element in list(result):
            x = list(element)
            x.append(num)
            result.append(x)
            print(result)
        
    return result
def subsets_2(nums):
    res = [[]]
    for num in nums: 
        res += [ i + [num] for i in res]
        print(res)
    return res

ここでちょっと注意したいことがありますが、forループは直接resultでいいですか?印刷結果を確認
---- i = 1 result = [[]] ---- i = 2 result = [[], [1]] ---- i = 3 result = [[], [1], [2], [1, 2]]
final :[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
直接resultではだめです.こちらlist(result)or result[:]はリストコピーです.
最初のforループは、resultをコピーするたびに、各要素に新しい要素を追加します.ここでelementもコピーします(直接x=elementであれば、実はxelementが同じ配列を指していると、元の決まった集合が変わります.
再帰的な書き方
こちらは遡及の思想を用いた.遡及で重要な2点:

どのようなアクセスがありますか?

はどのような状態を維持しますか?

def subsets_recursive(nums):
    lst = []
    result = []
    subsets_recursive_helper(result, lst, nums, 0);
    return result;

def subsets_recursive_helper(result, lst, nums, pos):
    result.append(lst[:])
    for i in range(pos, len(nums)):
        lst.append(nums[i]) #
        subsets_recursive_helper(result, lst, nums, i+1) #
        lst.pop()

砕砕念:逐次解析しnums=[a,b,c]1.result=[[]]で、コピーであることに注意してください.2.ループ開始0_0、i=0 3.lst->[a]->最初の再帰4に入る.result = [ [] , [a] ] 5.ループ1_へ0,start 1=1,lst->[a,b]->は2回目の再帰6に入る.result = [ [] , [a] , [a,b] ] 7. ループ2_へ0,start 2=2,lst->[a,b,c]->3回目の再帰8に入る.result = [ [] , [a] , [a,b] , [a,b,c] ] 9. 【遡及】循環するものはなく、3回目の再帰に対してlst.pop()はc,->lst=[a,b]をポップアップし,3回目の再帰を終了する.[a,b,c]から元の状態に戻る[a,b]10.10.「遡及」.2回目の再帰に戻りlst.pop()ポップアップb,サイクル2終了,2回目の再帰終了,lst=[a]である.このとき、[a,b]は元の状態に戻る[a]11.ループ1_へ1,start 1+1=2,lst->[a,c]->は4回目の再帰12に入る.result = [ [] , [a] , [a,b] , [a,b,c] ,[a,c]] 13. 【遡及】何も循環していないlst.pop()はcをポップアップし,4回目の再帰終了,lst=[a]であった.このとき[a,c]から元の状態に戻る[a]14.【遡及】対ループ1_1,lst.pop()はa,lst=[],ループ1が終了し,最初の再帰が終了する.このとき[a]から元の状態[]15に戻る.締め切り、サイクル0の最初のサイクルを完了し、合計4回の再帰を行った.16.ループ0_に入る1,i=1,lst->[b]について5回目の再帰を開始する...に続く
2.配列
配列にはいくつかのサブ問題があります.

重複しない要素の全配列

繰り返し要素全配列

要素kのサブセット全配列

遡及法によるすべての解決:(サブセットを模倣する方法)

def perm(nums,k):
    result = []
    lst = []
    n = len(nums)
    nums.sort()
    perm_helper(result,nums,lst,k)
    return result
def perm_helper(result,nums,lst,k):
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        lst.append(nums[i])
        print(lst)
        perm_helper(result,nums[0:i]+nums[i+1:],lst,k)
        lst.pop()
    if len(lst) == k:
        result.append(lst[:])
    print('res =', result)

サブセットとの差はどこですか?違いは、メンテナンスの結果配列(result)をいつ更新するかです.サブセットは、毎回新しいものを加えて短縮します.配列ではlstが指定された長さに達する限り、追加します.そして,元の配列をどのように減らすか.サブセット:Posを利用して、絶えず前に移動して、元の配列を縮小します;配列では、追加した要素を除去します.
枝切りの書き方は、並べ替えて枝を切ることが意味があることに注意しましょう.[1,2,3]を例にlstをプリントアウト[1,2],[1,2],[1,2],[3,3],[1,3,2][2,1],[2,1,3][2,3],[2,3,1][3,1],[3,1],[3,1][3,2],[3,2],[3,2,2,1]すると,遡及がどこで起こったのかがはっきり見える
交換の考え方(個人的なやり方)に基づいて(枝を切って重複を解決することができて、Kサブセットの配列はまだよく考えていません)
思想:配列とは何か、配列は絶えず位置を交換することである.例えば、【1,2,3,4】は、【1,2,3,4】、【2,1,3,4】、【3,2,1,4】、【4,2,3,1】と理解され、これは第1の位置が他の3つの位置と交換される.そして、【2,3,4】を見ても、同様に【3,2,4】、【4,3,2】を行うことができる..このようにすれば,全配列を実現できる.
コードは次のとおりです.

def perm1(nums):
    nums.sort()
    num = [nums]
    for i in range(len(nums)):
        num = swap(num,i)
    return num
def swap(num,k):
    for lis in num[:]:
        n = len(lis)
        for i in range(k+1,n):
            x = lis[:]
            if x[i-1]==x[i] :
                continue
            x[k],x[i] = x[i],x[k]
            num.append(x)
    return num

swap関数は、k位置の要素を後の要素と交換するために使用されます.次に配列はkを0からn−1まで遍歴し,全配列を得る.枝を切るのは前後の2つの同じ要素に対して、kと交換する必要はありません.そうしないと、繰り返しになります.
参考解法:万門の授業で与えられた解法を見てみましょう

def permUnique(result, nums):
    nums.sort()
    if (len(nums)==0):
        print(result)
    for i in range(len(nums)):
        if (i != 0 and nums[i] == nums[i-1]):
            continue;
        permUnique(result+str(nums[i]), nums[0:i]+nums[i+1:])

こちらでは、なぜlen(nums)=0になったのかを考えてみましょう.ループはまだできます.再帰中のnumsはnums[0:i]+nums[i+1:]であり,このスライスは実際には複製(浅いコピー)であり,実際の最初のnums長は変わらないことに気づいた.
3.およびKのすべてのサブセット
それともサブセットのテンプレートを使って、いつappendしますか?目標とappendを達成します.
2つの要件があります.

a.同じ要素が複数回現れることを許可する

.

b.同一の要素は一度に

しか使用できない.
まずbを見ましょう

def comb(nums,target):
    result = []
    lst = []
    nums.sort()
    helper(result,lst,nums,target)
    return result
def helper(result,lst,nums,remain):
	if remains < 0: return
    if remain == 0 :
        result.append(lst[:])
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        lst.append(nums[i])
        helper(result,lst,nums[i+1:],remain-nums[i])
        lst.pop()

ステータスを1つ多く維持しました、remain.remainが0の場合、resultに追加します.remain<0直接returnは、繰り返し要素の剪断にも注意して遡及を開始します.
もう一度aを見てみましょう:どのようにして同じ要素を何度も使うことができて、また繰り返しをもたらしません.まずソートし、次に使用したものが使用されないことを確認します.カリキュラムの解答は2つ目の点でもう1つのstartで保証されていますが、実際には少し変更すればいいです.

def comb1(nums,target):
    result = []
    lst = []
    nums.sort()
    helper(result,lst,nums,target)
    return result
def helper(result,lst,nums,remain):
	if remains < 0: return
    if remain == 0 :
        result.append(lst[:])
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i-1]:
            continue       
        lst.append(nums[i])
        helper(result,lst,nums[i:],remain-nums[i])
        lst.pop()

ループ中のnums[i+1:]をnums[i:]に変更するだけで、remain<=0までループを毎回自分から開始します.
4.かっこの正しい組み合わせ
正しい組み合わせというのは)です(これでは無理です.
サブセットテンプレートの方法

def kuohao(n):
    result = []
    lst = []
    nums = [0 if i<=n else 1 for i in range(1,2*n+1) ] #  
    helper_k(result,lst,nums,n)
    return result
def helper_k(result,lst,nums,n):
    if len(lst) ==  2*n:
        result.append(trans(lst[:],n)) #  
    for i in range(len(nums)):
        if count(nums,n) or( i>0 and nums[i-1]==nums[i]):  #  
            continue
        lst.append(nums[i])
        helper_k(result,lst,nums[:i]+nums[i+1:],n)
        lst.pop()
def count(nums,n): #      
    l = len([i for i in nums if i == 0])
    r = len([i for i in nums if i == 1])
    return True if l > r else False
def trans(lst,n): #    
    for i,num in enumerate(lst[:]):
        lst[i] = '(' if num == 0 else ')'
    return ''.join(lst)

考え方は簡単で、括弧は0と1にほかならない.すなわち、n個の0とn個の1がある.私がしなければならないのは0と1の配列を見つけることにほかならない.2つのコンストレイントがあります.重複した配列はありません.各配列について、左から右に0の数が1以上の数になります.方法:符号化->正常な全配列の書き方->枝切り->復号.
カリキュラムの方法:

def generateParenthesis(n):
    def generate(prefix, left, right, parens=[]):
        if right == 0:   parens.append(prefix)
        if left > 0:     generate(prefix + '(', left-1, right)
        if right > left: generate(prefix + ')', left, right-1)
        return parens
    return generate('', n, n)