回答編集履歴
2
一部変更。解説とコードの改良を追記
test
CHANGED
|
@@ -136,14 +136,12 @@
|
|
|
136
136
|
|
|
137
137
|
#sys.setrecursionlimit(10000)
|
|
138
138
|
|
|
139
|
-
for e in seek(1,[x for x in range(2,33)]):
|
|
139
|
+
for e in seek(1,[x for x in range(2,33)],[],[]):
|
|
140
140
|
|
|
141
141
|
print(e)
|
|
142
142
|
|
|
143
143
|
|
|
144
144
|
|
|
145
|
-
|
|
146
|
-
|
|
147
145
|
```
|
|
148
146
|
|
|
149
147
|
結果は以下の２件。右回りと左回りの鏡像パターンがでる。
|
|
@@ -151,3 +149,125 @@
|
|
|
151
149
|
[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]
|
|
152
150
|
|
|
153
151
|
[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]
|
|
152
|
+
|
|
153
|
+
|
|
154
|
+
|
|
155
|
+
### 追記：解説とコードの改良 (2019-03-07)
|
|
156
|
+
|
|
157
|
+
解決済みになったあとですが、のちに検索されるかもしれないので、情報を追加しておきます。
|
|
158
|
+
|
|
159
|
+
|
|
160
|
+
|
|
161
|
+
### 解説
|
|
162
|
+
|
|
163
|
+
課題のなかに再帰的なデータ構造が見つかれば、再帰的な処理を行います。
|
|
164
|
+
|
|
165
|
+
|
|
166
|
+
|
|
167
|
+
**データ構造**
|
|
168
|
+
|
|
169
|
+
|
|
170
|
+
|
|
171
|
+
データ構造は以下のとおり。
|
|
172
|
+
|
|
173
|
+
(すでに出来上がった数列、末尾の数)、(残りの数列)
|
|
174
|
+
|
|
175
|
+
処理の開始時点では、(1) 、(2 ... )です。
|
|
176
|
+
|
|
177
|
+
|
|
178
|
+
|
|
179
|
+
(残りの数列)になれるのは、[(末尾の数に足して平方数になる数)(残りの数列)] です。
|
|
180
|
+
|
|
181
|
+
(残りの数列)はこの構造が入れ子になっているリストです（再帰的なデータ構造）。
|
|
182
|
+
|
|
183
|
+
[(末尾の数に足して平方数になる数)([(末尾の数に足して平方数になる数)( ... [(末尾の数に足して平方数になる数)()]])]
|
|
184
|
+
|
|
185
|
+
|
|
186
|
+
|
|
187
|
+
ある時点で、(末尾の数に足して平方数になる数)が、複数あるかもしれないし、まったくないかもしれない。
|
|
188
|
+
|
|
189
|
+
- なければ、数列の作成を中止。
|
|
190
|
+
|
|
191
|
+
- あれば、それぞれの候補を使って、(残りの数列)に再帰的な処理を行います。
|
|
192
|
+
|
|
193
|
+
(残りの数列)がゼロになったら、(すでに出来上がった数列)の両端の平方数判定を行い、正しいか調べます。
|
|
194
|
+
|
|
195
|
+
|
|
196
|
+
|
|
197
|
+
**再帰処理**
|
|
198
|
+
|
|
199
|
+
|
|
200
|
+
|
|
201
|
+
回答のコードは明示的な終了条件を持ちません。後続の候補の全てに再帰的に平方数の探索を行います。後続の平方数がなければそこでreturnするし、最後まで探索すれば両端判定をおこなってreturnします。すべての候補を調べ尽くした後に終了し、正解があれば戻り値のリストに入っています。もしも、正解が見つかった時点で終了したければ、再帰呼び出しの都度、戻り値を調べて、正解があれば即座にbreakすればよいです。
|
|
202
|
+
|
|
203
|
+
|
|
204
|
+
|
|
205
|
+
### 集合分割の汎用関数
|
|
206
|
+
|
|
207
|
+
再帰を使わない集合分割関数を見つけました。ラムダ式(cond)、と集合(b)を引数にとり、集合をcond条件によって二分割する。
|
|
208
|
+
|
|
209
|
+
```python3
|
|
210
|
+
|
|
211
|
+
def partition(cond,b):
|
|
212
|
+
|
|
213
|
+
acc, rem = [], []
|
|
214
|
+
|
|
215
|
+
for num in b:
|
|
216
|
+
|
|
217
|
+
(acc if cond(num) else rem).append(num)
|
|
218
|
+
|
|
219
|
+
return (acc,rem)
|
|
220
|
+
|
|
221
|
+
```
|
|
222
|
+
|
|
223
|
+
|
|
224
|
+
|
|
225
|
+
上の集合分割関数を利用する平方数の分割関数です。ラムダ式で平方数判定を行います。
|
|
226
|
+
|
|
227
|
+
```python3
|
|
228
|
+
|
|
229
|
+
def findSuccesors2(last,b):
|
|
230
|
+
|
|
231
|
+
return partition(lambda x: issquare(last,x),b)
|
|
232
|
+
|
|
233
|
+
```
|
|
234
|
+
|
|
235
|
+
|
|
236
|
+
|
|
237
|
+
### リストのコピー
|
|
238
|
+
|
|
239
|
+
リストのスライス機能をつかえばdeepcopyは不要。
|
|
240
|
+
|
|
241
|
+
```python3
|
|
242
|
+
|
|
243
|
+
seek(s,r[:],acc[:],found) # seek(s,copy.deepcopy(r),copy.deepcopy(acc),found)
|
|
244
|
+
|
|
245
|
+
```
|
|
246
|
+
|
|
247
|
+
|
|
248
|
+
|
|
249
|
+
### Streamという用語
|
|
250
|
+
|
|
251
|
+
このプログラムはScalaで作成したあとpythonに移植しました。Scala(Java)のコレクションでは、Streamはイテレータと同義で、遅延評価されるリストのことです。Streamは、(先頭の要素,(未評価のリスト))が入れ子構造になっています。後ろが未評価なのでHskellなどと同様に無限集合が扱えます。Couseraで公開しているScala講座のビデオをみると、Martin Odersky教授が、関数型プログラミングのデータ構造として、遅延評価するかしないかにかかわらず、この構造を繰り返し説明しています。このデータ構造と再帰処理がセットになるので、いつか学んでみるのもよいかもしれません。
|
|
252
|
+
|
|
253
|
+
|
|
254
|
+
|
|
255
|
+
pythonに移植したあとの名前をGenreratorかIteratorとしてください。
|
|
256
|
+
|
|
257
|
+
|
|
258
|
+
|
|
259
|
+
```python3
|
|
260
|
+
|
|
261
|
+
def candidatesIterator(acc,rem):
|
|
262
|
+
|
|
263
|
+
wacc = set(acc + rem)
|
|
264
|
+
|
|
265
|
+
for e in set(acc):
|
|
266
|
+
|
|
267
|
+
remainder = list(wacc - set([e]))
|
|
268
|
+
|
|
269
|
+
yield (e, remainder)
|
|
270
|
+
|
|
271
|
+
|
|
272
|
+
|
|
273
|
+
```
|
1
コード統一のために修正
test
CHANGED
|
@@ -32,7 +32,7 @@
|
|
|
32
32
|
|
|
33
33
|
def findSuccesors(last, b, acc=[], rem=[]):
|
|
34
34
|
|
|
35
|
-
if b
|
|
35
|
+
if not b:
|
|
36
36
|
|
|
37
37
|
return (acc,rem)
|
|
38
38
|
|