資料結構—全排列的遞歸解法

1.全排列的遞歸實作

• 全排清單示把集合中元素的所有按照一定的順序排列起來，使用P(n, n) = n!表示n個元素全排列的個數。P(n, n)中的第一個n表示元素的個數，第二個n表示取多少個元素進行排列。
• 給定一個n個元素數組，其全排列的過程可以描述如下： 
  • 任意取一個元素放在第一個位置，則有n種選擇； 
  • 再剩下的n-1個元素中再取一個元素放在第二個位置則有n-1種選擇，此時可以看做對n-1個元素進行全排列； 
  • 重複第二步，直到對最後一個元素進行全排列，即最後一個元素放在最後一個位置，全排列結束。
• 字元串"123"為例，其全排列的過程如下： 
  • 1後面跟（2,3）的全排列； 
  • 2後面跟（1,3）的全排列； 
  • 3後面跟（1,2）的全排列。

2.代碼實作

• main.c

#include <stdio.h>
#include <stdlib.h>

void permutation(char s[],int begin,int end )
{
	if ((begin >= 0) && (begin <= end))
	{
		if (begin == end)
		{
			printf("%s \n", s);
		}
		else
		{
			int i = 0;

			for (i = begin; i <= end; i++)
			{
				char c = s[begin];    // 交換字元串的位置，使每個字母都依次位于子符串第一個位置
				s[begin] = s[i];
				s[i] = c;

				permutation(s, begin + 1, end); // 對剩下元素進行全排列

				c = s[begin];      // 交換回來
				s[begin] = s[i];
				s[i] = c;
			}
		}
	}	
}

int main()
{
	char s[] = "123";

	permutation(s, 0, 2);
	
	system("pause");

	return 0;
}
           

• 運作結果