回答編集履歴
2
一部変更。解説とコードの改良を追記
answer
CHANGED
|
@@ -67,11 +67,71 @@
|
|
|
67
67
|
```python3
|
|
68
68
|
#import sys
|
|
69
69
|
#sys.setrecursionlimit(10000)
|
|
70
|
-
for e in seek(1,[x for x in range(2,33)]):
|
|
70
|
+
for e in seek(1,[x for x in range(2,33)],[],[]):
|
|
71
71
|
print(e)
|
|
72
72
|
|
|
73
|
-
|
|
74
73
|
```
|
|
75
74
|
結果は以下の２件。右回りと左回りの鏡像パターンがでる。
|
|
76
75
|
[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
|
|
77
|
-
[1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8]
|
|
76
|
+
[1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8]
|
|
77
|
+
|
|
78
|
+
### 追記：解説とコードの改良 (2019-03-07)
|
|
79
|
+
解決済みになったあとですが、のちに検索されるかもしれないので、情報を追加しておきます。
|
|
80
|
+
|
|
81
|
+
### 解説
|
|
82
|
+
課題のなかに再帰的なデータ構造が見つかれば、再帰的な処理を行います。
|
|
83
|
+
|
|
84
|
+
**データ構造**
|
|
85
|
+
|
|
86
|
+
データ構造は以下のとおり。
|
|
87
|
+
(すでに出来上がった数列、末尾の数)、(残りの数列)
|
|
88
|
+
処理の開始時点では、(1) 、(2 ... )です。
|
|
89
|
+
|
|
90
|
+
(残りの数列)になれるのは、[(末尾の数に足して平方数になる数)(残りの数列)] です。
|
|
91
|
+
(残りの数列)はこの構造が入れ子になっているリストです（再帰的なデータ構造）。
|
|
92
|
+
[(末尾の数に足して平方数になる数)([(末尾の数に足して平方数になる数)( ... [(末尾の数に足して平方数になる数)()]])]
|
|
93
|
+
|
|
94
|
+
ある時点で、(末尾の数に足して平方数になる数)が、複数あるかもしれないし、まったくないかもしれない。
|
|
95
|
+
- なければ、数列の作成を中止。
|
|
96
|
+
- あれば、それぞれの候補を使って、(残りの数列)に再帰的な処理を行います。
|
|
97
|
+
(残りの数列)がゼロになったら、(すでに出来上がった数列)の両端の平方数判定を行い、正しいか調べます。
|
|
98
|
+
|
|
99
|
+
**再帰処理**
|
|
100
|
+
|
|
101
|
+
回答のコードは明示的な終了条件を持ちません。後続の候補の全てに再帰的に平方数の探索を行います。後続の平方数がなければそこでreturnするし、最後まで探索すれば両端判定をおこなってreturnします。すべての候補を調べ尽くした後に終了し、正解があれば戻り値のリストに入っています。もしも、正解が見つかった時点で終了したければ、再帰呼び出しの都度、戻り値を調べて、正解があれば即座にbreakすればよいです。
|
|
102
|
+
|
|
103
|
+
### 集合分割の汎用関数
|
|
104
|
+
再帰を使わない集合分割関数を見つけました。ラムダ式(cond)、と集合(b)を引数にとり、集合をcond条件によって二分割する。
|
|
105
|
+
```python3
|
|
106
|
+
def partition(cond,b):
|
|
107
|
+
acc, rem = [], []
|
|
108
|
+
for num in b:
|
|
109
|
+
(acc if cond(num) else rem).append(num)
|
|
110
|
+
return (acc,rem)
|
|
111
|
+
```
|
|
112
|
+
|
|
113
|
+
上の集合分割関数を利用する平方数の分割関数です。ラムダ式で平方数判定を行います。
|
|
114
|
+
```python3
|
|
115
|
+
def findSuccesors2(last,b):
|
|
116
|
+
return partition(lambda x: issquare(last,x),b)
|
|
117
|
+
```
|
|
118
|
+
|
|
119
|
+
### リストのコピー
|
|
120
|
+
リストのスライス機能をつかえばdeepcopyは不要。
|
|
121
|
+
```python3
|
|
122
|
+
seek(s,r[:],acc[:],found) # seek(s,copy.deepcopy(r),copy.deepcopy(acc),found)
|
|
123
|
+
```
|
|
124
|
+
|
|
125
|
+
### Streamという用語
|
|
126
|
+
このプログラムはScalaで作成したあとpythonに移植しました。Scala(Java)のコレクションでは、Streamはイテレータと同義で、遅延評価されるリストのことです。Streamは、(先頭の要素,(未評価のリスト))が入れ子構造になっています。後ろが未評価なのでHskellなどと同様に無限集合が扱えます。Couseraで公開しているScala講座のビデオをみると、Martin Odersky教授が、関数型プログラミングのデータ構造として、遅延評価するかしないかにかかわらず、この構造を繰り返し説明しています。このデータ構造と再帰処理がセットになるので、いつか学んでみるのもよいかもしれません。
|
|
127
|
+
|
|
128
|
+
pythonに移植したあとの名前をGenreratorかIteratorとしてください。
|
|
129
|
+
|
|
130
|
+
```python3
|
|
131
|
+
def candidatesIterator(acc,rem):
|
|
132
|
+
wacc = set(acc + rem)
|
|
133
|
+
for e in set(acc):
|
|
134
|
+
remainder = list(wacc - set([e]))
|
|
135
|
+
yield (e, remainder)
|
|
136
|
+
|
|
137
|
+
```
|
1
コード統一のために修正
answer
CHANGED
|
@@ -15,7 +15,7 @@
|
|
|
15
15
|
|
|
16
16
|
```python3
|
|
17
17
|
def findSuccesors(last, b, acc=[], rem=[]):
|
|
18
|
-
if
|
|
18
|
+
if not b:
|
|
19
19
|
return (acc,rem)
|
|
20
20
|
elif issquare(last,b[0]):
|
|
21
21
|
acc.append(b[0])
|