【算法复习】全排列专题

一，全排列算法

由于这部分十分重要，这里再次做一下总结。

更多详细内容参考博文组合数学-全排列

二，算法思想

这里采用递归算法，思路如下

固定第一个数，然后处理后面n-1的全排列。

第一个数的可能性有n种，故采用for循环依次将后面n-1个数swap到前面，递归处理。处理完成之后再交换过来。

例如：1 2 3 ： 固定1 然后全排列 2 3

swap(2,2)(固定2) 然后全排列 3 //输出 1 2 3

swap(2,3)(固定3) 然后全排列2 //输出 1 3 2

递归之后交换swap(3,2)

swap(1,2) 固定2 然后处理 1 3 //同理

swap(1,3) 固定3 然后处理 1 2 //同理

#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

int sum=0;
void  FullArray(int a[],int begin,int end)
{
    if(begin>end)
    {
        for(int i=0;i<=end;i++)
            cout<<a[i]<<" ";
        
        sum++;
        cout<<endl;
    }
    else
    {
        for(int i=begin;i<=end;++i)
        {
            swap(a[i],a[begin]);
            FullArray(a,begin+1,end);
            swap(a[begin],a[i]);
        }
    }
    
}
int main(int argc, char** argv) {

    int a[5]={1,2,3,4,5};
    FullArray(a,0,4);
    cout<<"total number:"<<sum<<endl;
    return 0;
}

三，提高篇

问题：从1--n 中的n个数中选取 r个数，全排列输出

思想：递归算法 选取 r个数，然后调用全排列算法

#include <cstdlib>
#include <iostream>

using namespace std;
int a[100];
int n = 0;
void swap(int *a, int *b) 
{ 
	int m; 
	m = *a; 
	*a = *b; 
	*b = m; 
} 
void FullArray(int list[], int k, int m) 
{ 
	int i; 
	if(k > m) 
	{ 
		for(i = 0; i <= m; i++) 
			cout<< list[i]<<" "; 
		
                cout<<endl;
		n++; 
	} 
	else 
	{ 
		for(i = k; i <= m; i++) 
		{ 
			swap(&list[k], &list[i]); 
			FullArray(list, k + 1, m); 
			swap(&list[k], &list[i]); 
		} 
	} 
} 

void comb(int m,int k) 
{   
   int i,j; 
   for (i=m;i>=k;i--) //循环的关键
   { 
    	a[k]=i; 
    	if (k>1) 
           comb(i-1,k-1); 
        else 
        { 
          FullArray(a+1,0,2);
	   
	}
   }
}


int main()
{
	comb(5,3);
	cout<<"total:"<<n<<endl; 
	return 0;
}