C/C++实现不重复三位数排列生成算法

1. 问题分析与算法设计

1.1 问题描述解析

给定四个不同的数字（0-9），我们需要生成所有可能的三位数组合，要求：

1. 每个三位数的数字不重复
2. 所有组合按从小到大顺序排列
3. 每个组合的数字必须来自给定的四个数字

例如输入1 2 3 4，输出应为从123到432的所有24种排列。

1.2 算法选择考量

解决这个问题主要有两种思路：

1. 暴力枚举法：通过三重循环遍历所有可能的排列组合
2. 标准库排列法：利用C++的next_permutation函数生成排列

暴力枚举法的优势在于：

• 逻辑直观，适合初学者理解排列组合原理
• 不依赖特定语言特性，可移植性强
• 便于添加自定义过滤条件

标准库排列法的优势在于：

• 代码简洁，开发效率高
• 内置的排列算法经过优化，性能更好
• 减少手动编写循环可能引入的错误

提示：教学场景建议先掌握暴力枚举法，实际项目开发推荐使用标准库函数

2. C语言实现详解

2.1 基础版本实现

c复制#include <stdio.h>

void composeNumber(int a, int b, int c, int d) {
    int num[4] = {a, b, c, d};
    
    for(int i = 0; i < 4; i++) {        // 百位选择
        for(int j = 0; j < 4; j++) {    // 十位选择
            if(j == i) continue;         // 避免数字重复
            for(int k = 0; k < 4; k++) { // 个位选择
                if(k == i || k == j) continue;
                printf("%d\n", num[i]*100 + num[j]*10 + num[k]);
            }
        }
    }
}

int main() {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    composeNumber(a, b, c, d);
    return 0;
}

2.2 关键点解析

1. 数字存储：使用数组存储输入数字，便于循环访问
2. 三重循环结构：
   • 外层循环确定百位数
   • 中层循环确定十位数
   • 内层循环确定个位数
3. 去重机制：通过continue跳过使用相同数字的情况
4. 数值计算：通过位权计算三位数值：百位×100 + 十位×10 + 个位

2.3 常见错误与调试

1. 变量未重置：

   c复制// 错误示例
   int sum = 0;
   for(...) {
       sum = num[i]*100;
       // 忘记在每次循环开始时重置sum
   }
   

2. 索引混淆：

   c复制// 错误示例
   if(k == i || k == i) continue; // 第二个条件应为k == j
   

3. 输出格式错误：

   c复制// 错误示例
   printf("%d", num[i], num[j], num[k]); // 缺少数值计算
   

调试技巧：可在每个循环开始处添加printf打印当前变量值，观察执行流程

3. C++优化实现

3.1 使用STL算法

cpp复制#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int nums[4];
    for(int i=0; i<4; i++) cin >> nums[i];
    
    sort(nums, nums+4); // 必须先排序
    
    do {
        cout << nums[0] << nums[1] << nums[2] << endl;
    } while(next_permutation(nums, nums+4));
    
    return 0;
}

3.2 next_permutation原理

1. 字典序生成：按照数字大小顺序生成下一个排列
2. 必要条件：输入数组必须是有序的，否则无法生成全部排列
3. 时间复杂度：O(n!) 全排列数量

3.3 性能对比

4. 算法扩展与变种

4.1 通用排列生成模板

cpp复制template<typename T>
void printPermutations(T arr[], int n, int k) {
    sort(arr, arr+n);
    do {
        for(int i=0; i<k; i++) cout << arr[i] << " ";
        cout << endl;
    } while(next_permutation(arr, arr+n));
}

4.2 去重排列问题

当输入数字有重复时，需要修改算法：

cpp复制sort(nums, nums+4);
do {
    // 检查前三位是否有重复
    if(nums[0]==nums[1] || nums[1]==nums[2]) continue;
    cout << nums[0] << nums[1] << nums[2] << endl;
} while(next_permutation(nums, nums+4));

4.3 组合数学分析

对于4个不同数字取3个的排列数计算：
P(4,3) = 4! / (4-3)! = 24种

排列数公式：
P(n,k) = n! / (n-k)!

5. 工程实践建议

1. 输入验证：

   cpp复制if(a==b || a==c || a==d || b==c || b==d || c==d) {
       cerr << "输入数字必须互不相同" << endl;
       return 1;
   }
   

2. 性能优化：

   • 对于大规模排列问题，考虑剪枝算法
   • 使用迭代替代递归避免栈溢出

3. 输出格式化：

   cpp复制cout << setw(3) << setfill('0') << nums[0]*100+nums[1]*10+nums[2];
   

4. 单元测试用例：

   cpp复制void test() {
       // 边界测试
       assert(permutationCount(1,2,3,4) == 24);
       // 含0测试
       assert(permutationCount(0,1,2,3) == 18); // 0不能作为百位数
   }
   

在实际项目中遇到类似排列组合问题时，建议先明确具体需求：是否需要所有排列、是否有重复元素、是否需要考虑顺序等。根据不同的需求场景选择合适的算法实现，平衡代码可读性和运行效率。