LeetCode "47. Permutations II"をPythonで解いた話

前回の記事とほぼ同じ内容です。

問題

数の集まりnumsが与えられています。これには、同じ数字が複数入っていることがありえます。
すべてのありうる順列を、1つの順列につき1つずつ答えてください。
順番は気にしません。

こちらから挑戦できます。
https://leetcode.com/problems/permutations-ii/

方針

今回も、ライブラリーを使ってはいけないという注意書きがないので、itertoolsを使います。

from itertools import permutations

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        #重複を防ぐために一度setにします。
        #問題は答えとしてlistを求めていますが、setのままでも通ります。
        return  set(permutations(nums, len(nums)))

結果：Success

やったぜ！

おまけ：permutationsを使わずに解けるか？

方針：
前回とほぼ同じ方針でできそうです。
ただし、要素の順列を作るのではなく、先にindexの順列を作ります。
そのindexの順列に従って、要素を改めて並べます。

import queue

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        len_nums = len(nums)

        wake = set()

        q = queue.Queue()

        indices = [i for i in range(len_nums)]
        set_indices = set(indices)

        ans_indices = set()

        for index in indices:
            q.put(tuple([index]))

        while not q.empty():
            cur = q.get()

            if len(cur) == len_nums:
                ans_indices.add(cur)
                continue

            uncharted = set_indices - set(cur)

            for index in uncharted:
                candidate = cur + tuple([index])

                if candidate not in wake:
                    q.put(candidate)
                    wake.add(candidate)

        ans_nums = set()

        for item in ans_indices:
            ans_nums.add(tuple(nums[i] for i in item))

        return ans_nums

結果:Succes

やったぜ！