고유한 정수 모음이 있다고 가정합니다. 가능한 모든 순열을 찾아야 합니다. 따라서 배열이 [2,1,3]과 같으면 결과는 [[1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [3,1,2], [3,2,1]]
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 재귀적 접근 방식을 사용하여 list, start, curr 및 res를 만들 것입니다.
- if start> length of list – 1이면 res에 curr을 추가하고 반환합니다.
- 지정된 목록의 길이 시작부터 범위 내 i의 경우 – 1
- 인덱스 시작 및 (시작 + (i – 시작))에 있는 목록의 요소 교체
- 순열(목록, 시작 + 1, curr + [목록[시작]], res)
- 인덱스 시작 및 (시작 + (i – 시작))에 있는 목록의 요소 교체
- 처음에 순열(arr, 0, [], res) 호출
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def permute(self, nums): result = [] self.permute_util(nums,0,[],result) return result def permute_util(self,given_list,start,curr,result): if start > len(given_list)-1: #print(curr) result.append(curr) return for i in range(start,len(given_list)): self.swap(given_list,start,start+(i-start)) self.permute_util(given_list,start+1,curr+[given_list[start]],result) #print(given_list) self.swap(given_list, start, start + (i - start)) def swap(self,nums,index1,index2): temp = nums[index1] nums[index1] = nums[index2] nums[index2] = temp ob1 = Solution() print(ob1.permute([1,2,3,4]))
입력
[1,2,3,4]
출력
[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,3,2],[1,4,2,3],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1],[2,4,1,3],[3,2,1,4],[3,2,4,1],[3,1,2,4],[3,1,4,2],[3,4,1,2],[3,4,2,1],[4,2,3,1],[4,2,1,3],[4,3,2,1],[4,3,1,2],[4,1,3,2],[4,1,2,3]]