C语言实现全排列算法：字典序生成n!个排列

一、问题描述

给定正整数n，生成整数1,2,…,n的n!个排列，不同的排列之间按照字典顺序由最小顺序生成。即从123…n开始，到n…321结束。

二、输入

输入数据包含多个测试实例，每个测试实例占一行，由一个正整数n(0<n<10)组成。

三、输出

对于每个测试实例，每组测试数据的输出占一行。该行中为所有的n个数字的排列，按字典顺序输出，每两个排列之间用'->'连接。

四、输入样例

2 3

五、输出样例

12->21 123->132->213->231->312->321

六、实验原理

生成的排列的算法基础是从一个给定排列按照字典顺序构成下一个排列的过程:

首先找到整数a'j' 和a'j+1' ,使得a'j' <a'j+1' ,且a'j+1' >a'j+2' >…>a'n' ，即在这个排列中的最后一对相邻的整数，使得这个对的第一个整数小于第二个整数。
然后把a'j+1' ,a'j+2' ,...,a'n' 中大于a'j' 的最小的整数放到第j个位置，再按照递增顺序从位置j+1到n列出a'j' ,a'j+1' ,...,a'n' 中其余的整数，这就得到依照字典顺序的下一个更大的排列。

七、核心代码

void nextpermutation(int a[1..n])
//存储在数组中
{
    j=n-1;
    while(a[j]>a[j+1]) j--;
        //使得j是aj<aj+1的最大下标
    k=n;
    while(a[j]>a[k]) k--;
                  //ak是在aj的右边大于aj的最小正整数
    swap(a[j],a[k]);//互换aj,ak    
    r=n;
    s=j+1;
    while(r>s){swap(a[r],a[s]);r--;s++;}
}

八、代码实现

以下是使用C语言实现的代码：

#include <stdio.h>

// 交换数组中两个元素的位置
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 生成下一个排列
void nextPermutation(int* nums, int n) {
    int j = n - 2;
    while (j >= 0 && nums[j] > nums[j + 1]) {
        j--;
    }
    if (j < 0) {
        return; // 已经是最后一个排列，不能生成下一个排列
    }
    int k = n - 1;
    while (nums[j] > nums[k]) {
        k--;
    }
    swap(&nums[j], &nums[k]);
    int r = n - 1;
    int s = j + 1;
    while (r > s) {
        swap(&nums[r], &nums[s]);
        r--;
        s++;
    }
}

int main() {
    int n;
    while (scanf('%d', &n) != EOF) {
        // 初始化数字数组
        int nums[10];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }

        // 输出初始排列
        for (int i = 0; i < n; i++) {
            printf('%d', nums[i]);
            if (i < n - 1) {
                printf(',');
            }
        }
        printf('->');

        // 生成并输出所有排列
        int count = 1;
        while (count < n * (n - 1)) {
            nextPermutation(nums, n);
            for (int i = 0; i < n; i++) {
                printf('%d', nums[i]);
                if (i < n - 1) {
                    printf(',');
                }
            }
            if (count < n * (n - 1) - 1) {
                printf('->');
            }
            count++;
        }

        printf('\n');
    }

    return 0;
}

九、代码说明

nextPermutation 函数实现了生成下一个排列的功能。
swap 函数用于交换两个元素的位置。
main 函数用于读取输入、初始化数字数组、生成并输出所有排列。

十、总结

本文介绍了使用C语言实现全排列算法的方法，并提供了详细的代码示例。希望本文对您学习全排列算法有所帮助。