全排列的两种实现方式

Dear 丶 2022-03-11 10:39 304阅读 0赞

## 全排列： ##

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。如果这组数有n个，那么全排列数为n!个。

假设现在有三个数字：0 1 2，将其全排列结果为：

0 1 2

0 2 1

1 0 2

1 2 0

2 0 1

2 1 0

### 第一种方式是利用c++STL中的prev\_permutation: ###

#include <iostream>
    #include <algorithm>
    using namespace std;
    int main ()
    {
        int arr[] = {2,1,0};
        do
        {
            cout << arr[0] << ' ' << arr[1] << ' ' << arr[2]<<'\n';
        }
        while ( prev_permutation(arr,arr+3) );     
    
        int arr1[] = {0,1,2};
        do
        {
            cout << arr1[0] << ' ' << arr1[1] << ' ' << arr1[2] <<'\n';
        }
        while ( next_permutation(arr1,arr1+3) );     
    
        return 0;
    }

说明：prev\_permutation是获取**上**一个较大字典序排列，其中3为参数，可根据自己的需求更改。

next\_permutation 是获取**下**一个较大字典序排列，

必要时要对数组先进行排序(sort)

### 第二种方式是使用递归： ###

#include <iostream>
    using namespace std;
    void print_permutation(int n,int *x,int cur){
    	if(cur==n){
    		for(int i = 0; i < n;i++){
    			cout << x[i];
    		} 
    		cout << endl;
    	}
    	else{
    		for(int i= 0; i < n; i++){
    			int ok = 1;
    			for(int j = 0; j < cur; j++){
    				if(x[j]==i) ok = 0;
    			}
    			if(ok){
    				x[cur] = i;
    				print_permutation(n,x,cur+1);
    			}
    		}
    	}	
    }
    
    int main(){
    	int nums[10]={0,1,2,3,4,5,6,7,8,9};
    	print_permutation(3,nums,0);		
    	return 0;
    }

说明：

递归结束的条件当然是所有的数全部用上了，循环变量的i是当前考察的x\[cur\].为了检查元素i是否已经被使用过，变量ok作为一个标记。

不妥之处，请多见谅并赐教。