Heap의 알고리즘은 Go에서 어떻게 모든 순열을 생성할 수 있나요?

Go에서 모든 순열 생성

소개

목록의 가능한 모든 순열 생성 요소는 프로그래밍에서 흔히 발생하는 문제입니다. 이 기사에서는 모든 순열을 생성하는 가장 간단한 접근 방식 중 하나인 Heap의 알고리즘을 살펴봅니다. 생성된 순열은 사전순으로 정렬되지 않습니다.

힙의 알고리즘

힙의 알고리즘은 교환할 요소 쌍을 선택하여 각 순열을 생성합니다. 배열에 요소가 하나만 있는 기본 사례로 시작합니다. 더 큰 배열의 경우 요소를 반복하면서 쌍을 교환하여 재귀적으로 새로운 순열을 생성합니다.

Go 구현

아래는 Heap 알고리즘의 Go 구현입니다.

func permutations(arr []int) [][]int {
    res := [][]int{}
    helper := func(arr []int, n int) {
        if n == 1 {
            tmp := make([]int, len(arr))
            copy(tmp, arr)
            res = append(res, tmp)
        } else {
            for i := 0; i < n; i++ {
                helper(arr, n-1)
                if n%2 == 1 {
                    tmp := arr[i]
                    arr[i] = arr[n-1]
                    arr[n-1] = tmp
                } else {
                    tmp := arr[0]
                    arr[0] = arr[n-1]
                    arr[n-1] = tmp
                }
            }
        }
    }
    helper(arr, len(arr))
    return res
}

사용법 예

순열 기능을 사용하는 방법의 예는 다음과 같습니다.

arr := []int{1, 2, 3}
fmt.Println(permutations(arr))

출력

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

추가의 참고

• 순열이 생성되지만 사전순으로 정렬되지는 않습니다.
• 사전순 정렬의 경우 계승 번호 시스템을 사용하여 순열을 생성하는 것이 좋습니다.

위 내용은 Heap의 알고리즘은 Go에서 어떻게 모든 순열을 생성할 수 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!