程序员的数学（五）排列组合：编程中解决计数问题的核心思维

举报
倔强的石头_ 发表于 2025/12/09 15:17:22 2025/12/09
【摘要】 本文探讨排列组合在编程中的核心应用，强调“不遗漏、不重复”的计数原则。通过密码破解、接口测试等实际场景，说明排列组合能高效解决复杂计数问题。重点解析加法法则（分类计数）与乘法法则（分步计数）的区别，并详细讲解置换（全排列n!）和排列（P(n,k)）的数学原理与递归实现。程序员掌握这些方法后，可避免硬套公式，灵活处理有序/无序、可重复/不可重复等计数场景，提升代码的准确性与效率。

223d74346013f80be0b0acccf8e3ecd5.png


文章目录


欢迎回到 “程序员的数学” 系列专栏。前面我们陆续掌握了 “余数的分组简化”“归纳法的无穷验证”“逻辑的无歧义计数”—— 今天要讲的排列组合，是这些思维的综合应用，专门解决 “计数问题”。比如编程中 “密码有多少种可能”“任务有多少种调度方式”“从列表中选元素有多少种组合”，本质都是排列组合问题。


你可能会觉得 “排列组合不就是背公式吗？C (n,k) 等于多少，P (n,k) 等于多少”—— 但实际编程中，死记公式很容易出错，比如 “到底要不要考虑顺序”“是否允许重复选择”，这些才是计数的关键。今天我们从 “不遗漏、不重复” 的核心原则出发，用生活例子 + 编程场景，把排列组合的逻辑讲透，让你下次遇到计数问题时，能先理清 “计数对象的性质”，再选择合适的方法，而不是硬套公式。

一、为什么程序员需要排列组合？因为 “计数” 是编程的高频需求

先看几个编程中常见的计数场景，感受排列组合的实用性：

  • 密码破解：6 位数字密码有多少种可能？（10^6=1000000 种，乘法法则）；
  • 接口测试：一个接口有 3 个参数，每个参数有 2 种取值，要测所有组合需要多少次？（2×2×2=8 次，乘法法则）；
  • 团队组建：从 10 个候选人中选 3 人组成开发团队，有多少种选法？（C (10,3)=120 种，组合）；
  • 任务排序：5 个任务按优先级排序，有多少种排列方式？（5!=120 种，置换）。

这些问题的核心都是 “不重复、不遗漏地计数”—— 如果靠手数，数字大了根本数不过来；如果硬写循环遍历，遇到复杂场景（比如选 3 人且不考虑顺序）很容易出错。排列组合就是帮我们 “抽象计数逻辑”，用数学方法快速算出结果，再落地到代码的工具。

二、计数的基础：不遗漏、不重复（从植树问题说起）

在讲排列组合之前，先回顾一个前面提到的 “植树问题”—— 它揭示了计数的核心陷阱：边界处理。比如 “10 米路，每隔 1 米种一棵树，共种多少棵？” 答案是 11 棵（0 到 10 米共 11 个点），因为我们容易遗漏 “起点 0” 或 “终点 10”。

编程中的计数问题也常遇到类似陷阱，比如 “从数组索引 0 到 9 选 2 个不同的索引，有多少种组合？” 如果直接算 10×9=90，就错了（因为 (0,1) 和 (1,0) 是同一组合），正确是 C (10,2)=45 种。

所以计数前，先明确两个问题：

  1. 是否考虑顺序？（比如 “选索引 (0,1)” 和 “(1,0)” 是否算同一种？）
  2. 是否允许重复选择？（比如 “选索引 (0,0)” 是否合法？）

这两个问题的答案，决定了用 “排列” 还是 “组合”，以及是否用 “重复排列”“重复组合”。

三、加法法则与乘法法则：计数的两大基石

排列组合的所有公式，本质都是 “加法法则” 和 “乘法法则” 的延伸。先掌握这两个基础法则，再复杂的计数问题都能拆解。

1. 加法法则：分类计数（“要么… 要么…”）

定义：如果完成一件事有 A、B 两类方法，A 类有 m 种，B 类有 n 种，且 A、B 没有重叠，那么总方法数是 m+n 种。核心是 “分类”—— 每类方法都能独立完成任务，且不重复。

例子 1：选水果

你去水果店，要么选苹果（有 3 种品种），要么选香蕉（有 2 种品种），总共有 3+2=5 种选法。

例子 2：编程中的功能选择

一个工具类有两种排序功能：冒泡排序（1 种实现）、快速排序（2 种实现，递归 / 迭代），总共有 1+2=3 种排序方式。

代码示例：统计合法的输入类型

判断用户输入是否为 “数字” 或 “字母”，统计合法输入的类型数：

python

def count_valid_input_types(input_str):
    # 分类：数字（1种类型）、字母（1种类型），无重叠
    has_digit = any(c.isdigit() for c in input_str)
    has_alpha = any(c.isalpha() for c in input_str)
    count = 0
    if has_digit:
        count += 1  # 数字类
    if has_alpha:
        count += 1  # 字母类
    return count

# 测试："123a"有数字和字母→2种；"123"只有数字→1种
print(count_valid_input_types("123a"))  # 输出2
print(count_valid_input_types("123"))   # 输出1

2. 乘法法则：分步计数（“先… 再…”）

定义：如果完成一件事需要分两步，第一步有 m 种方法，第二步有 n 种方法，且第一步的结果不影响第二步，那么总方法数是 m×n 种。核心是 “分步”—— 两步都完成才算完成任务，步骤间独立。

例子 1：搭配衣服

上衣有 2 件（T 恤、衬衫），裤子有 3 件（牛仔裤、运动裤、西裤），总搭配数是 2×3=6 种（T 恤 + 牛仔裤、T 恤 + 运动裤、T 恤 + 西裤、衬衫 + 牛仔裤、衬衫 + 运动裤、衬衫 + 西裤）。

例子 2：编程中的参数组合

一个接口有两个参数：size（可选 “small”、“medium”、“large”，3 种）、color（可选 “red”、“blue”，2 种），总参数组合数是 3×2=6 种，需要测试 6 次才能覆盖所有情况。

代码示例：生成参数组合

生成所有参数组合的列表，方便测试：

python

def generate_param_combinations(sizes, colors):
    combinations = []
    # 分步：先选size，再选color
    for size in sizes:
        for color in colors:
            combinations.append((size, color))
    return combinations

# 测试：size=["small","medium"], color=["red","blue"]→4种组合
sizes = ["small", "medium"]
colors = ["red", "blue"]
print(generate_param_combinations(sizes, colors)) 
# 输出[("small","red"), ("small","blue"), ("medium","red"), ("medium","blue")]

加法与乘法的区别：一句话分清

  • 加法法则：“或” 关系（要么 A 类，要么 B 类）；
  • 乘法法则：“与” 关系（先 A 步，再 B 步）。

比如 “选上衣或裤子” 是加法（但实际搭配是乘法，因为要 “上衣与裤子”），“选红色上衣或蓝色上衣” 是加法。

四、置换：n 个元素的全排列（有序、无重复）

定义：将 n 个不同的元素按顺序排列，总共有多少种排法？这就是置换（Permutation of n elements），记为 n!（n 的阶乘）。

1. 置换的推导：从乘法法则出发

以 “3 张牌 A、B、C 的全排列” 为例：

  • 第 1 张牌：有 3 种选法（A、B、C）；

  • 第 2 张牌：选了第 1 张后，剩 2 种选法；

  • 第 3 张牌：选了前 2 张后，剩 1 种选法；

    总排法 = 3×2×1=6 种（ABC、ACB、BAC、BCA、CAB、CBA）。

推广到 n 个元素：n! = n×(n-1)×(n-2)×…×1，其中 0! 定义为 1（基底条件，对应 “0 个元素的排列只有 1 种：空排列”）。

2. 编程实现：递归生成全排列

利用递归（联系前面的递归思维），每次固定第 k 个元素，递归排列剩下的 n-k 个元素：

python

def permute(arr):
    """生成数组的全排列（递归实现）"""
    n = len(arr)
    if n == 0:
        return [[]]  # 基底：空数组的排列是[[]]
    if n == 1:
        return [arr]  # 基底：1个元素的排列是自身
    # 递归：固定第0个元素，排列剩下的元素，再将第0个元素插入所有位置
    result = []
    for i in range(n):
        # 固定arr[i]作为第一个元素
        fixed = arr[i]
        # 剩下的元素（排除arr[i]）
        remaining = arr[:i] + arr[i+1:]
        # 递归排列剩下的元素
        for p in permute(remaining):
            result.append([fixed] + p)
    return result

# 测试：[1,2,3]的全排列→6种
print(permute([1,2,3]))
# 输出[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

3. 置换与归纳法：证明 n! 的正确性

用前面学的数学归纳法，证明 “n 个元素的全排列数是 n!”：

  • 基底条件：n=1 时，1! =1，正确；

  • 归纳条件：假设 k 个元素的全排列数是 k!，证明 k+1 个元素的全排列数是 (k+1)!。

    推导：k+1 个元素中，选 1 个作为第一个元素（k+1 种选法），剩下 k 个元素的排列数是 k!（归纳假设），总排法 =(k+1)×k!=(k+1)!，正确。

五、排列：从 n 个元素中选 k 个排列（有序、无重复）

定义：从 n 个不同元素中，选 k 个按顺序排列，总排法数记为 P (n,k)（或 A (n,k)）。

1. 排列的推导：乘法法则的延伸

以 “从 5 张牌中选 3 张排列” 为例：

  • 第 1 张牌：5 种选法；

  • 第 2 张牌：剩 4 种选法；

  • 第 3 张牌：剩 3 种选法；

    总排法 = 5×4×3=60 种，即 P (5,3)=5×4×3。

推广到一般情况：P(n,k) = n×(n-1)×(n-2)×…×(n-k+1) = n! / (n-k)!（因为 n! = n×(n-1)×…×(n-k+1)×(n-k)!，约分后得到 P (n,k)）。

2. 编程实现：生成选 k 个元素的排列

在全排列的基础上，只保留长度为 k 的结果：

python

def permute_k(arr, k):
    """从数组中选k个元素生成排列"""
    n = len(arr)
    if k == 0:
        return [[]]
    if k > n:
        return []  # 选的数量超过元素总数，无排列
    result = []
    for i in range(n):
        fixed = arr[i]
        remaining = arr[:i] + arr[i+1:]
        # 递归选k-1个元素排列
        for p in permute_k(remaining, k-1):
            result.append([fixed] + p)
    return result

# 测试：从[1,2,3,4,5]选3个排列→60种（此处只展示前5种）
arr = [1,2,3,4,5]
k = 3
perms = permute_k(arr, k)
print(f"总排列数：{len(perms)}")  # 输出60
print("前5种排列：", perms[:5])
# 输出前5种：[[1,2,3], [1,2,4], [1,2,5], [1,3,2], [1,3,4]]

六、组合：从 n 个元素中选 k 个组合（无序、无重复）

定义：从 n 个不同元素中，选 k 个不考虑顺序，总选法数记为 C (n,k)（或 C (n,k)）。组合与排列的核心区别是 “无顺序”—— 比如 (1,2) 和 (2,1) 是同一组合，但不同排列。

1. 组合的推导：排列去重

因为 “选 k 个元素的排列数”=“选 k 个元素的组合数”דk 个元素的全排列数”（先选组合，再排序），所以：C(n,k) = P(n,k) / k! = [n! / (n-k)!] / k! = n! / [k!×(n-k)!]

以 “从 5 张牌中选 3 张组合” 为例：C (5,3) = P (5,3) / 3! = 60 / 6 = 10 种（ABC、ABD、ABE、ACD、ACE、ADE、BCD、BCE、BDE、CDE）。

2. 组合的递归公式：用归纳法证明

组合数有一个重要的递归公式：C (n,k) = C (n-1,k-1) + C (n-1,k)，这个公式可以用 “是否选第 n 个元素” 来理解：

  • 选第 n 个元素：需要从剩下的 n-1 个中选 k-1 个，即 C (n-1,k-1)；

  • 不选第 n 个元素：需要从剩下的 n-1 个中选 k 个，即 C (n-1,k)；

    总选法 = 两者之和（加法法则）。

用归纳法证明这个公式：

  • 基底条件：k=0 或 k=n 时，C (n,k)=1（选 0 个元素只有 1 种方法，选 n 个元素也只有 1 种方法）；
  • 归纳条件：假设 C (n-1,k-1) 和 C (n-1,k) 成立，证明 C (n,k) 成立（由加法法则直接推导，正确）。

3. 编程实现：生成选 k 个元素的组合

用递归实现组合生成，基于 “选或不选” 的逻辑：

python

def combine(arr, k):
    """从数组中选k个元素生成组合（递归实现）"""
    n = len(arr)
    if k == 0:
        return [[]]
    if k > n:
        return []
    # 情况1：选第一个元素，再从剩下的n-1个中选k-1个
    take_first = [[arr[0]] + c for c in combine(arr[1:], k-1)]
    # 情况2：不选第一个元素，再从剩下的n-1个中选k个
    skip_first = combine(arr[1:], k)
    # 总组合=两种情况之和（加法法则）
    return take_first + skip_first

# 测试：从[1,2,3,4,5]选3个组合→10种
arr = [1,2,3,4,5]
k = 3
combs = combine(arr, k)
print(f"总组合数：{len(combs)}")  # 输出10
print("所有组合：", combs)
# 输出：[[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]]

七、实战：排列组合的复杂场景

前面讲的都是 “无重复、有序 / 无序” 的基础场景，实际编程中还会遇到 “允许重复”“带约束条件” 的情况，我们用两个实战例子巩固。

实战 1：重复组合（允许重复选择）

问题：有 A、B、C3 种药品，选 100 粒调剂，每种至少 1 粒，不考虑顺序，有多少种方法？这是 “重复组合” 问题，公式为 C (n+k-1,k-1)（n 种元素，选 k 个，允许重复，每种至少 1 个）。推导：先给每种药品分 1 粒（满足至少 1 粒），剩下 97 粒自由分配，相当于 “3 种元素选 97 粒，允许重复”，公式为 C (3+97-1,97)=C (99,2)=4851 种。

代码实现：重复组合的生成（以 “3 种选 5 粒，每种至少 1 粒” 为例）：

python

def combine_with_repetition(elements, k):
    """重复组合：从elements选k个，允许重复，每种至少1个"""
    n = len(elements)
    if k < n:
        return []  # 每种至少1个，k不能小于n
    if n == 1:
        return [[elements[0]] * k]
    # 情况1：选至少1个elements[0]，再从所有元素选k-1个（允许重复）
    take = [[elements[0]] + c for c in combine_with_repetition(elements, k-1)]
    # 情况2：不选elements[0]，再从剩下的n-1个选k个（每种至少1个）
    skip = combine_with_repetition(elements[1:], k)
    return take + skip

# 测试：3种药品选5粒，每种至少1粒→C(3+5-1,5-3)=C(7,2)=21种
drugs = ["A", "B", "C"]
count = 5
combs = combine_with_repetition(drugs, count)
print(f"总组合数：{len(combs)}")  # 输出21
print("前5种组合：", combs[:5])
# 输出前5种：[["A","A","A","B","C"], ["A","A","A","C","B"], ["A","A","B","A","C"], ["A","A","B","B","C"], ["A","A","B","C","A"]]

实战 2：带约束的排列（容斥原理）

问题：5 张牌（2 张王牌、J、Q、K）排成一排，至少一端是王牌的排法有多少种？（不区分大小王牌）用 “容斥原理”（联系前面的逻辑章节）：总排列数 - 两端都不是王牌的排列数。

  • 总排列数：不区分大小王牌，先算区分的情况再除以 2（王牌重复度），即 P (5,5)/2=120/2=60 种；
  • 两端都不是王牌：从 J、Q、K 选 2 个排两端（P (3,2)=6），中间 3 张（2 张王牌 + 剩下 1 张）排列（P (3,3)/2=3），总排法 = 6×3=18 种；
  • 至少一端是王牌：60-18=42 种。

代码验证：

python

def count_ace_at_ends(cards):
    """统计至少一端是王牌的排列数（不区分大小王牌）"""
    # 生成所有全排列
    all_perms = permute(cards)
    # 去重（不区分大小王牌，假设王牌是"J1"和"J2"）
    unique_perms = []
    seen = set()
    for p in all_perms:
        # 将"J1"和"J2"统一为"J"，再转tuple去重
        normalized = tuple("J" if c in ["J1", "J2"] else c for c in p)
        if normalized not in seen:
            seen.add(normalized)
            unique_perms.append(normalized)
    # 统计至少一端是"J"的排列
    count = 0
    for p in unique_perms:
        if p[0] == "J" or p[-1] == "J":
            count += 1
    return count, unique_perms

# 测试：5张牌["J1","J2","J","Q","K"]（J1、J2是王牌）
cards = ["J1", "J2", "J", "Q", "K"]
count, perms = count_ace_at_ends(cards)
print(f"至少一端是王牌的排法数：{count}")  # 输出42

八、小结：排列组合的核心是 “认清计数对象”

今天我们从加法 / 乘法法则出发，逐步讲解了置换、排列、组合，核心收获是：

  1. 计数前先明确两个问题：是否考虑顺序？是否允许重复？

    • 置换：有序、无重复、全选（n 选 n）；
    • 排列：有序、无重复、选 k 个（n 选 k）；
    • 组合：无序、无重复、选 k 个（n 选 k）；
    • 重复组合：无序、允许重复、选 k 个。

  2. 公式不是死记的：所有公式都源于 “加法法则” 和 “乘法法则”，比如组合数的递归公式是 “选或不选” 的分类（加法），排列数是 “分步选元素” 的分步（乘法）。

  3. 编程实现的关键：递归是生成排列组合的常用方法，本质是 “拆解问题为小问题”（联系前面的递归和归纳法），去重则需要根据 “是否重复”（如王牌不区分）做特殊处理。

排列组合是后面 “概率统计” 章节的基础 —— 比如 “抽到王牌的概率” 就是 “王牌的组合数 / 总组合数”。下一篇我们将学习 “递归” 的深入应用，比如斐波那契数列、汉诺塔，而递归生成排列组合正是递归思维的典型实践。

如果你在编程中遇到过计数问题，比如生成测试用例、计算任务调度方案，欢迎在评论区分享你的经历！

【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
开发者 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入