排列：從n個元素中任取m個元素，并按照一定的順序進(jìn)行排列，稱為排列；
全排列：當(dāng)n==m時，稱為全排列；
比如：集合{ 1,2,3}的全排列為：
{ 1 2 3}
{ 1 3 2 }
{ 2 1 3 }
{ 2 3 1 }
{ 3 2 1 }
{ 3 1 2 }
我們可以將這個排列問題畫成圖形表示，即排列枚舉樹，比如下圖為{1,2,3}的排列枚舉樹，此樹和我們這里介紹的算法完全一致；
算法思路：
(1)n個元素的全排列=（n-1個元素的全排列）+（另一個元素作為前綴）；
(2)出口：如果只有一個元素的全排列，則說明已經(jīng)排完，則輸出數(shù)組；
(3)不斷將每個元素放作第一個元素，然后將這個元素作為前綴，并將其余元素繼續(xù)全排列，等到出口，出口出去后還需要還原數(shù)組；
這里先把集合中的元素理解為不會出現(xiàn)重復(fù)了，那么實現(xiàn)的方法（C++）如下：
成員管理，互評，文件共享，事務(wù)通知
#include <iostream>
using namespace std;
int sum = 0;//記錄有多少種組合
void Swap(char str[], int a, int b)
{
char temp = str[a];
str[a] = str[b];
str[b] = temp;
}
void Perm(char str[], int begin, int end)
{
if (begin == end)
{
for (int i = 0; i <= end; i++)
{
cout << str[i];
}
cout << endl;
sum++;
return;
}
else
{
for (int j = begin; j <= end; j++)
{
Swap(str, begin, j);
Perm(str, begin + 1, end);
Swap(str, j, begin);
}
}
}
int main()
{
int n;
char c[16];
char tmp;
cin >> n;
tmp = getchar(); // 接受回車
if (1 <= n && n <= 15) {
for (int i = 0; i < n; i++) {
c[i] = getchar();
}
Perm(c, 0, n - 1);
}
cout << sum;
cout << endl;
return 0;
}
實現(xiàn)后效果如下圖：
有重復(fù)元素的排列問題
然后現(xiàn)在的題目要求是排列中的元素是包含相同元素的，給定n以及待排的n個可能重復(fù)的元素。計算輸出n個元素的所有不同排列，因此上面那個算法顯然還是不夠好，因為相同的元素都當(dāng)成不同的元素，因此有了重復(fù)的排列在里面
去掉重復(fù)符號的全排列：在交換之前可以先判斷兩個符號是否相同，不相同才交換，這個時候需要一個判斷符號是否相同的函數(shù)。也就是下面的IsSwap（）；
對122，第一個數(shù)1與第二個數(shù)2交換得到212，然后考慮第一個數(shù)1與第三個數(shù)2交換，此時由于第三個數(shù)等于第二個數(shù)，所以第一個數(shù)不再與第三個數(shù)交換。再考慮212，它的第二個數(shù)與第三個數(shù)交換可以得到解決221。
去掉重復(fù)的規(guī)則：去重的全排列就是從第一個數(shù)字起每個數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。
#include <iostream>
using namespace std;
int sum=0;//記錄有多少種組合
void Swap(char str[], int a, int b)
{
char temp = str[a];
str[a] = str[b];
str[b] = temp;
}
bool IsSwap(char *pchar, int nBegin, int nEnd)
{
for (int i = nBegin; i < nEnd; i++)
if (pchar[i] == pchar[nEnd])
return false;
return true;
}
void Perm(char str[], int begin, int end)
{
if (begin==end)
{
for (int i = 0; i <= end; i++)
{
cout << str[i];
}
cout << endl;
sum++;
return;
}
else
{
for (int j = begin; j <= end; j++)
{
if (IsSwap(str, begin, j))
{
Swap(str, begin, j);
Perm(str, begin + 1, end);
Swap(str, j, begin);
}
}
}
}
int main()
{
int n;
char c[16];
char tmp;
cin >> n;
tmp = getchar(); // 接受回車
if (1 <= n && n <= 15) {
for (int i = 0; i < n; i++) {
c[i] = getchar();
}
Perm(c, 0, n - 1);
}
cout << sum;
cout << endl;
return 0;
}
非遞歸的實現(xiàn)
實現(xiàn)思路：
要考慮全排列的非遞歸實現(xiàn)，先來考慮如何計算字符串的下一個排列。如"1234"的下一個排列就是"1243"。只要對字符串反復(fù)求出下一個排列，全排列的也就迎刃而解了。
如何計算字符串的下一個排列了？來考慮"926520"這個字符串，我們從后向前找第一雙相鄰的遞增數(shù)字，"20"、"52"都是非遞增的，"26 "即滿足要求，稱前一個數(shù)字2為替換數(shù)，替換數(shù)的下標(biāo)稱為替換點，再從后面找一個比替換數(shù)大的最小數(shù)（這個數(shù)必然存在），0、2都不行，5可以，將5和2交換得到"956220"，然后再將替換點后的字符串"6220"顛倒即得到"950226"。
對于像"4321"這種已經(jīng)是最“大”的排列，采用STL中的處理方法，將字符串整個顛倒得到最“小”的排列"1234"并返回false。
//全排列的非遞歸實現(xiàn)
#include <iostream>
using namespace std;
void Swap(char *a, char *b)
{
char t = *a;
*a = *b;
*b = t;
}
//反轉(zhuǎn)區(qū)間
void Reverse(char *a, char *b)
{
while (a < b)
Swap(a++, b--);
}
//下一個排列
bool Next_permutation(char a[])
{
char *pEnd = a + strlen(a);
if (a == pEnd)
return false;
char *p, *q, *pFind;
pEnd--;
p = pEnd;
while (p != a)
{
q = p;
--p;
if (*p < *q) //找降序的相鄰2數(shù),前一個數(shù)即替換數(shù)
{
//從后向前找比替換點大的第一個數(shù)
pFind = pEnd;
while (*pFind <= *p)
--pFind;
//替換
Swap(pFind, p);
//替換點后的數(shù)全部反轉(zhuǎn)
Reverse(q, pEnd);
return true;
}
}
Reverse(p, pEnd);//如果沒有下一個排列,全部反轉(zhuǎn)后返回true
return false;
}
int QsortCmp(const void *pa, const void *pb)
{
return *(char*)pa - *(char*)pb;
}
int main()
{
int sum = 0;
char szTextStr[16];
cin >> szTextStr;
char tmp = getchar(); // 接受回車
//加上排序
qsort(szTextStr, strlen(szTextStr), sizeof(szTextStr[0]), QsortCmp);
int i = 1;
cout << endl << endl << endl;
do{
cout<<szTextStr<<endl;
sum++;
} while (Next_permutation(szTextStr));
cout << sum<<endl;
return 0;
}
總結(jié)：
排列在筆試面試中很熱門，在百度和迅雷的校園招聘以及程序員和軟件設(shè)計師的考試中都考到了，因此了解全排列算法對我們都很有好處。也是算法的一個基本思想。遞歸算法的思路比較直，而非遞歸的就比較難去想到使用這種方法來實現(xiàn)。
1．全排列就是從第一個數(shù)字起每個數(shù)分別與它后面的數(shù)字交換。
2．去重的全排列就是從第一個數(shù)字起每個數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。
3．全排列的非遞歸就是由后向前找替換數(shù)和替換點，然后由后向前找第一個比替換數(shù)大的數(shù)與替換數(shù)交換，最后顛倒替換點后的所有數(shù)據(jù)。
