【題目】
給出一個集合{1，2，3}，求解該集合的全排列并列印。
全排列問題的遞歸算法（Perm）
【算法思想】
設R={r1,r2,…,rn}是要進行排列的n個元素，Ri=R{ri}。
集合X中元素的全排列記為Perm(X)。
(ri)Perm(X)表示在全排列Perm(X)的每一個排列前加上字首得到的排列。
R的全排列可歸納定義如下：
當n=1時，Perm(R）=(r），其中r是集合R中唯一的元素；
當n>1時，Perm(R）由(r1)Perm(R1)，(r2)Perm(R2)，…，(rn)Perm(Rn)構成。
【算法解讀】
由Perm(X)=(r1)Perm(R1)，(r2)Perm(R2)，…，(rn)Perm(Rn)
一直向下分解（即不斷化簡Perm(R1),Perm(R2),…,Perm(Rn))直到n=1,
化到R為Perm(R）中唯一的元素。
規律：化簡的過程即模拟了我們不斷控制位置不變的元素變多的排列規則，也即使得能夠自由排列的元素個數越來越小的過程。
【算法排列圖解】以{1，2，3}為例
以上即是以算法的角度了解，略帶晦澀，看後讓人不容易想象到代碼怎麼寫，我們可以換個角度了解：
【我們的思路】
從上圖我們可以看出一切的精髓在于這條藍線的移動以及移動區，非移動區
那麼，要怎樣才能使得藍線移動呢？？？
我們發現，要點在于：
（1）邊界元素的位置，也即第一個可以任意排序的元素的位置。
（2）移動區和非移動區暗示着我們會有一對以上的坐标變量
對于{1，2，3}的第一個分支來說，這個元素為1.
那麼，我們給他注明下标：
這時，我們有一個問題：如何能讓上圖的1跑到非移動區呢？？？
要點在于：一開始讓i與k指向相同的元素，依次讓i指向的元素與k指向的元素交換位置，然後i指向下一個元素，k指向元素再與之交換。我們進行交換操作的範圍就是在移動區内，随着逐層遞歸進行，移動區元素個數逐漸為0，即i==j，這時，我們再将非移動區的元素列印出來，這樣就逐漸實作了遞歸周遊。
代碼如下：
//交換元素位置函數
void Swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
void Perm(int *br, int i, int j)
{
if (i == j)
{
for (int m = 0; m <= i; ++m)
{
cout << br[m] << " ";
}
cout << endl;
}
else
{
for (int k = i; k <= j; ++k)
{
Swap(br[i], br[k]);
Perm(br, i + 1, j);
//遞歸回來時還原到本層的初始模樣，
//以便于下一次i++繼續做遞歸時出發點是一樣的。
Swap(br[i], br[k]);
}
}
}
int main()
{
int ar[] = { 1,2,3 };
Perm(ar, 0, 2);
return 0;
}
當我們遞歸到底之後，在傳回過程中，還需要把元素位置還原。以便以相同的出發點向不同方向遞歸。
以上分析可以幫助了解Perm算法的思想，一句簡單的結題口訣就是：
在遞歸的過程中将整組數中的所有的數分别與第一個數交換，這樣就總是在處理後n-1個數的全排列，直到n=0。