学步园

前面的文章曾用非递归的方法实现过全排列。本文用递归的方法实现全排列。（摘自计算机算法设计与分析）

设R={r₁,r₂,...,r_n}是要进行排列的n个元素，R_i=R-{r_i}。集合X中元素的全排列记为Perm(X)。(r_i)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀r_i得到的全排列。R的全排列可归纳定义如下：

当n=1时，Perm(R)=(r)，其中r是集合R中唯一的元素。

当n>1时，Perm(R)由(r₁)Perm(R₁),(r₂)Perm(R₂),...,(r_n)Perm(R_n)构成。

#include <iostream><br /> using namespace std;</p> <p>template <typename T><br /> void perm(T list[], int begin, int end)<br /> {<br /> int i;<br /> if(begin==end)<br /> {<br /> for (i=0;i<=end;++i)<br /> {<br /> cout << list[i] << " " ;<br /> }<br /> cout << endl;<br /> }<br /> else<br /> {<br /> for (i=begin;i<=end;++i)<br /> {<br /> swap(list[begin],list[i]);<br /> perm(list,begin+1,end);<br /> swap(list[begin],list[i]);<br /> }<br /> }<br /> }</p> <p>template <typename T><br /> void swap(T& a,T& b)<br /> {<br /> T tmp;<br /> tmp=a;<br /> a=b;<br /> b=tmp;<br /> }</p> <p>int main()<br /> {<br /> int a[]={1,2,3,4};<br /> perm(a,0,3);<br /> return 0;<br /> }