【递归与分治】全排列问题 C/C#/C++ 算法优化

tensai 1月前 38

给定一个数组,给出其全排列。例如,给定数组1,2,3。它的全排列是得到如下的6种排列:
123
132
213
231
312
321

解题思路: 假设某一数组要求从begin到end进行全排列。可以将全排列分解为两步:

  • 第一步,选择一个元素打头;
  • 第二步,从第begin+1个元素开始到第end个元素,对数组进行全排列。

伪代码如下:

void perm(a,begin,end)
{
	for (i=begin; i<=end; i++)
	{
		swap(a,begin,i);
		perm(a,begin+1,end);
		swap(a,begin,i); //这步是关键,将数组恢复到以前的样子,否则容易出问题
	}
}

参考代码:

#include <stdio.h>
 
void perm(int a[], int begin, int end);
 
int main()
{
    int a[3]={1,2,3};
    perm(a,0,2);
    return 1;
}
 
void perm(int a[], int begin, int end)
{
    int i,temp;
 
    if (begin==end){
        for(i=0;i<3;i++)
             printf("%d ",a[i]);
 
            printf("\n");
    }else{
        for(i=begin;i<=end;i++){
             temp=a[begin];
             a[begin]=a[i];
             a[i]=temp;
             perm(a,begin+1,end);
 
             temp=a[begin];
             a[begin]=a[i];
              a[i]=temp;
        }
   }
}
最新回复 (0)
全部楼主
返回
发新帖