全排列是什么?
全排列是指将一组元素按照一定顺序进行排列的所有可能结果。以一组数字为例,比如[1, 2, 3]的全排列结果为:[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]。
全排列有许多不同的计算方法,其中最常用的方法之一是使用递归。可以通过递归函数来实现全排列,每次从剩余未排列数字中选择一个数字放置到当前位置上,然后对剩余数字递归调用全排列函数,直到所有元素都被排列完毕。
以下是一个使用递归算法计算全排列的示例代码(使用C++语言):
#include <stdio.h>
#include <stdbool.h>
// 判断当前排列是否重复
bool isDuplicate(int arr[], int start, int end) {
for (int i = start; i < end; i++) {
if (arr[i] == arr[end]) {
return true;
}
}
return false;
}
// 交换两个元素的值
void change(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
// 递归生成全排列
void generatePermutations(int arr[], int start, int end) {
if (start == end) {
// 打印当前排列
for (int i = 0; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
} else {
// 递归生成全排列
for (int i = start; i <= end; i++) {
if (!isDuplicate(arr, start, i)) { // 判断当前元素是否重复
change(&arr[start], &arr[i]);
generatePermutations(arr, start + 1, end);
change(&arr[start], &arr[i]); // 恢复原数组
}
}
}
}
int main() {
int n;
printf("请输入要生成全排列的元素个数:");
scanf("%d", &n);
int arr[n];
printf("请输入%d个整数:", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("生成的全排列为:\n");
generatePermutations(arr, 0, n - 1);
return 0;
}
验算: