Heap生成置换的算法-yiteyi-C++库

希普算法 用于生成n个对象的所有置换。其思想是通过选择一对要交换的元素，在不干扰另一个元素的情况下，从之前的排列生成每个排列 n-2 元素。下面是生成n个给定数的所有置换的示例。 例子：

null

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

算法：

算法生成（n-1）！前n-1个元素的排列，与最后一个元素相邻。这将生成以最后一个元素结尾的所有排列。
如果n是奇数，交换第一个和最后一个元素，如果n是偶数，则交换i ^th 元素（i是从0开始的计数器）和最后一个元素，重复上述算法，直到i小于n。
在每次迭代中，算法将产生以当前最后一个元素结尾的所有排列。

实施：

C++

                         // C++ program to print all permutations using                       
                         // Heap's algorithm                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Prints the array                       
                         void                                     printArr(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << a[i] <<                                     " "                                     ;                       
                                                 printf                                     (                                     ""                                     );                       
                         }                       
           
                         // 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                       
                         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(a,n)                       
                         {                       
                                                 document.write(a.join(                                     " "                                     )+                                     "<br>"                                     );                       
                                   
                         }                       
           
                         // Generating permutation using Heap Algorithm                       
                         function                                     heapPermutation(a,size,n)                       
                         {                       
                                                 // 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 32 1 33 1 21 3 22 3 13 2 1

参考资料： 1. “https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 本文由 拉胡尔·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章