[leetcode]46. ぜんはいち

重複する数値のないシーケンスを指定し、可能なすべての配列を返します.
例:
入力:[1,2,3]出力:[[1,2,3],[1,3,2],[2,3,1],[3,1,2],[3,2,1]
解法
やはり遡及アルゴリズムです.考え方は簡単で、簡単に書けると思っていたが、pythonのlistコピーと順序の問題という2つの大きな穴にぶつかった.
慣例に従って、まず自分で書いたコードを貼ります.

class Solution:
    def __init__(self):
        super().__init__()
        self.length = None
        self.ans = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.length = len(nums)
        now = []
        self.walk(now, nums)
        return self.ans

    def walk(self, now, left):
        if len(now) == self.length:
            self.ans.append(now.copy())
            return

        for i in range(len(left)):
            num = left.pop(i)	# left    i   
            now.append(num)		#   now
            self.walk(now, left)#walk
            now.pop()			# now  
            left.insert(i,num)	#  left

遡及する思想があった後、構想は実はとても簡単です:リストの中から1つ1つの数字を順番に抽出して、すべての数字が抽出された後、1つの実行可能な解を得ました.詳細は次のとおりです.

最初のデータが[1,2,3]、

であると仮定する

は順番に1つ目を取り、[1]#######を得て最終的にここまで遡ると、1つ目は2または3

を取ります.

残りは[2,3]、

さらに順番に残りを取って、[1,2]を得て最終的にここまで遡り、残りの2,3は3

を取る

残り[3]

解

を得る

遡及

ここで私は2つのlistを使って、それぞれnowとleftで、それぞれ今抽出したデータと残りのデータを代表します.最初はnowが空で、leftは元のデータです.
コード最適化

from typing import List
class Solution:
    def __init__(self):
        super().__init__()
        self.length = None
        self.ans = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.length = len(nums)
        now = []
        self.walk(now, nums)
        return self.ans

    def walk(self, now, left):
        if len(now) == self.length:
            self.ans.append(now)		#     copy
            return

        for i in range(len(left) ):
            # num = left.pop(i)
            # now.append(num)
            # self.walk(now, left)
            # now.pop()
            # left.insert(i,num)
            self.walk(now+[left[i]],left[:i]+left[i+1:])	#   

リストのコピー

>>> a = []
>>> b = [1,2,3]
>>> a.append(b)
>>> b.pop()
3
>>> b
[1, 2]
>>> a
[[1, 2]]

もし私がここでbを直接操作したら、aも変化します.
じゅんもんだい
ここでの順番とは、leftからデータを取り出すには必ず順番に、どこから取り出さなければならないかを指します.