1. 以字典序产生排列 【问题描述】给定正整数n生成1到n的全排列(利用书上P112页的字典序算法) 【输入形式】一个整数n(1<=n<=9) 【输出形式】n!行,每一行的第一个数是第几个全排列,第二个数是全排列打印(中间用制表符\t分开); 【样例输入】 3 【样例输出】 1 123 2 132 3 213 4 231 5 312 6 321 用C语言实现
时间: 2023-06-15 22:07:40 浏览: 193
以下是C语言实现代码:
```c
#include <stdio.h>
// 计算n的阶乘
int factorial(int n) {
int res = 1;
for (int i = 1; i <= n; i++) {
res *= i;
}
return res;
}
// 交换两个数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 字典序全排列
void permutation(int n) {
int p[n];
// 初始化为1,2,3,...,n
for (int i = 0; i < n; i++) {
p[i] = i + 1;
}
int count = 0;
do {
count++;
printf("%d\t", count);
for (int i = 0; i < n; i++) {
printf("%d", p[i]);
}
printf("\n");
} while (next_permutation(p, n));
}
// 下一个字典序排列
int next_permutation(int *p, int n) {
// 从后往前找到第一个相邻的逆序对
int i = n - 2;
while (i >= 0 && p[i] >= p[i + 1]) {
i--;
}
// 如果找不到逆序对,说明已经是最后一个排列,返回0
if (i < 0) {
return 0;
}
// 从i的右侧找到最小的大于p[i]的数
int j = n - 1;
while (j > i && p[j] <= p[i]) {
j--;
}
// 交换p[i]和p[j]
swap(&p[i], &p[j]);
// 反转i右侧的元素
int k = i + 1, l = n - 1;
while (k < l) {
swap(&p[k], &p[l]);
k++;
l--;
}
return 1;
}
int main() {
int n;
printf("请输入一个整数n(1<=n<=9):");
scanf("%d", &n);
int count = factorial(n);
printf("%d!共有%d个全排列,输出如下:\n", n, count);
permutation(n);
return 0;
}
```
该程序使用了字典序全排列算法,先将1到n初始化为一个数组p,然后按照字典序的顺序依次输出全排列,直到输出了n!个全排列。在每次输出时,先输出当前排列的编号,然后再输出该排列的元素。在next_permutation函数中,实现了求下一个字典序排列的算法。
阅读全文
相关推荐














