46 순열

46 순열

문제

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

조건

$1 \le nums.length \le 6$
$-10 \le nums[i] \le 10$
All the integers of nums are unique.

예제

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

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

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

해결

1st

1 생각

순열이란?
- 순서 있는 집합을 다른 순서로 뒤섞는 연산
- n개의 원소에 대해 $n! = n \times (n - 1) \times (n - 2) \times \dotsb \times 2 \times 1$ 경우의 수

# 4자리 수: 4 x 3 x 2 x 1 = 24 경우의 수
2 3 4
2 4 3
3 2 4
3 4 2
4 2 3
4 3 2

1 3 4
1 4 3
3 1 4
3 4 1
4 1 3
4 3 1

1 2 4
1 4 2
2 1 4
2 4 1
4 1 2
4 2 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

배열의 숫자는 같은데 인덱스만 다양하게 바꿔야 하는 상황
- 근데 사실 어떻게 바꿔야 할지 모르겠다
- 개념을 모르나? 순서 있는 집합을 다른 순서로 뒤섞는 연산임을 안다
- 규칙을 모르나? 위에처럼 규칙에 따라 나열할 수 있다
- 근데 개념과 패턴을 코드로 못 바꾼다?
  - 개념에 대한 이해가 부족하거나
  - 규칙에 대한 이해가 부족하거나
  - 개념이나 규칙이 아닌 다른 무엇에 대한 이해가 필요하거나
    - 개념과 규칙 외에, 개념과 규칙을 개발 언어로 바꾸고 최적화하는 능력은 별개
    - 어떻게 보면 창조의 영역 같은데, 이걸 어떻게 잘할 수 있을까?(#TODO)
- 일단 지금으로 봐서는 규칙에 대한 이해가 부족한 거 같다.
- 모를 땐? 검색

# source: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
def do_permutation(nums, nums_len):
    # 1. 1 6 7 3 5 4 2
    idx1 = nums_len - 1
    while idx1 > 0 and nums[idx1 - 1] >= nums[idx1]:
        idx1 -= 1

    # 2. idx1이 0보다 작으면 모두 내림차순으로 종료 케이스
    if idx1 <= 0:
        return False
    
    # 3. 찾아낸 오름차순인 수보다 큰 수가 우측에 있으면, `다음 내림차순` 준비
    idx2 = nums_len - 1
    while nums[idx2] <= nums[idx1 - 1]:
        idx2 -= 1

    # 다음 내림차순 위한 치환
    # 4. 1 6 7 4 5 3 2
    nums[idx1 - 1], nums[idx2] = nums[idx2], nums[idx1 - 1]
    
    # 다음 내림차순이 시작된 후 idx1과 idx2 사이의 숫자는 다시 정순으로 정렬되어야 다음 순열이 진행되므로, 뒤집는다
    # 5. 1 6 7 4 2 3 5
    idx2 = nums_len - 1
    while idx1 < idx2:
        nums[idx1], nums[idx2] = nums[idx2], nums[idx1]
        idx1 += 1
        idx2 -= 1

    return True

어떻게 위의 규칙을 알고리즘화 했을까?

`# 1. 1 6 7 3 5 4 2`

첫번째 while문의 목적: 오름차순인 인덱스(nums[4] = 3) 찾기

`# 2. 종료 케이스`

오름차순으로 정렬된 숫자를 내림차순 순열로 바꾸는 과정
따라서 원래는 가장 큰 우측의 수보다 좌측의 모든 수들이 크다면, 더 이상 진행할 순열이 없다는 의미이므로 종료

`# 3. 다음 내림차순 수의 인덱스 찾기`

두번째 while문의 목적: 다음 내림차순 순열을 만들기 위한 다음 수의 인덱스 찾기
내림차순이 아닌 인덱스의 수보다 큰 수의 인덱스(nums[6] = 4) 찾는다

`# 4. 1 6 7 4 5 3 2`

내림차순이 아닌 인덱스의 수를 다음 내림차순 순열의 수와 치환한다

`# 5. 1 6 7 4 2 3 5`

핵심인 부분인 거 같은데 너무 간단하게 되어 있다. 정렬의 이해가 선행되어야 할 것 같다
위에서 nums[4]와 nums[6]을 바꾼 것은 다음 내림차순 순열 시작을 의미한다
- 그 말은 1 6 7 3 5 4 2에서 5 4 2는 이미 역순 정렬이 끝났음을 의미
- 1 6 7 4 5 3 2에서 2와 5를 치환하는 것만으로 정순 정렬이 됨을 의미
- 5 4 3 2 1에서 5와 1을 치환하고, 4와 2를 치환하면 1 2 3 4 5가 되는 것과 같다

정리

결국 코드 자체는 발견한 규칙과 마찬가지다. 오름차순에서 시작해서 내림차순으로 끝난다
오름차순인 수를 내림차순으로 바꿔 나간다
- 오름차순인 부분을 찾고,
- 내림차순 수로 바꾸고,
- 나머지 수를 정순으로 만들어 다시 내림차순으로 바꿔 나간다
세 while문을 정리하자면
- 첫번째 while문: 오름차순인 부분의 인덱스를 찾고
- 두번째 while문: 다음 내림차순이 될 수를 찾는다
- 세번째 while문: 다음 내림차순이 된 수 다음 이미 역순 정렬되어 있는 수를 정순 정렬로 바꾼다
개발과 코딩에 익숙해진다는 건, 규칙을 컴퓨터에 맞게 코드를 쓸 수 있는 능력이란 건 알고 있었는데, 새삼 새롭게 느껴진다. 저 세 while문은 규칙을 컴퓨터에 맞게 필요 최소한으로 구현해 냈다. 설명을 코드로 바꾸는 능력은 어떻게 기를 수 있을까?

1 코드

def permute(self, nums: List[int]) -> List[List[int]]:
    nums = sorted(nums)
    ans = [nums[:]]
    def do_permutation(nums_curr, nums_len):
        # 1. 1 6 7 3 5 4 2
        idx1 = nums_len - 1
        while idx1 > 0 and nums_curr[idx1 - 1] >= nums_curr[idx1]:
            idx1 -= 1

        # 2. 종료 케이스
        if idx1 <= 0:
            return False

        # 3. 
        idx2 = nums_len - 1
        while nums_curr[idx2] <= nums_curr[idx1 - 1]:
            idx2 -= 1

        # 4. 1 6 7 4 5 3 2
        nums_curr[idx1 - 1], nums_curr[idx2] = nums_curr[idx2], nums_curr[idx1 - 1]

        # 5. 1 6 7 4 2 3 5
        idx2 = nums_len - 1
        while idx1 < idx2:
            nums_curr[idx1], nums_curr[idx2] = nums_curr[idx2], nums_curr[idx1]
            idx1 += 1
            idx2 -= 1
            
        ans.append(nums_curr[:])
        
        return True
    
    
    while result := do_permutation(nums, len(nums)):
        continue
    
    return ans

1 결과: 성공

25 / 25 test cases passed.
Status: Accepted
Runtime: 40 ms
Memory Usage: 14.2 MB

2nd

2 생각

DFS로 구현을 해보자
모든 경우의 수를 조합해 나가면 되지 않을까? 그러면 어떻게 모든 경우의 수를 DFS로 조합할 수 있을까?

DFS?

Depth First Search, 깊이 우선 탐색
방식은?
- 자료 구조를 그래프로 볼 때
- 가장 말단의 노드(리프 노드)까지 도달하여 종료 조건을 만나 백 트래킹할 때까지
- 재귀적으로 함수를 호출하여
- 원하는 데이터를 탐색하는 방법

경우의 수?

DFS로 경우의 수를 만든다면 아래와 같이 자기 자신을 제외한 수가 자식 노드로 붙어 가는 형식이 될 것이다.

depth
1       [  1,             2,             3  ]
2       [2]  [3]        [1]  [3]     [1]  [2]
3       [3]  [2]        [3]  [1]     [2]  [1]
        종료 종료       종료 종료     종료 종료

종료 지점은?
- 전달된 배열 nums([1, 2, 3])의 길이와 depth가 같아지는 경우

2 코드

def second(self, nums: List[int]) -> List[List[int]]:
    ans = []
    nums_len = len(nums)
    '''
    nums: 원본 배열. 요소를 계속 붙여 나가야 하므로 계속 전달
    permutaion: 순열을 만들어 나갈 배열
    depth: 백 트래킹 조건
    '''
    def dfs(nums, permutaion, depth):
        # 배열의 길이만큰 깊어지면 종료
        if depth == nums_len:
            ans.append(permutaion)
            return

        for num in nums:
            if not num in permutaion:
                """
                permutaion.append(num) (X) 
                    - append를 하면 기존 permutation에 추가되고, 유지된다. 
                    - 리프 노드에서 백 트래킹 후 기존 permutation 배열이 있어야 하므로, 전달 시에는 이전 배열 유지 위해 + 연산자 사용
                """
                dfs(nums, permutaion + [num], depth + 1)

    dfs(nums, [], 0)

    return ans

2 결과: 성공

25 / 25 test cases passed.
Status: Accepted
Runtime: 32 ms
Memory Usage: 14.3 MB

3rd

3 itertools

itertools에는 permuation과 combination 등 유용한 함수들 있다
permuation의 소스 코드는 링크 참조

3 코드

def third(self, nums: List[int]) -> List[List[int]]:
    return list(map(list, itertools.permutations(nums)))

회고

dfs가 더 빠른 것 같지만, 함수 콜 스택이 많이 쌓이면 안 좋다고 들었던 거 같다
- Efficiency: recursion vs loop
알고리즘 공부를 통해 배울 것은 결국 아래 세 가지일 것 같다
- 문제에 해당하는 샘플들을 통해 규칙을 찾고,
- 규칙을 사람의 말로 설명하고,
- 그 설명을 컴퓨터에 맞는 코드로 변환