程式扎記: [ Algorithm ] Heap's algorithm for Permutation

標籤

2016年10月22日 星期六

[ Algorithm ] Heap's algorithm for Permutation

Source From Here 
Preface 
Heap's algorithm generates all possible permutations of N objects. It was first proposed by B. R. Heap in 1963.[1] The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other N−2 elements are not disturbed. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer. 

Details of the algorithm 
Suppose we have a permutation containing N different elements. Heap found a systematic method for choosing at each step a pair of elements to switch, in order to produce every possible permutation of these elements exactly once. Let us describe Heap's method in a recursive way. First we set a counter i to 0. Now we perform the following steps repeatedly until i is equal to N. We use the algorithm to generate the (N − 1)! permutations of the first N − 1 elements, adjoining the last element to each of these. This generates all of the permutations that end with the last element. Then if N is odd, we switch the first element and the last one, while if N is even we can switch the i th element and the last one (there is no difference between N even and odd in the first iteration). We add one to the counter i and repeat. In each iteration, the algorithm will produce all of the permutations that end with the element that has just been moved to the "last" position. The following pseudocode outputs all permutations of a data array of length N
- Recursive Pseudo Code 
  1. procedure generate(n : integer, A : array of any):  
  2.     if n = 1 then  
  3.           output(A)  
  4.     else  
  5.         i := 0  
  6.         while True do  
  7.             generate(n - 1, A)  
  8.             if i = (n - 1) then  
  9.                 break  
  10.             end if  
  11.             if n is even then  
  12.                 swap(A[i], A[n-1])  
  13.             else  
  14.                 swap(A[0], A[n-1])  
  15.             end if  
  16.             i := i + 1  
  17.         end while  
  18.     end if  
One can also write the algorithm in a non-recursive format. 
  1. procedure generate(n : integer, A : array of any):  
  2.     c : array of int  
  3.   
  4.     for i := 0; i < n; i += 1 do  
  5.         c[i] := 0  
  6.     end for  
  7.   
  8.     output(A)  
  9.     i := 1  
  10.     while i < n do  
  11.         if c[i] < i then  
  12.             if i is even then  
  13.                 swap(A[0], A[i])  
  14.             else  
  15.                 swap(A[c[i]], A[i])  
  16.             end if  
  17.             output(A)  
  18.             c[i] += 1  
  19.             i := 1  
  20.         else  
  21.             c[i] := 0  
  22.             i += 1  
  23.         end if  
  24.     end while  
- Java Implementation 
  1. package medium;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5.   
  6. public class permutations {  
  7.     /** 
  8.      * Given a collection of distinct numbers, return all possible permutations. 
  9.      * For example, 
  10.      * [1,2,3] have the following permutations: 
  11.      *  
  12.      * [[1,2,3], 
  13.      * [1,3,2], 
  14.      * [2,1,3], 
  15.      * [2,3,1], 
  16.      * [3,1,2], 
  17.      * [3,2,1]] 
  18.      *  
  19.      * @see 
  20.      *  https://en.wikipedia.org/wiki/Heap%27s_algorithm 
  21.      *  
  22.      * @param nums 
  23.      *  Numbers with distinct values to do permutation 
  24.      *  
  25.      * @return 
  26.      */  
  27.     public static List> permute(int[] nums) {  
  28.         List> permList = new ArrayList>();  
  29.           
  30.         generate(nums.length, nums, permList);  
  31.           
  32.         return permList;  
  33.     }  
  34.       
  35.     public static void generate(int n, int[] nums, List> permList)  
  36.     {  
  37.         if(n==1)  
  38.         {  
  39.             List list = new ArrayList();  
  40.             for(int v:nums) list.add(v);  
  41.             permList.add(list);  
  42.         }  
  43.         else  
  44.         {  
  45.             int i = 0;  
  46.             while(true)  
  47.             {  
  48.                 generate(n-1, nums, permList);  
  49.                 if(i==(n-1)) break;  
  50.                 if(n%2==0// even  
  51.                 {  
  52.                     swap(nums, i, n-1);  
  53.                 }  
  54.                 else  
  55.                 {  
  56.                     swap(nums, 0, n-1);  
  57.                 }  
  58.                 i++;  
  59.             }  
  60.         }  
  61.     }  
  62.       
  63.     public static void swap(int[] nums, int i, int j)  
  64.     {  
  65.         int t = nums[i]; nums[i]=nums[j]; nums[j]=t;  
  66.     }  
  67. }  

Supplement 
leetcode - Permutation

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!