21xrx.com
2024-11-05 18:47:35 Tuesday
登录
文章检索 我的文章 写文章
C++全排列算法实现
2023-07-13 19:05:50 深夜i     --     --
C++ 全排列算法 实现

全排列是指给定一组数,求其中所有数的组合方式。比如给定数列2,它的全排列是2、1、2、3、3和1。

在C++中,实现全排列算法可以使用STL库中的next_permutation函数,也可以使用递归算法。下面介绍递归算法的实现步骤。

步骤一:编写递归函数

首先,需要编写一个递归函数。该函数的输入是待排列的数组和当前要处理的数组下标。对于每一个下标,从该下标开始的元素和前面的元素依次交换,以达到产生全排列的目的。

下面是一个递归函数的实现样例:

void permute(int arr[], int start, int end) {

  if (start == end) {

    for (int i = 0; i <= end; i++) {

      cout << arr[i] << " ";

    }

    cout << endl;

  } else {

    for (int i = start; i <= end; i++) {

      swap(arr[start], arr[i]);

      permute(arr, start + 1, end);

      swap(arr[start], arr[i]);

    }

  }

}

这个函数的实现很简单。如果已经处理到了数组末尾,则打印该数组;否则从当前位置开始,在该位置和后续位置上交换数组元素,并递归处理后续元素。

步骤二:编写主函数

为了运行上面编写的递归函数,还需要编写一个主函数。该主函数先定义待排列的数组,然后将它传递给递归函数进行处理。

下面是一个主函数的实现样例:

int main() {

  int arr[] = 2;

  int n = sizeof(arr) / sizeof(arr[0]);

  permute(arr, 0, n - 1);

}

这个主函数的实现也很简单。先定义一个数组,然后计算数组大小,并将数组和数组下标范围传递给递归函数。

步骤三:运行程序

最后,只需要运行编写的程序即可得到输出结果。以下是上面编写的程序的输出结果:

1 2 3

1 3 2

2 1 3

2 3 1

3 2 1

3 1 2

这些输出结果就是上面定义的数组 3的全排列。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复