【LeetCode】46. Permutations 解答・解説【Python】

問題
1. 原文
2. 内容
解答
メモ・参考・感想

問題

原文

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

1
2

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1] Output: [[0,1],[1,0]]

1
2

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1] Output: [[1]]

1
2

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6

-10 <= nums[i] <= 10

All the integers of nums are unique.

内容

各要素が異なる整数であるリストnumsが与えられます。

考えられる全ての順列を返してください。

解答はどの順番でも問題ありません。

※正しくない可能性があります。

解答

解答1：Python,itertools.permutations(ライブラリ)

from itertools import permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = permutations(nums)
        return answer

from itertools import permutations

class Solution:

def permute(self, nums: List[int]) -> List[List[int]]:

answer = permutations(nums)

return answer

Pythonにはitertoolsというライブラリで順列を作る方法がある。

とても便利だけど、今回はライブラリに頼らずに作る方法を勉強する問題。

解答2：Python,DFS(深さ優先探索)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = []
        element = []
        self.DFS(nums,element,answer)
        return answer


    def DFS(self, nums, element, answer):
        if not nums:
            answer.append(element)

        for i in range(len(nums)):
            self.DFS(nums[:i]+nums[i+1:], element+[nums[i]], answer)

class Solution:

def permute(self, nums: List[int]) -> List[List[int]]:

answer = []

element = []

self.DFS(nums,element,answer)

return answer

def DFS(self, nums, element, answer):

if not nums:

answer.append(element)

for i in range(len(nums)):

self.DFS(nums[:i]+nums[i+1:], element+[nums[i]], answer)

■詳細

〇変数

・answerはこの問題の解答である順列。

→[[1,2,3],[1,3,2],[2,1,3],[2,3,1]・・・]

再帰的に処理される中で、1つずつ要素が加えられていく。

・elementはanswerに加えられる各要素。

→[1,2,3]、[1,3,2]、[2,1,3]などanswerの各要素

〇各関数の動作

・permute関数ではanswerとelementを用意してからDFS関数を呼び出す。

DFS関数でanswerに1つずつ要素elementが加えられ、順列の作成終了後にreturnで返す。

・DFS関数では、まずnumsが空だった場合はanswerにelementを追加する。

次に、numsが空でない場合は、numsの各要素をfor文で一巡走査する。

numsのi番目の要素を除外し、numsの残りの要素を使って再帰的にDFS関数を呼び出す。

nums[:i]+nums[i+1:] は、i番目より前と、i番目より後の要素を結合している。

これにより、i番目の要素を取り除いている。

element+[nums[i]] は、elementにnumsのi番目の要素を結合している。

i番目の要素を除外することでnumsの要素をへらしていきつつ、

最初は空だったelementに一つずつ要素を加えていくことで

answerの要素の1つであるelementを作る。

■以下、DFS関数の動作イメージ

※nums = [1,2,3]、　「・」はDFS関数が呼び出されたことを指す。

以下の処理をnumsの各要素に行う。

＜i=1の場合＞

・element = [1], nums = [2,3]　再度DFS関数を呼び出し

nums = [2,3]をfor文で処理↓　※2の場合

・element = [1,2], nums = [3]　再度DFS関数を呼び出し

nums = [3]をfor文で処理↓

・element = [1,2,3], nums = []　再度DFS関数を呼び出し

・numsが空なのでanswerにelement = [1,2,3]を追加

nums = [2,3]をfor文で処理↓　※3の場合

・element = [1,3],nums = [2]　再度DFS関数を呼び出し

nums = [2]をfor文で処理↓

・element = [1,3,2],nums = []　再度DFS関数を呼び出し

・numsが空なのでanswerにelement = [1,3,2]を呼び出し

■以下、メモ

nums.remove(i)でもi番目の要素を除外できるが、元の配列numsから要素がなくなると再帰的な処理ができなくなる？

再帰的にDFS関数を呼び出す際、nums[:i]+nums[i+1:]として新しく配列を作ることで、i番目の要素除外の操作が元の配列numsに影響しないようにしている。

解答3：Python, DFS(深さ優先探索),enumerate

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = []
        if len(nums) == 1:
            return [nums]
        else:
            #enumerateはイテラブルオブジェクトから、要素とインデックスを同時に取得できる
            for i, num in enumerate(nums):
                #
                for permutation in self.permute(nums[:i] + nums[i+1:]):
                    answer.append([num] + permutation)
            return answer