数据结构—全排列的递归解法

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;
}
           

• 运行结果