21xrx.com
2025-04-01 08:01:37 Tuesday
文章检索 我的文章 写文章
C++实现全排列算法
2023-06-29 10:12:09 深夜i     --     --
C++ 全排列 算法

全排列算法是一种常见的算法，其主要作用是为给定的一组数据找出其中的所有可能排列组合。在C++中，我们可以通过使用递归函数来实现这一算法。

实现思路：

首先定义一个函数来进行排列，该函数接收以下三个参数：

1.当前正在排列的位置。

2.要求排列的数据数组。

3.数据数组长度。

接着使用递归的方法，将每个位置的数依次交换，直到所有元素都排列完成。最后打印出排列组合即可。

以下是C++程序实现代码：

#include<iostream>
using namespace std;
void permutation(int n, int arr[], int size)
{
  if(n==size-1)
  {
    for(int i=0;i<size;i++)
      cout << arr[i] << " ";
    cout<<endl;
  }
  else
  {
    for(int i=n;i<size;i++)
    {
      swap(arr[n],arr[i]);
      permutation(n+1, arr, size);
      swap(arr[n],arr[i]);
    }
  }
}
int main()
{
  int arr[] = 1;
  permutation(0, arr, 4);
  return 0;
}

在此代码中，我们通过调用 `permutation` 函数来运行全排列算法。我们需要传递三个参数。第一个参数是当前序列中正在处理的位置。第二个参数是数据数组，第三个参数是数组的长度。函数的逻辑如下：

1. 如果处理的位置为最后一个元素，就打印出整个数组。

2. 如果处理的位置不是最后一个元素，则将该位置的元素依次与后面的元素交换，然后递归调用 `permutation` 函数。在递归返回前，我们需要将数组还原为原来的样子，以便下一次交换。

我们可以通过上述函数来输出数组 `2` 的全排列组合。运行结果如下：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3

全排列算法是C++程序中非常常用的算法之一。它能够生成由给定数据组合成的所有可能的顺序排列。通过实现这个算法来获取目标集合中的所有可能排列，既能为代码提供灵活性，也能提高代码的可重用性。

  
  

评论区