いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 46 Permutations

投稿日:

こんにちは

今回の学びは

chosen[:]のコピーであることに注意!バックトラックではchosenを使いまわしているので、
こうする必要があることに注意。

どこに戻すか?が重要で、以前と同じ場所でないと、いけない.

バックトラッキングの方法は、再起を呼び出す前の状態に完全に戻すこと!が動作する条件

 

問題はpermutations

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

O(2^N)

 

今回の入力条件はdistinctだったので、一個づつ選んでいくという作戦も効いた。

そうでなければ最初の回答のようにchosenを持ち歩く必要があると思う。

 

4、実装しましょう。

メモリをぶん回す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[:], [])

 

5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

 

 

まとめ

chosen[:]のコピーであることに注意!バックトラックではchosenを使いまわしているので、
こうする必要があることに注意。

どこに戻すか?が重要で、以前と同じ場所でないと、いけない.

バックトラッキングの方法は、再起を呼び出す前の状態に完全に戻すこと!が動作する条件

 

以上です

-アルゴリズム
-,

Copyright© CTOの日記 , 2020 All Rights Reserved.