C语言实现的排列组合问题的通用算法、解决方法

C语言实现的排列组合问题的通用算法

概述

排列组合问题是指在n个元素集合中选择m个元素，不同的选择方式就是一组排列。当考虑可重复选取时，一组排列就变成了一组组合。C语言实现排列组合问题需要用到递归方式和暴力枚举的方法。

排列与组合的代码实现

下面分别介绍排列和组合的算法实现。

排列

#include <stdio.h>

void permutation(int arr[], int k, int m) {
    if (k == m) {  // 完成一组排列
        for (int i = 0; i <= m; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
    else {
        for (int i = k; i <= m; i++) {   
            int temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;
            permutation(arr, k + 1, m);  // 递归处理后面的元素
            temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int arr[n];
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    permutation(arr, 0, m - 1);  // m个元素的排列
    return 0;
}

以上代码中，permutation函数使用了递归的方式。若m=k，证明已完成一次排列，需要输出并返回；否则，将当前要处理的一位与后面的每一位进行交换，再递归处理后面的元素。

组合

#include <stdio.h>

void combination(int arr[], int k, int m, int index) {
    if (index == m) {  // 完成一组组合
        for (int i = 0; i < m; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
    else {
        for (int i = k; i <= n; i++) {
            arr[index] = i;
            combination(arr, i, m, index + 1);   // 递归处理后面的元素
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int arr[m];
    combination(arr, 1, m, 0);  // 从1开始选择m个元素的组合
    return 0;
}

组合问题同样使用了递归的方式。arr[index]用于存储已选择的元素，i表示当前可以选择的元素。需要注意的是，为了避免重复，每次选择的元素都比上一次选择的元素编号大。

示例说明

示例1：求n个元素中任选3个的组合

输入示例：

5 3

输出示例：

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

示例2：求n个元素中任选4个的排列

输入示例：

6 4

输出示例：

1 2 3 4 
1 2 3 5 
1 2 3 6 
1 2 4 3 
1 2 4 5 
1 2 4 6 
1 2 5 3 
1 2 5 4 
1 2 5 6 
1 2 6 3 
...（省略部分）
6 4 3 1 
6 4 3 2 
6 4 5 1 
6 4 5 2 
6 4 5 3 
6 5 1 2 
6 5 1 3 
6 5 1 4 
6 5 2 1 
6 5 2 3 
6 5 2 4 
6 5 3 1 
6 5 3 2 
6 5 4 1 
6 5 4 2 
6 5 4 3 

以上就是C语言实现排列组合问题的通用算法和解决方法。