Permutations

Q: 입력에 중복 항목이 있을 때 순열을 어떻게 생성하나요?

값을 정렬하고, 각 위치에서 앞의 값과 같으며 앞의 값이 아직 사용되지 않은 경우 해당 값을 건너뜁니다: i > 0 , values[i] == values[i-1] 및 !used[i-1] . 이렇게 하면 같은 값은 원래 순서대로 배치되므로 각 고유한 순서는 한 번만 만들어집니다.

보통백트래킹

+10

서로 다른 정수로 이루어진 목록 nums가 주어집니다. 각 값이 정확히 한 번씩 사용된 목록인 모든 순열을 반환하세요. 값이 n개라면 순열은 n!개입니다. 사전순으로 나열하세요. 두 순열을 위치별로 비교하고 처음으로 다른 위치의 값으로 순서를 정합니다. [1, 2, 3]의 경우 [1, 2, 3]이 가장 먼저 오고 [3, 2, 1]이 마지막에 옵니다.

함수

permute(nums: integer-array) → integer-2d-array

numsinteger-array: 값은 모두 서로 다르며, 순서는 상관없습니다
반환값integer-2d-array: 값의 모든 순서를 사전식 순서로 나열

제약 조건

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
nums의 모든 값은 서로 다릅니다.
nums는 어떤 순서로든 올 수 있습니다.

예제

입력: nums = [3, 1, 2]
출력: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
설명: 세 개의 값은 3! = 6개의 순서가 있습니다. 정렬하면 값은 1, 2, 3이므로 1로 시작하는 순서가 먼저 오고, 두 번째 위치에서 2가 3보다 작기 때문에 [1, 2, 3]이 [1, 3, 2]보다 먼저 옵니다. 입력의 순서는 중요하지 않습니다.

입력: nums = [2, -1]
출력: [[-1, 2], [2, -1]]
설명: 두 값은 두 가지 순서로 쓸 수 있습니다. [-1, 2]가 먼저 오는데, -1이 2보다 작기 때문입니다.

제출 시 숨은 테스트 +13개

후속 질문

주어진 순서가 있을 때, O(n) 시간과 O(1)의 추가 공간으로 제자리에서 사전식 순서의 다음 순서를 만들어 낼 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

서로 다른 n개의 값으로 이루어진 목록에는 n!개의 순서가 있으며, 값이 여섯 개라면 720개입니다. 답에는 그 순서를 모두 나열해야 하므로 작업량은 적어도 n × n!입니다. 과제는 각 순서를 한 번씩 만들고 사전식 순서로 출력하는 것입니다. 정렬된 값들을 대상으로 백트래킹하면서 사용하지 않은 값 중 가장 작은 값을 항상 먼저 시도하면 두 가지를 동시에 해낼 수 있습니다.

모든 빈칸에 삽입한 다음 정렬하세요

핵심 아이디어

순열을 한 번에 값 하나씩 늘려 갑니다. 값이 없을 때는 빈 목록이라는 순열 하나가 있습니다. 값 3을 순열 [1, 2]에 추가하려면 세 개의 틈 각각에 넣습니다. [3, 1, 2], [1, 3, 2], [1, 2, 3]입니다. 가지고 있는 모든 순열에 대해 이 작업을 하면 k개 값의 순열이 k+1개 값의 순열이 됩니다.

k+1개 값의 모든 순열은 정확히 한 번씩 만들어집니다. 가장 최근에 추가한 값을 순열에서 빼면 그 순열이 만들어져 나온 순열 하나를 얻고, 가장 최근 값의 위치가 틈을 나타냅니다. 따라서 개수는 1, 2, 6, 24가 되고, 값이 n개면 순열은 n!개입니다.

하지만 순열은 필요한 순서대로 나오지 않습니다. [1, 2, 3]의 경우 처음 만들어지는 순열은 [3, 2, 1]이므로, 마지막에 위치별로 비교하는 정렬을 해야 합니다. 이 정렬이 가장 비용이 많이 드는 부분입니다. n!개의 순열을 정렬하려면 약 n! × log(n!)번의 비교가 필요하고, 각 비교에서는 최대 n개의 값을 읽습니다. 값이 여섯 개라면 대략 720 × 9.5 × 6, 즉 약 41,000번 읽습니다. 또한 이 방법은 다음 세대를 만드는 동안 순열의 한 세대 전체를 메모리에 보관합니다.

알고리즘

빈 순열 하나를 담은 목록으로 시작합니다.
nums의 각 값에 대해 새 목록을 만듭니다. 지금까지의 각 순열과 0부터 해당 순열의 길이까지의 각 삽입 위치에 대해, 그 위치에 값을 삽입한 순열을 복사합니다.
기존 목록을 새 목록으로 바꿉니다.
순열을 각 위치별로 정렬한 다음 반환합니다.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

사용 여부 배열을 이용한 백트래킹

핵심 아이디어

n개의 슬롯을 왼쪽에서 오른쪽으로 채웁니다. 첫 번째 슬롯에는 n개의 후보가 있고, 두 번째 슬롯에는 n-1개가 있으며, 이런 식으로 이어집니다. 여기서 n!이 나옵니다. 이 선택 과정을 트리로 그려 보세요. 루트는 비어 있는 경로이고, 각 간선은 값 하나를 더 배치하며, 깊이가 n인 각 리프는 완성된 순열 하나입니다. 정렬된 값 1, 2, 3의 경우 루트에는 자식 [1], [2], [3]이 있습니다. [1]에는 자식 [1, 2]와 [1, 3]이 있으며, 각 자식에는 리프가 하나씩 있습니다.

백트래킹은 하나의 공유 path와 각 값에 대한 used 플래그를 사용해 이 트리를 탐색합니다. 각 노드에서 값들을 반복하면서 이미 사용된 값은 건너뜁니다. 사용 가능한 각 값에 대해 선택하고(사용됨으로 표시하고 추가), 탐색한 다음(한 단계 더 깊이 재귀 호출), 선택을 취소합니다(값을 제거하고 사용 가능 상태로 표시). 선택 취소 단계는 반복문이 시작되기 전의 상태를 정확히 복원하므로, 다음 값은 같은 노드에서 시도됩니다. 길이가 n인 경로는 리프입니다. 복사본을 기록하고 반환합니다.

순서는 저절로 올바르게 만들어집니다. 반복문은 사용 가능한 값 중 가장 작은 값부터 시도하고, 탐색은 접두부가 바뀌기 전에 해당 접두부로 시작하는 모든 순열을 완성합니다. 따라서 1로 시작하는 모든 순열이 2로 시작하는 순열보다 먼저 나오고, 그중에서도 [1, 2, ...]가 [1, 3, ...]보다 먼저 나옵니다. 이것이 사전식 순서입니다. 또한 nums를 먼저 정렬하는 이유이기도 합니다. 반복문은 인덱스 순서로 진행하므로 인덱스가 값의 순서와 일치해야 합니다.

트리에는 약 e × n!개의 노드가 있고(e는 약 2.72), 각 노드에서 n번 반복문을 실행하므로 시간 복잡도는 O(n × n!)입니다. 이는 답의 크기와 같은 차수입니다. 출력 외에 경로, 플래그, 호출 스택은 각각 최대 n개의 항목을 담습니다.

알고리즘

값을 정렬하고 n개의 false 플래그가 있는 used 배열을 만듭니다.
explore()를 작성합니다. path에 값이 n개 들어 있으면 복사본을 결과에 추가하고 반환합니다.
그렇지 않으면 값이 사용되지 않은 0부터 n-1까지의 각 인덱스 i에 대해 사용됨으로 표시하고 values[i]를 추가한 다음(선택), explore()를 호출하고(탐색), 해당 값을 제거한 뒤 사용되지 않음으로 표시합니다(선택 취소).
explore()를 한 번 호출하고 결과를 반환합니다.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

함정과 경계 사례

백트래킹 버그는 거의 항상 복원되지 않은 상태이거나, 실수로 공유된 상태 때문에 발생합니다.

path의 복사본이 아니라 path 자체를 기록하는 경우입니다. n!개의 항목이 모두 같은 목록을 가리키게 되고, 탐색이 끝나면 그 목록은 비어 있습니다.
선택을 절반만 되돌리는 경우입니다. 값을 제거했지만 used[i]를 설정된 상태로 남겨 두면, 이후 분기에서 그 값은 다시 나타나지 않으며 n!개보다 적은 순열을 반환하게 됩니다.
먼저 nums를 정렬하지 않는 경우입니다. 탐색은 여전히 모든 순열을 찾지만 입력 순서대로 나열하므로, 입력 [3, 1, 2]가 첫 번째로 나열됩니다.
최종 정렬 없이 스왑 방법(각 이후 위치의 값과 nums[start]를 스왑하고, 재귀 호출한 다음, 다시 스왑)을 사용하는 경우입니다. 모든 n!개의 순열을 찾지만, [1, 2, 3]에 대해 [3, 1, 2]보다 [3, 2, 1]을 먼저 나열합니다.
path를 검색해 사용된 값을 확인하는 경우입니다. 여기서는 값이 서로 다르기 때문에 작동할 뿐이며, 매 단계마다 n의 비용이 듭니다. 인덱스마다 플래그를 두면 O(1)의 비용으로 값이 반복될 때도 작동합니다.

자주 묻는 질문4

서로 다른 n개의 원소로 이루어진 리스트에는 순열이 몇 개 있나요?

n!, n 팩토리얼이라고 읽습니다. 첫 번째 위치에는 n개의 선택지가 있고, 두 번째 위치에는 n-1개가 있으며, 마지막 위치에는 하나가 남을 때까지 줄어듭니다. 이를 모두 곱합니다. 값이 세 개이면 순서가 6가지이고, 여섯 개이면 720가지이며, 열 개이면 벌써 3,628,800가지입니다. 그래서 순열 문제에서는 n을 작게 유지합니다.

모든 순열을 생성하는 시간 복잡도는 얼마인가요?

O(n × n!). n!개의 순서가 있고 각각을 모두 적는 데 n단계가 걸리므로, 모든 순서를 반환해야 한다면 어떤 방법도 이보다 더 효율적일 수 없습니다. 백트래킹은 이 경계에 도달하며, 출력 공간 외에도 현재 경로, 사용 여부 플래그 및 재귀를 위해 O(n) 공간이 필요합니다.

백트래킹은 왜 사전식 순서로 순열을 생성하나요?

사용 가능한 값 중 가장 작은 값부터 시도하는 깊이 우선 탐색입니다. 다음 접두사로 넘어가기 전에 주어진 접두사로 시작하는 모든 순서를 끝까지 탐색하고, 접두사는 작은 것부터 큰 것 순으로 시도합니다. 탐색을 시작하기 전에 입력을 정렬하면 사전에서 단어를 정렬하는 방식과 일치합니다.

입력에 중복 항목이 있을 때 순열을 어떻게 생성하나요?

값을 정렬하고, 각 위치에서 앞의 값과 같으며 앞의 값이 아직 사용되지 않은 경우 해당 값을 건너뜁니다: i > 0, values[i] == values[i-1] 및 !used[i-1]. 이렇게 하면 같은 값은 원래 순서대로 배치되므로 각 고유한 순서는 한 번만 만들어집니다.

Python

def permute(nums):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

nums = [3, 1, 2]

기대값

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]