全排列算法之Perm算法實現

題目描述：

給定一個由不同的小寫字母組成的字符串，輸出這個字符串的所有全排列。
我們假設對於小寫字母有'a' < 'b' < ... < 'y' < 'z'，而且給定的字符串中的字母已經按照從小到大的順序排列。

輸入：

輸入只有一行，是一個由不同的小寫字母組成的字符串，已知字符串的長度在1到6之間。

輸出：

輸出這個字符串的所有排列方式，每行一個排列。要求字母序比較小的排列在前面。字母序如下定義：
已知S = s1s2...sk , T = t1t2...tk，則S < T 等價於，存在p (1 <= p <= k)，使得
s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。

樣例輸入：

abc

樣例輸出：

abc
acb
bac
bca
cab
cba

提示：

每組樣例輸出結束後要再輸出一個回車。

想必大家對perm遞歸算法求全排列並不陌生，但我貼出來的題目卻不能用perm算法來解決，為什麼呢？請容我慢慢道來，首先題目對全排列有著非常嚴格的順序要求，即按字典順序排列，就是這個perm算法是滿足不了的（或許經過小小的改變是可以實現的，我們在這裡就不討論了）。那麼下來我來談談perm算法的核心思：舉個例子，比如要你1的全排列，你肯定會說那還不簡單啊，那麼接下來加深難度求1，2的全排列，其實也不難，現在讓你求1，2，3，4，5的全排列呢，還轉得過來嗎？現在我們可以這樣想，3，4，5的全排列是以3開頭的4，5的全排列組合和4開頭的3，5的全排列組合以及以5開頭的3，4全排列組合。這就是perm算法的核心思想，列出一個通俗一點的式子：

從而可以推斷，設一組數p = {r1, r2, r3, ... ,rn}, 全排列為perm(p)，pn = p - {rn}。

因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。

當n = 1時perm(p} = r1。

下面貼出代碼：

#include
#include
#define MAX 10

using namespace std;

void swap(char str[],int i,int j)
{
	int temp;
	temp=str[i];
	str[i]=str[j];
	str[j]=temp;
}

void perm(char str[],int k,int m)
{
	int i;
	if(k>m)
	{
		for(i=0;i<=m;i++)
			printf("%c",str[i]);
		printf("\n");
	}
	else
	{
		for(i=k;i<=m;i++)
		{
			swap(str,k,i);
			perm(str,k+1,m);
			swap(str,k,i);
		}
	}
}

int main(int argc,char *argv[])
{
	char str[MAX];
	while(scanf("%s",str)!=EOF)
	{
		int len=strlen(str);
		perm(str,0,len-1);
		printf("\n");
	}

	return 0;
}

這裡會出現兩個問題，其一是超時，其二是答案順序不對。。。

因為每次都進行的是將數組中的數與第一個數進行交換，它注重的是所有的全排列，但沒有注意到換位順序的問題，這樣會產生一個問題：比如 1 2 3 4 的全排列，處理2，3，4的全排列時會將4與2交換，這樣會出現1432排在1423的前面。所以如果對全排列的順序有非常嚴格的順序，就不能用perm算法。

例如，abc的全排列：

有序全排： perm全排：

abc           abc
acb           acb
bac           bac
bca           bca
cab           cba
cba           cab

接下來，我們來看一看perm算法的另一大問題，如果對有重復元素的序列進行全排呢？例如：輸入122則會輸出什麼呢？很遺憾，輸出結果為：122，122，212，221，221，212（如果你能直接說出來，那麼你對perm算法的運行流程就弄明白了），這樣的結果明顯是不對的，該如何解決呢？我們來看一下，第1個數與第2個數交換得到212（此時第一個數在第二個位置），接著第3個數與第2個數交換得到221（此時第一個數1在第三個位置上，第三個數在第二個位置上，第二個數在第一個位置上），然而第二個數與第三個數是相等的（原序列上），這不相當於直接第三個數與第一個數交換了嗎？一下子把下面的事給做了。所以第i個數與第j個數交換時，要求[i,j)中沒有與第j個數相等的數就行了。。。

代碼：

#include
#include
#define MAX 10

using namespace std;

void swap(char str[],int i,int j)
{
	int temp;
	temp=str[i];
	str[i]=str[j];
	str[j]=temp;
}

bool IsUnique(char str[],int start,int end)//檢查重復項
{
	int i;
	for(i=start;im)
	{
		for(i=0;i<=m;i++)
			printf("%c",str[i]);
		printf("\n");
	}
	else
	{
		for(i=k;i<=m;i++)
		{
			if(IsUnique(str,k,i))
			{
				swap(str,k,i);
			    perm(str,k+1,m);
		    	swap(str,k,i);
			}
		}
	}
}

int main(int argc,char *argv[])
{
	char str[MAX];
	while(scanf("%s",str)!=EOF)
	{
		int len=strlen(str);
		perm(str,0,len-1);
		printf("\n");
	}

	return 0;
}