在C语言中生成一个指定数组的全排列,不用递归实现
时间: 2024-09-13 13:18:17 浏览: 41
求一个动态数组的全排列,c语言实现
5星 · 资源好评率100%
在C语言中生成一个指定数组的全排列,可以使用非递归的迭代方法,通常采用基于置换的方法,即循环交换数组中的元素。以下是一个实现的示例:
```c
#include <stdio.h>
#include <stdbool.h>
// 函数声明
void swap(int *a, int *b);
void permute(int arr[], int start, int end);
int main() {
int arr[] = {1, 2, 3}; // 示例数组
int n = sizeof(arr) / sizeof(arr[0]);
permute(arr, 0, n - 1);
return 0;
}
// 交换数组中的两个元素
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 生成数组的全排列(非递归实现)
void permute(int arr[], int start, int end) {
bool flag = true; // 控制循环的标志变量
int i;
// 初始化一个数组来记录是否访问过每个位置
int isVisited[10]; // 假设数组元素范围不超过10
for (i = 0; i <= end; i++) {
isVisited[i] = 0; // 初始化所有位置为未访问
}
for (i = 0; i <= end; i++) {
// 当前位置未被访问,进行排列
if (isVisited[i] == 0) {
// 找到一个未被访问的位置,从当前位置开始生成排列
isVisited[i] = 1; // 标记为已访问
swap(&arr[start], &arr[i]); // 将当前位置的元素与起始位置的元素交换
// 如果当前不是最后一个元素,递归生成剩余元素的排列
if (start < end) {
permute(arr, start + 1, end);
} else {
// 当前是最后一个元素,打印一个全排列
for (int j = 0; j <= end; j++) {
printf("%d ", arr[j]);
}
printf("\n");
}
// 回溯,将元素交换回去,标记为未访问
swap(&arr[start], &arr[i]);
isVisited[i] = 0;
}
// 如果当前位置已访问,直接跳过
flag = false;
}
// 如果所有元素都被访问过一次,则结束循环
if (flag) {
return;
} else {
// 恢复最后交换的状态,继续循环
if (start < end) {
permute(arr, start + 1, end);
} else {
for (int j = 0; j <= end; j++) {
printf("%d ", arr[j]);
}
printf("\n");
}
}
}
```
这段代码首先定义了`swap`函数用于交换数组中的两个元素,然后定义了`permute`函数来生成全排列。`permute`函数使用了一个`isVisited`数组来记录每个元素是否在当前排列中被访问过。函数通过循环遍历数组,找到一个未被访问的元素,并将其与起始位置的元素交换,然后递归地生成剩余元素的排列。通过这种方式,可以非递归地生成所有可能的全排列。
阅读全文