logo

TechCodeview

순열 생성을 위한 힙 알고리즘

힙의 알고리즘 n 객체의 모든 순열을 생성하는 데 사용됩니다. 아이디어는 다른 요소를 방해하지 않고 교환할 요소 쌍을 선택하여 이전 순열에서 각 순열을 생성하는 것입니다. n-2 강요. 
다음은 n개의 주어진 숫자의 모든 순열을 생성하는 그림입니다.
예:  

  Input:   1 2 3   Output:   1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1

연산: 



  1. 알고리즘은 (n-1)을 생성합니다! 마지막 요소에 인접한 첫 번째 n-1 요소의 순열. 그러면 마지막 요소로 끝나는 모든 순열이 생성됩니다.
  2. n이 홀수이면 첫 번째 요소와 마지막 요소를 바꾸고, n이 짝수이면 i를 바꿉니다.일요소(i는 0부터 시작하는 카운터)와 마지막 요소를 선택하고 i가 n보다 작을 때까지 위 알고리즘을 반복합니다.
  3. 각 반복에서 알고리즘은 현재 마지막 요소로 끝나는 모든 순열을 생성합니다.

구현:   

C++ 
// C++ program to print all permutations using // Heap's algorithm #include    using namespace std; // Prints the array void printArr(int a[] int n) {  for (int i = 0; i < n; i++)  cout << a[i] << ' ';  printf('n'); } // Generating permutation using Heap Algorithm void heapPermutation(int a[] int size int n) {  // if size becomes 1 then prints the obtained  // permutation  if (size == 1) {  printArr(a n);  return;  }  for (int i = 0; i < size; i++) {  heapPermutation(a size - 1 n);  // if size is odd swap 0th i.e (first) and   // (size-1)th i.e (last) element  if (size % 2 == 1)  swap(a[0] a[size - 1]);  // If size is even swap ith and   // (size-1)th i.e (last) element  else  swap(a[i] a[size - 1]);  } } // Driver code int main() {  int a[] = { 1 2 3 };  int n = sizeof a / sizeof a[0];  heapPermutation(a n n);  return 0; }
Java 
// Java program to print all permutations using // Heap's algorithm import java.io.*; class HeapAlgo {  // Prints the array  void printArr(int a[] int n)  {  for (int i = 0; i < n; i++)  System.out.print(a[i] + ' ');  System.out.println();  }  // Generating permutation using Heap Algorithm  void heapPermutation(int a[] int size int n)  {  // if size becomes 1 then prints the obtained  // permutation  if (size == 1)  printArr(a n);  for (int i = 0; i < size; i++) {  heapPermutation(a size - 1 n);  // if size is odd swap 0th i.e (first) and  // (size-1)th i.e (last) element  if (size % 2 == 1) {  int temp = a[0];  a[0] = a[size - 1];  a[size - 1] = temp;  }  // If size is even swap ith   // and (size-1)th i.e last element  else {  int temp = a[i];  a[i] = a[size - 1];  a[size - 1] = temp;  }  }  }  // Driver code  public static void main(String args[])  {  HeapAlgo obj = new HeapAlgo();  int a[] = { 1 2 3 };  obj.heapPermutation(a a.length a.length);  } } // This code has been contributed by Amit Khandelwal.
Python3 
# Python program to print all permutations using # Heap's algorithm # Generating permutation using Heap Algorithm def heapPermutation(a size): # if size becomes 1 then prints the obtained # permutation if size == 1: print(a) return for i in range(size): heapPermutation(a size-1) # if size is odd swap 0th i.e (first) # and (size-1)th i.e (last) element # else If size is even swap ith # and (size-1)th i.e (last) element if size & 1: a[0] a[size-1] = a[size-1] a[0] else: a[i] a[size-1] = a[size-1] a[i] # Driver code a = [1 2 3] n = len(a) heapPermutation(a n) # This code is contributed by ankush_953 # This code was cleaned up to by more pythonic by glubs9
C# 
// C# program to print all permutations using // Heap's algorithm using System; public class GFG {  // Prints the array  static void printArr(int[] a int n)  {  for (int i = 0; i < n; i++)  Console.Write(a[i] + ' ');  Console.WriteLine();  }  // Generating permutation using Heap Algorithm  static void heapPermutation(int[] a int size int n)  {  // if size becomes 1 then prints the obtained  // permutation  if (size == 1)  printArr(a n);  for (int i = 0; i < size; i++) {  heapPermutation(a size - 1 n);  // if size is odd swap 0th i.e (first) and  // (size-1)th i.e (last) element  if (size % 2 == 1) {  int temp = a[0];  a[0] = a[size - 1];  a[size - 1] = temp;  }  // If size is even swap ith and  // (size-1)th i.e (last) element  else {  int temp = a[i];  a[i] = a[size - 1];  a[size - 1] = temp;  }  }  }  // Driver code  public static void Main()  {  int[] a = { 1 2 3 };  heapPermutation(a a.Length a.Length);  } } /* This Java code is contributed by 29AjayKumar*/
JavaScript 
<script> // JavaScript program to print all permutations using // Heap's algorithm // Prints the array function printArr(an) {  document.write(a.join(' ')+'  
');   } // Generating permutation using Heap Algorithm function heapPermutation(asizen) {  // if size becomes 1 then prints the obtained  // permutation  if (size == 1)  printArr(a n);    for (let i = 0; i < size; i++) {  heapPermutation(a size - 1 n);    // if size is odd swap 0th i.e (first) and  // (size-1)th i.e (last) element  if (size % 2 == 1) {  let temp = a[0];  a[0] = a[size - 1];  a[size - 1] = temp;  }    // If size is even swap ith  // and (size-1)th i.e last element  else {  let temp = a[i];  a[i] = a[size - 1];  a[size - 1] = temp;  }  } } // Driver code let a=[1 2 3]; heapPermutation(a a.length a.length); // This code is contributed by rag2127 </script>

산출 
1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1

시간 복잡도: O(N*N!) 여기서 N은 주어진 배열의 크기입니다.
보조 공간: 크기가 N인 재귀 스택 공간의 경우 O(N)입니다.

참고자료:  
1. 'https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3