详解全排列问题的递归算法(C语言实现)

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。如果如果输入为1、2、3,要求输出123、132、213、231、312和321。下面分有重复元素和无重复元素的两种情况说明:

一、无重复元素的递归算法实现

无重复元素的全排列问题,用递归算法比较简单。代码如下:

#include <stdio.h>
#define NUM 3

int arr[NUM] = {1, 2, 3};

void do_range(int low, int high)
{
	if(low == high)
	{
		for(int i=0; i<NUM; i++) printf("%6d", arr[i]);
		printf("\n");
	}
	else
	{
		do_range(low+1, high);
	
		for(int i=low+1; i<=high; i++)
		{
			//递归前交换 
			int t = arr[low]; arr[low] = arr[i]; arr[i] = t;
			do_range(low+1, high);
			//递归后复位 
			t = arr[low]; arr[low] = arr[i]; arr[i] = t;
		}
	}
}

int main(int argc,char *argv[])
{
    do_range(0, NUM-1);
    return 0;
}

输出如下:

1     2     3
1     3     2
2     1     3
2     3     1
3     2     1
3     1     2

二、有重复元素的递归算法实现

如果有重复元素,比如输入113,再按照上述算法,输出如下,显然不符合要求。

1     1     3
1     3     1
1     1     3
1     3     1
3     1     1
3     1     1

关键问题就是有重复元素,算法中就不需要进行交换,再递归求解了。上述代码修改如下:

#include <stdio.h>
#define NUM 3

int arr[NUM] = {1, 1, 3};

void do_range(int low, int high)
{
	if(low == high)
	{
		for(int i=0; i<NUM; i++) printf("%6d", arr[i]);
		printf("\n");
	}
	else
	{
		do_range(low+1, high);
	
		for(int i=low+1; i<=high; i++)
		{
			//如果有重复元素,就不要交换再递归求解了。直接过滤就行。 
			if(arr[low] == arr[i]) continue;
			//递归前交换 
			int t = arr[low]; arr[low] = arr[i]; arr[i] = t;
			do_range(low+1, high);
			//递归后复位 
			t = arr[low]; arr[low] = arr[i]; arr[i] = t;
		}
	}
}

int main(int argc,char *argv[])
{
    do_range(0, NUM-1);
    return 0;
}

输出如下:

1     1     3
1     3     1
3     1     1

上述输出结果符合要求,完毕~~~

Leave a Reply

Your email address will not be published. Required fields are marked *