permutations
1# @leet start 2class Solution: 3 def permute(self, nums: list[int]) -> list[list[int]]: 4 """ 5 To calculate the permutations of an array, we first note what we want to do: 6 if we're given just one item, the permutation is just that item. 7 If we're given two items, we want to take the previous iteration 8 and add the second item to the beginning and end, returning 2 items. 9 For the third one, we take the previous 2 items (0, 1), (1, 0) 10 and we want to add the third item in the beginning, middle, and end for 11 both previous items. 12 To do this, we first iterate through all the given numbers, 13 and create an array that contains all the items for this iteration. 14 Then, for each of the previous round's members, we want to iterate 15 from beginning to one past the end and we add the current number to 16 every index. 17 Finally, in each iteration, we replace the previous round's result with 18 our current round's result. 19 """ 20 res = [[]] 21 22 for num in nums: 23 new_res = [] 24 for curr in res: 25 for i in range(0, len(curr) + 1): 26 new_res.append(curr[:i] + [num] + curr[i:]) 27 res = new_res 28 29 return res 30 31 32# @leet end 33q = Solution().permute 34 35 36def test(): 37 assert q([1, 2, 3]) == [ 38 [3, 2, 1], 39 [2, 3, 1], 40 [2, 1, 3], 41 [3, 1, 2], 42 [1, 3, 2], 43 [1, 2, 3], 44 ]
3class Solution: 4 def permute(self, nums: list[int]) -> list[list[int]]: 5 """ 6 To calculate the permutations of an array, we first note what we want to do: 7 if we're given just one item, the permutation is just that item. 8 If we're given two items, we want to take the previous iteration 9 and add the second item to the beginning and end, returning 2 items. 10 For the third one, we take the previous 2 items (0, 1), (1, 0) 11 and we want to add the third item in the beginning, middle, and end for 12 both previous items. 13 To do this, we first iterate through all the given numbers, 14 and create an array that contains all the items for this iteration. 15 Then, for each of the previous round's members, we want to iterate 16 from beginning to one past the end and we add the current number to 17 every index. 18 Finally, in each iteration, we replace the previous round's result with 19 our current round's result. 20 """ 21 res = [[]] 22 23 for num in nums: 24 new_res = [] 25 for curr in res: 26 for i in range(0, len(curr) + 1): 27 new_res.append(curr[:i] + [num] + curr[i:]) 28 res = new_res 29 30 return res
4 def permute(self, nums: list[int]) -> list[list[int]]: 5 """ 6 To calculate the permutations of an array, we first note what we want to do: 7 if we're given just one item, the permutation is just that item. 8 If we're given two items, we want to take the previous iteration 9 and add the second item to the beginning and end, returning 2 items. 10 For the third one, we take the previous 2 items (0, 1), (1, 0) 11 and we want to add the third item in the beginning, middle, and end for 12 both previous items. 13 To do this, we first iterate through all the given numbers, 14 and create an array that contains all the items for this iteration. 15 Then, for each of the previous round's members, we want to iterate 16 from beginning to one past the end and we add the current number to 17 every index. 18 Finally, in each iteration, we replace the previous round's result with 19 our current round's result. 20 """ 21 res = [[]] 22 23 for num in nums: 24 new_res = [] 25 for curr in res: 26 for i in range(0, len(curr) + 1): 27 new_res.append(curr[:i] + [num] + curr[i:]) 28 res = new_res 29 30 return res
To calculate the permutations of an array, we first note what we want to do: if we're given just one item, the permutation is just that item. If we're given two items, we want to take the previous iteration and add the second item to the beginning and end, returning 2 items. For the third one, we take the previous 2 items (0, 1), (1, 0) and we want to add the third item in the beginning, middle, and end for both previous items. To do this, we first iterate through all the given numbers, and create an array that contains all the items for this iteration. Then, for each of the previous round's members, we want to iterate from beginning to one past the end and we add the current number to every index. Finally, in each iteration, we replace the previous round's result with our current round's result.
4 def permute(self, nums: list[int]) -> list[list[int]]: 5 """ 6 To calculate the permutations of an array, we first note what we want to do: 7 if we're given just one item, the permutation is just that item. 8 If we're given two items, we want to take the previous iteration 9 and add the second item to the beginning and end, returning 2 items. 10 For the third one, we take the previous 2 items (0, 1), (1, 0) 11 and we want to add the third item in the beginning, middle, and end for 12 both previous items. 13 To do this, we first iterate through all the given numbers, 14 and create an array that contains all the items for this iteration. 15 Then, for each of the previous round's members, we want to iterate 16 from beginning to one past the end and we add the current number to 17 every index. 18 Finally, in each iteration, we replace the previous round's result with 19 our current round's result. 20 """ 21 res = [[]] 22 23 for num in nums: 24 new_res = [] 25 for curr in res: 26 for i in range(0, len(curr) + 1): 27 new_res.append(curr[:i] + [num] + curr[i:]) 28 res = new_res 29 30 return res
To calculate the permutations of an array, we first note what we want to do: if we're given just one item, the permutation is just that item. If we're given two items, we want to take the previous iteration and add the second item to the beginning and end, returning 2 items. For the third one, we take the previous 2 items (0, 1), (1, 0) and we want to add the third item in the beginning, middle, and end for both previous items. To do this, we first iterate through all the given numbers, and create an array that contains all the items for this iteration. Then, for each of the previous round's members, we want to iterate from beginning to one past the end and we add the current number to every index. Finally, in each iteration, we replace the previous round's result with our current round's result.