Heap's algorithm

Overview

Heap's algorithm 내용 정리.

Basic

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

Example

Go

<source lang=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)
   }

} </source>

See also

• https://en.wikipedia.org/wiki/Heap%27s_algorithm