c++之排列

c++之排列

科技前沿 • 2025-01-12 10:38 • 阅读 68

大家好，我是讯享网，很高兴认识大家。

c++递归实现全排列

一、什么是全排列？

排列就是将给定序列进行任意组合，比如举个简单的例子，给定数组 arr[3] = {1,2,3},那么1,2，3的不同排列就有A₃³ = 321 = 6种，分别对应的组合为：（1 2 3）（1 3 2）（3 2 1）（3 1 2）（2 1 3）（2 3 1）

二、实现思想

这里主要采用的实现思想是每次两两交换，然后依次递归，直到考虑到最后一个位置为止，因为要进行递归，因此这里在交换两数之后进行递归之后一定要记得进行回溯，不然就会导致其递归是在前一个序列基础之上的，从而得不到整个排列过程。

三、代码模板

模板代码如下（示例）：

讯享网

void pailie(int arr[],int k,int size) { 
    //cout << sizeof(arr)/ sizeof(arr[0]) << endl; //k表示当前考虑位置 size表示数组长度 if (k == size - 1) { 
    for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; return; } for (int i = k; i < size; i++) { 
    int tem = arr[k]; arr[k] = arr[i]; arr[i] = tem; pailie(arr,k+1,size); tem = arr[k]; arr[k] = arr[i]; arr[i] = tem; } }

讯享网

注释：其中arr表示要进行组合的数组，k表示当前考虑的位置，size表示需要排列的数值个数。

三、使用案列

比如我要对int a[3] = { 1 , 2 , 3 ,4 , 5}中前3个数据进行排列，我们可以这样只用：

讯享网#include<iostream> using namespace std; void pailie(int arr[],int k,int size) { 
    //cout << sizeof(arr)/ sizeof(arr[0]) << endl; //k表示当前考虑位置 size表示数组长度 if (k == size - 1) { 
    //输出所有排列，也可以在这里面处理每组排列的数据 for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; return; } for (int i = k; i < size; i++) { 
    int tem = arr[k]; arr[k] = arr[i]; arr[i] = tem; pailie(arr,k+1,size); tem = arr[k]; arr[k] = arr[i]; arr[i] = tem; } } int a[3] = { 
    1,2,3,4,5 }; int main() { 
    pailie(a,0,3); return 0; }

四、结果输出

在这里插入图片描述