选择整数1至n中m个数进行字典序全排列C语言

以下是C语言代码实现：

#include <stdio.h>

int n, m;
int a[100], vis[100];

void dfs(int step)
{
    if (step > m) {
        for (int i = 1; i <= m; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = 1;
            a[step] = i;
            dfs(step + 1);
            vis[i] = 0;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    dfs(1);
    return 0;
}

其中，`n`表示1至n中的数，`m`表示选出的数的个数，`a`数组记录当前排列，`vis`数组记录数字是否已经被选过。通过深度优先搜索遍历所有排列，按照字典序输出。

相关问题

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语言实现

以下是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函数中，实现了求下一个字典序排列的算法。

c语言按照字典序输出自然数 1 1 到 � n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

在C语言中，生成从1到n的所有不重复元素的全排列通常采用递归回溯法，也叫做“next permutation”算法。这里是一个简单的示例代码，用于实现这个功能：

#include <stdio.h>
#include <stdlib.h>

// 比较两个整数数组是否相等
int compare(const void *a, const void *b) {
    return (*(const int *)a - *(const int *)b);
}

// 排列函数，生成下一个排列
void generatePermutation(int arr[], int n, int i) {
    if (i == n - 1) { // 如果已经到了最后一个位置，直接返回，因为到达最末就是最后一个排列
        for (int j = 0; j < n; j++) {
            printf("%d ", arr[j]);
        }
        puts("");
        return;
    }

    int maxIndex = i; // 初始化最大值索引为当前遍历的位置
    for (int k = i + 1; k < n; k++) { // 寻找大于arr[i]的最小值
        if (arr[k] > arr[maxIndex]) {
            maxIndex = k;
        }
    }

    // 交换arr[i]和maxIndex位置上的元素，得到一个新的递增序列
    swap(&arr[i], &arr[maxIndex]);

    // 对剩余部分进行递归排列
    generatePermutation(arr, n, i + 1);

    // 对于递增序列，将arr[i+1]到end部分进行reverse操作，形成下一个排列
    for (int j = n - 1; j > i; j--) {
        swap(&arr[j], &arr[j - 1]);
    }
}

// 交换两个元素的指针
void swap(void **a, void **b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    
    int* arr = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }

    qsort(arr, n, sizeof(int), compare); // 先对数组进行升序排序

    generatePermutation(arr, n, 0); // 开始生成排列

    free(arr);
    return 0;
}