Content deleted Content added
Pengfeituan (talk | contribs) |
Pengfeituan (talk | contribs) No edit summary |
||
Line 1:
Heap's permutation Generation Algorithm is an algorithm for generating permutations. It was first proposed by B. R. Heap in 1963<ref>{{cite journal|last=Heap|first=B. R.|title=Permutations by Interchanges|journal=The Computer Journal|year=1963|volume=6|issue=3|page=293-4|url=http://comjnl.oxfordjournals.org/content/6/3/293.full.pdf}}</ref> . It interchanges positions of elements to generate the next permutation.
== Details of Algorithm ==
Suppose we have a sequence of different characters with a length of N, Heap found that, we can simply interchanges the positions of two elements to get a new permutation output. Let us describe it in a recursive way. If we have got (N-1)! permutation outputs, fixing the last element. Then if N is odd, we can switch the first element and the last one, while N is even we can switch the ith (i is the step number of the cycle, and now it is 1) element and the last one, then we will continue outputting the (N-1)! permutation outputs and switching step for another N-1 times( N times int total). Below is a C/C++ like code, it outputs permutations of a data array of length N.<br>
<code>
void generate(int N,char data[])<br>
Line 12:
{{spaces|8}}swap(data[N%2?1:c],data[N]);<br>
{{spaces|8}}output();<br>
{{spaces|4}}}<br>
}<br>
</code>
== Non-recursive Method ==
We could also use rewrite the algorithm in a non-recursive method.<br>
<code>
void permutation(int N,char data[])<br>
{<br>
{{spaces|4}}int c[N];<br>
{{spaces|4}}memset(c,0,sizeof(c));<br>
{{spaces|4}}int i=0;<br>
{{spaces|4}}while(i<n){<br>
{{spaces|8}}if(c[i]<i){<br>
{{spaces|12}}swap(p[i&1?c[i]:0],p[i]);<br>
{{spaces|12}}c[i]++;<br>
{{spaces|12}}i=1;<br>
{{spaces|12}}output();<br>
{{spaces|8}}}<br>
{{spaces|8}}else c[i++]=0;<br>
{{spaces|4}}}<br>
}<br>
| |||