こんにちは
今回の学びは
・ chosen[:]のコピーであることに注意！バックトラックではchosenを使いまわしているので、
こうする必要があることに注意。
・どこに戻すか？が重要で、以前と同じ場所でないと、いけない.
・バックトラッキングの方法は、再起を呼び出す前の状態に完全に戻すこと！が動作する条件
問題はpermutations
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
O(2^N)
今回の入力条件はdistinctだったので、一個づつ選んでいくという作戦も効いた。
そうでなければ最初の回答のようにchosenを持ち歩く必要があると思う。
４、実装しましょう。
メモリをぶん回すBF実装
class Solution_ok:
def permute(self, nums: List[int]) -> List[List[int]]:
def rec(options, chosen):
ans = []
nums = options[:]
#print(options, chosen)
if len(options) == 0:
#print(chosen)
ans.append(chosen)
else:
for i in range(len(nums)):
options = nums[:]
chosen_copy = chosen[:]
chosen_copy.append(nums[i])
del options[i]
ans += rec(options, chosen_copy)
return ans
return rec(nums, [])
これで40ms
枝刈りでだいぶ改善されて28ms。これで上位5%だ。
パフォーマンスの差はコピーの回数と思う。コピー自体、O(N)かかっちゃうからね。
inspired by https://leetcode.com/problems/permutations/discuss/496859/Python-Backtracking-beats-88
返却値として、premutationsに追加している部分は chosen[:]のコピーであることに注意！バックトラックではchosenを使いまわしているので、 こうする必要があることに注意。
class Solution:
"""
1 2 3
[1] .. [1 3] .. [ 1 3 2 ]
"""
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(nums, chosen, permutations):
if len(chosen) == len(nums):
# chosen[:]のコピーであることに注意！バックトラックではchosenを使いまわしているので、
# こうする必要があることに注意。
permutations.append(chosen[:])
else:
for i in range(len(nums)):
# 入力の特徴を活かす
# collection of distinct integers, return all possible permutations.
if nums[i] not in chosen:
chosen.append(nums[i])
backtrack(nums, chosen, permutations)
chosen.remove(nums[i])
permutation, permutations = [], []
backtrack(nums, permutation, permutations)
return permutations
バックトラッキングで、配列を配下にながして、もどってきたら元に戻す
という方法になれてきたので、最初の実装も、そのように修正してみた。
途中、options.append(value)とやっていたが
これには落とし穴があり、
・どこに戻すか？が重要で、以前と同じ場所でないと、いけない.
という重要なポイントいもきづけた。バックトラッキングの方法は、再起を呼び出す前の状態に完全に戻すこと！が動作する条件
であることがわかった
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def rec(options, chosen):
ans = []
if len(options) == 0:
ans.append(chosen[:])
else:
N = len(options)
for i in range(N):
value = options[i]
chosen.append(value)
options.remove(value)
ans += rec(options, chosen)
# 元に戻す
options.insert(i, value) # どこに戻すか？が重要で、以前と同じ場所でないと、いけない.
chosen.remove(value)
return ans
return rec(nums[:], [])
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
まとめ
・ chosen[:]のコピーであることに注意！バックトラックではchosenを使いまわしているので、
こうする必要があることに注意。
・どこに戻すか？が重要で、以前と同じ場所でないと、いけない.
・バックトラッキングの方法は、再起を呼び出す前の状態に完全に戻すこと！が動作する条件
以上です