LoginSignup
0
0

More than 3 years have passed since last update.

@AKpirion

部分和と向き合ってみる

Last updated at Posted at 2020-10-28

こんばんは。
お久しぶりです(*´ω｀)

今回のチャンレンジは、任意の要素を含んだ配列の中から
無作為に要素を選んで、合算します。
しかし、ただ合算すれば良いのではなく、
目標値になるように合算しなければなりません。

例えば、合計が 20になるように配列の中から組み合わせを選んでください!!
っというものです。

ややこい(;´･ω･)

かなり有名で基礎的な内容のようですが、
個人的には手こずりました(笑)

いきなりですけど、
コードを載せちゃいます。

Partial_sum.py
def solve(Nlist, target,  i=0, sum=0):
    if i == len(Nlist):
        return sum == target
    if (solve(Nlist, target, i + 1, sum)):
        return True
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
    return False

Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))

思ったよりシンプルですが、動きは複雑です。
例えばですが、
最初はここだけ見ます。

Partial_sum.py
#ここから start!! 
Nlist = [1,3,5,12,7]
target = 11
#          ↓[1,3,4...] ↓ 11
print(solve(Nlist, target))

solve の中に、Nlist と target を放り込みます。
イメージとしては、要素を含んだ配列と、目標となる合計値を
丸々投げて、あと宜しく!! ってするだけです。
では、solve の中を見ていきましょう。

Partial_sum.py
# iは現在地のイメージです。
# sum は現在の数値の合計値です。
# 現在地は 0, 合計値も 0 
def solve(Nlist, target,  i=0, sum=0):
    # Nlist の長さは 5 、最初は i == 0 なので Pass!!
    if i == len(Nlist):
        return sum == target
    # あれ?! if 文の中に更に solve があります。分けわからん!!
    # もう読むのを辞めよう(笑)
    if (solve(Nlist, target, i + 1, sum)):

分からん、投げ出したいです(笑)。

ダメダメ!逃げちゃ。。
答えから言うと、if 文の中に再帰を設けている場合、
その再帰処理をやり切って ture or false を導きます。
これにより if 文の中に入るか否かを判断します。
んな、馬鹿な(笑)

取りあえず出発しますか、
if の中にある solve(Nlist, target, i + 1, sum) の
先に何があるかを探す冒険に。

では、順番に行きましょう( ｀ー´)ノ

i=0.py
def solve(Nlist, target,  i=0, sum=0):
    #pass!
    if i == len(Nlist):
        return sum == target
    #if 文の条件文が True or False の何れか、ハッキリするまで再帰処理を続けます。
    if (solve(Nlist, target, i + 1, sum)):
        return True
i=1.py
#solve(Nlist,target,1(=0+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=1, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
i=2.py
#solve(Nlist,target,2(=1+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=2, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
i=3.py
#solve(Nlist,target,3(=2+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=3, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
i=4.py
#solve(Nlist,target,4(=3+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=4, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
i=5.py
#solve(Nlist,target,5(=4+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=0):
    #i == len(Nlist) == 5 でやっと、冒頭の if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(0) != target(11)。False
        return sum == target

なるほど、i = 5 まで行きましたが結局 False でした。
その後、どうなるんでしょう。。
とりあえず i = 5 の結果は False だったので、
前の層である i = 4 に持ち帰ってみましょう。

i=4.py
def solve(Nlist, target,  i=4, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # if 分内の条件文は Flase でした。って事は、ここの if 文は pass です!!
    #次の if 文へ行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
    # ここでは i = 4 なので代入してみましょう
    #  (solve(Nlist, target, 4 + 1, sum + Nlist[4]))
    #  (solve(Nlist, target,   5  , 0   + 7        ) //Nlist = [1,3,5,12,7]
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True

はい、次の if 文に移ります。
新たな条件文で、再度 i = 5 の時を確かめてみましょう。

i=5.py
#solve(Nlist,target,5,7) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=7):
    #i == len(Nlist) == 5 , if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(7) != target(11)。False
        return sum == target

ここまでを図にすると以下のような形になると思います。
図2.PNG
優秀な人は、頭でこれが出来るんでしょうけど、
自分はできなかったので、紙に書いたりして整理しました。
話を戻します、i = 4 までは何をしてもダメだったようです。
では、i = 3 に、この結果を報告しましょう。

i=3.py
#solve(Nlist,target,3(=2+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=3, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #False なので pass !! 
    #今までの処理からsum が 11 になることはありませんでした
    if (solve(Nlist, target, i + 1, sum)):
        return True
    #  (solve(Nlist, target, 3 + 1, sum + Nlist[3])): //Nlist = [1,3,5,12,7]
    #  (solve(Nlist, target,   4  ,  0  +    12   )):
    #  上記の条件を以下に代入して、新たな if 分に突入!!                 
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
i=4.py
#solve(Nlist,target,4(=3+1),12) で再帰処理に入りました。
def solve(Nlist, target,  i=4, sum=12):
    #pass!!
    if i == len(Nlist):
        return sum == target

    # 再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
i=5.py
#solve(Nlist,target,5(=4+1),12) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=12):
    #i == len(Nlist) == 5 , if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(12) != target(11)。False
        return sum == target

False でしたね、一つ戻って報告です。

i=4.py
#solve(Nlist,target,4(=3+1),12) で再帰処理に入りました。
def solve(Nlist, target,  i=4, sum=12):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #False で Pass!
    if (solve(Nlist, target, i + 1, sum)):
        return True
    #Next↓
    if (solve(Nlist, target, i + 1, sum + Nlist[i]))://Nlist = [1,3,5,12,7]
        return True
i=5.py
#solve(Nlist,target,5(=4+1),12 + 7) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=19):
    #i == len(Nlist) == 5 , if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(19) != target(11)。False
        return sum == target

図にしてみます。
図3.PNG
なんか、木構造見たいです(笑)
気の長い作業ですが、以下のポイントだけ抑えれば oK です。

1.True, False が見えるまで if 文の条件文(再帰)は追っかけ続ける
2.True, False が見えたら、ひとつ前の層に戻り、solve 内の記述に沿い忠実に動作を追いかける

偉そうに書いていますが、私は全く知らなかったので、
何をどう遷移しているか確認するために
以下のように pirnt を混ぜました。

Partial_sum.py
def solve(Nlist, target,  i=0, sum=0):
    print(f"i:{i},sum:{sum}") # 再帰処理中に、現在値を表示して分かりやすくする
    if i == len(Nlist):
        # 再帰処理は、冒頭に最下層に来た時の条件文を入れます。
        # なので、この if 文に入った時が最下層と分かるコメントを print します
        print(f"Result:i={i},sum={sum}") 
        print() # 次の処理とを区切るために改行しています
        return sum == target
    if (solve(Nlist, target, i + 1, sum)):
        return True
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
    return False

Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))

実行結果を見てみましょう!!

実行結果.py
i:0,sum:0
i:1,sum:0
i:2,sum:0
i:3,sum:0
i:4,sum:0
i:5,sum:0
Result:i=5,sum=0
#↑前述の図と比較してみてください。i, sum の変化が図と一致していません？
#Result:i=5,sum=0 とあるように sum は 11 ではないので False を返します
#返した後は i=4 の時に帰ります。
#帰ったあとは、そのまま次の IF 文に続きます。
#よって、次の表示は以下にある i = 5 の時の pirnt になります。
#理解できない人は前述のページに戻ってください。
i:5,sum:7
Result:i=5,sum=7
#↑sum(=7) != 11 なので False です。
#よって、i = 4 の時の 2 つの if 文は両方とも False となります。
#次は i = 3 の時の if 文に戻りますが、処理は後は前述と同じです。
i:4,sum:12
i:5,sum:12
Result:i=5,sum=12

i:5,sum:19
Result:i=5,sum=19

i:3,sum:5
i:4,sum:5
i:5,sum:5
Result:i=5,sum=5

i:5,sum:12
Result:i=5,sum=12

i:4,sum:17
i:5,sum:17
Result:i=5,sum=17

i:5,sum:24
Result:i=5,sum=24

i:2,sum:3
i:3,sum:3
i:4,sum:3
i:5,sum:3
Result:i=5,sum=3

i:5,sum:10
Result:i=5,sum=10

i:4,sum:15
i:5,sum:15
Result:i=5,sum=15

i:5,sum:22
Result:i=5,sum=22

i:3,sum:8
i:4,sum:8
i:5,sum:8
Result:i=5,sum=8

i:5,sum:15
Result:i=5,sum=15

i:4,sum:20
i:5,sum:20
Result:i=5,sum=20

i:5,sum:27
Result:i=5,sum=27

i:1,sum:1
i:2,sum:1
i:3,sum:1
i:4,sum:1
i:5,sum:1
Result:i=5,sum=1

i:5,sum:8
Result:i=5,sum=8

i:4,sum:13
i:5,sum:13
Result:i=5,sum=13

i:5,sum:20
Result:i=5,sum=20

i:3,sum:6
i:4,sum:6
i:5,sum:6
Result:i=5,sum=6

i:5,sum:13
Result:i=5,sum=13

i:4,sum:18
i:5,sum:18
Result:i=5,sum=18

i:5,sum:25
Result:i=5,sum=25

i:2,sum:4
i:3,sum:4
i:4,sum:4
i:5,sum:4
Result:i=5,sum=4

i:5,sum:11
Result:i=5,sum=11

True

以上のように、遷移できない限界まで達した後に、
一つ戻り、また限界まで動作するような処理を繰り返す手法を深さ優先探索と言います。
資料には、比較的簡単に書けるって書いてありますが、
いやいや、初心者にはキッツイ!!( ﾟДﾟ)

まだまだ先は長そうです(*´ω｀)

0
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0