Heap's algorithm

From 탱이의 잡동사니
Jump to: navigation, search

Overview

Heap's algorithm 내용 정리.

Basic

모든 조합가능한 아이템의 목록을 나타내는 알고리즘 중의 하나이다.

Example

Go

package main
 
import "fmt"
 
 
func permutations(arr []int)[][]int{
    var helper func([]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
}
 
func main() {
    arr := []int{1, 2, 3, 4}
    for _, perm := range(permutations(arr)){
       fmt.Println(perm)
    }
}

See also