回答編集履歴
1
コメントに対する追記
test
CHANGED
|
@@ -1,3 +1,65 @@
|
|
|
1
|
+
通常、事前条件などはコード化されません。コメントに書かれればいいところで、プログラムの一部として表明(アサーション)されることは稀です。今回のコードにも、「ここを見ればわかるでしょ」といえるほど明確に示してる部分があるとは思いません。
|
|
2
|
+
|
|
3
|
+
|
|
4
|
+
|
|
5
|
+
ではなぜこれが重要なのかというと、これを理解することがコードを理解することだと思ってるからです。特に強調したいのが、これは再帰だとか関係なく、コードの読み書き全般において重要だと考えているということです。
|
|
6
|
+
|
|
7
|
+
例えば、ソースコードが与えられたときに紙と鉛筆を使って同じ処理を行えることも理解してるといえる状況の一つです。しかし、ふつうはこれを理解してるとは言わないでしょう。それぞれのコードがどういう役割を果たして、どう関係しているのかがわからなければ理解したとは言えません。
|
|
8
|
+
|
|
9
|
+
|
|
10
|
+
|
|
11
|
+
それさえわかってしまえば再帰関数への書き換えは大きく進みます。あとは、その役割を再帰関数で行うにはどうしたらいいのか、完全に同じ役割の再帰関数でないのならほかの役割をどう変えなきゃいけないのか、これを考えるだけですから。
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
コメントを見ていて気になったのは手続き的には理解できると言ってるところで、きちんと理解しようと思ったら手続き的だろうがそれなりに大変です。逆に手続き的なコードのほうが本質的ではない部分が入り込みやすいので理解しづらいことすらあります。
|
|
16
|
+
|
|
17
|
+
たとえば今のコードでも、tmpsのような典型的な一時変数は言語の都合上置かれてるだけで理解する上では冗長なだけです。
|
|
18
|
+
|
|
19
|
+
一番内側のwhileループ中でresultsに追加している部分も同様です。resultsに追加している部分がない場合このwhileループの役割は__**「outputにcを0個以上追加したもののうち合計がtarget以下のものをtmpsに入れる」**__ことで、resultsに追加する部分を付け加えることで**__「outputにcを0個以上追加したもののうち合計がtarget以下のものをtmpsに入れる + outputにcを1個以上追加したもののうち合計がtargetになるものをresultsに入れる」__**になります。
|
|
20
|
+
|
|
21
|
+
なんでtmpsに入れるのが「**__0個以上追加したもの__**」で、resultsに入れるのが「**__1個以上追加したもの__**」なんでしょう? あんまり深入りしませんがややこしくないですか? 実はresultsへの追加はここでやる必要はないのでこんなこと考えないようにすることも可能なんです。ありうる組み合わせを列挙してその中から合計がちょうどtargetになるものを選び出すと考えれば、むしろループが終わってからoutputsから合計がちょうどになるものを抜き出すほうが自然です。そういう意味ではこのwhileループは手続き型のコードにありがちな、分離可能な処理を一つのループで同時に行っている状態です。
|
|
22
|
+
|
|
23
|
+
|
|
24
|
+
|
|
25
|
+
そんなこともあって、別にループで書かれてるからと言って理解する難しさにはそんなに差がないのにループなら理解できると思っているのは、ループのコードに関しては深く追及してないんじゃないかと思ってしまいます。
|
|
26
|
+
|
|
27
|
+
|
|
28
|
+
|
|
29
|
+
再帰で書いたコードの全体です。Pythonの言語仕様に詳しくないので同名の関数がどう扱われてるのかわかりませんが、とりあえず期待通り動いてるのでそのまま貼ります。appendの呼び出しはすべてここで定義しているappendを呼び出しているつもりです。
|
|
30
|
+
|
|
31
|
+
```Python
|
|
32
|
+
|
|
33
|
+
def append(combination: List[int], value: int) -> List[List[int]]:
|
|
34
|
+
|
|
35
|
+
if sum(combination) > target: #base case すでにtargetを超えていたら組み合わせは存在しない
|
|
36
|
+
|
|
37
|
+
return []
|
|
38
|
+
|
|
39
|
+
|
|
40
|
+
|
|
41
|
+
return [combination] + append(combination + [value], value) # valueを一つも追加しない組み合わせと一つ以上追加したものの和集合
|
|
42
|
+
|
|
43
|
+
|
|
44
|
+
|
|
45
|
+
def rec(i: int) -> List[List[int]]:
|
|
46
|
+
|
|
47
|
+
if i == len(candidates):
|
|
48
|
+
|
|
49
|
+
return [[]] #使える要素がないので、何も選ばない組み合わせしかない
|
|
50
|
+
|
|
51
|
+
|
|
52
|
+
|
|
53
|
+
return [appended for combination in rec(i + 1) for appended in append(combination, candidates[i])] #i + 1以降を使う組み合わせ(combination)それぞれに対してcandidates[i]を0個以上追加したもので合計がtarget以下のもの
|
|
54
|
+
|
|
55
|
+
|
|
56
|
+
|
|
57
|
+
return [combination for combination in rec(0) if sum(combination) == target]
|
|
58
|
+
|
|
59
|
+
```
|
|
60
|
+
|
|
61
|
+
---
|
|
62
|
+
|
|
1
63
|
少し話はそれますが「事前条件」「事後条件」「(ループ)不変条件」という考え方になじみはありますか?
|
|
2
64
|
|
|
3
65
|
|