用Python自己实现排列与组合——不靠现成函数 - 八级

自己动手写排列与组合——深入理解回溯算法

有没有想过，在玩“数字密码锁”时，从0~9中选出3个不重复的数字能组成多少种密码？或者，从5种口味的冰淇淋中任意选2种，能有多少种搭配？这些问题的答案，其实就是排列（讲究顺序）和组合（不讲究顺序）的计算。

平时我们可以直接用Python的itertools模块里的permutations和combinations来快速得到答案，但如果你想更深入地理解它们背后的原理，或者在考试、竞赛中不允许使用itertools，那么就需要自己动手写代码。下面我们就一步步手工实现排列和组合，并顺便学会一种超级有用的算法思想——回溯。

一、手工实现排列——像在玩“填空游戏”

核心思想：想象有n个空位，我们要依次往每个空位里放一个元素。放的时候，已经放过的元素不能再次使用（就像从口袋里拿糖果，拿走了就不能再拿）。当所有空位填满时，就得到一种排列。

生活例子：你有3张卡片，分别写着1、2、3，现在要排成3位数的密码（顺序不同密码不同）。先选第一个数字，有3种可能；然后选第二个数字，只能从剩下的2个里选；最后第三个数字只有1种。总共3×2×1=6种密码。而我们的代码就是模拟这个过程。

下面是用递归+回溯写的手工排列代码：

def my_permutations(elements, length):
    result = []                       # 存放所有排列结果
    used = [False] * len(elements)    # 标记哪些元素已被使用

    def backtrack(path):
        # 如果当前路径长度等于目标长度，则记录结果
        if len(path) == length:
            result.append(tuple(path))
            return
        for i in range(len(elements)):
            if not used[i]:
                used[i] = True
                path.append(elements[i])
                backtrack(path)        # 递归：继续填下一个位置
                path.pop()             # 撤销选择（回溯的关键）
                used[i] = False

    backtrack([])
    return result

# 测试：从 [1, 2, 3] 中选3个的全排列
elements = [1, 2, 3]
perms = my_permutations(elements, 3)
print("手动实现的排列：")
for p in perms:
    print(p)

运行结果：

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

代码讲解：

used数组像“已用标记牌”，记录每个元素是否已经被放在前面的空位里。
backtrack(path)函数负责填一个空位。path里保存了已经选好的元素序列。
递归调用backtrack(path)会继续填下一个空位，直到path长度等于length，就记录结果。
关键步骤path.pop()和used[i] = False：这是“回溯”——把刚刚放的元素拿回来，标记为未使用，这样就能去尝试下一个选择。就像我们在拼密码时，试完一个数字不成功就换另一个。

注意：如果length小于元素的总数，比如从[1,2,3,4]中选2个的排列，代码依然能正确工作，因为它只填满2个位置就停了。

二、手工实现组合——不看顺序，只看选择

核心思想：组合不关心顺序，只关心你选了哪些元素。所以我们需要避免产生(1,2)和(2,1)这样的重复。常用的方法是固定元素顺序：每次选择当前元素后，下一个元素只能从它后面的元素中选，这样就不会回头选到前面的元素。

生活例子：你从5种口味的冰淇淋（草莓、巧克力、香草、抹茶、芒果）中选2种，问有几种搭配。如果顺序无关（草莓+巧克力和巧克力+草莓算同一种），那么答案是10种。我们手动实现就要避免把相同元素的不同顺序当成两种。

下面是组合代码：

def my_combinations(elements, length):
    result = []                       # 存放所有组合结果

    def backtrack(start, path):
        # 如果当前路径长度等于目标长度，则记录结果
        if len(path) == length:
            result.append(tuple(path))
            return
        # 从start索引开始往后选，避免重复
        for i in range(start, len(elements)):
            path.append(elements[i])
            backtrack(i + 1, path)   # 下一个只能从i+1开始
            path.pop()               # 回溯

    backtrack(0, [])
    return result

# 测试：从 ['A', 'B', 'C'] 中选2个的组合
elements = ['A', 'B', 'C']
combs = my_combinations(elements, 2)
print("手动实现的组合：")
for c in combs:
    print(c)

运行结果：

('A', 'B')
('A', 'C')
('B', 'C')

代码讲解：

这里没有used数组，而是用一个start参数控制下一轮搜索的起始位置。
为什么从i+1开始？因为选了第i个元素后，它前面的元素已经被考虑过（或者已经在当前组合里），如果再从前面选就会重复。比如elements = ['A','B','C']，先选了'A'（i=0），下一轮只能从索引1（'B'）开始选，所以不会出现('A','B')和('B','A')同时存在的情况。
回溯时只要path.pop()，不需要修改start（因为start只在递归调用时传入参数，不影响外层循环）。

对比：组合的backtrack比排列简单，因为它不需要额外标记使用状态，只需控制起始位置。

三、新手最容易犯的错误

忘记回溯
写排列时忘记写path.pop()和used[i] = False，会导致path一直增长，最后结果全是重复的相同排列，或者程序死循环。记住：递归前做了什么，递归后一定撤销（恢复现场）。
组合中起始参数写错
新手可能会写成backtrack(0, path)而不是backtrack(i+1, path)，这样就会重复使用当前元素（比如(1,1)）或者产生(1,2)和(2,1)两种顺序。组合不允许重复选同个元素，也不区分顺序，所以必须从下一个位置开始。
深度混淆“长度”和“元素总数”
在排列中，如果length设为len(elements)，就是全排列；如果设为更小的数，就是选部分元素的排列。组合亦然。有时初学者会把length写成len(elements)但想得到部分排列，结果得到的全是全排列。
变量命名太复杂
有些人喜欢用temp_list、index等，但建议用path、start、used，配合注释，代码更清晰。

四、完整可运行的示例（整合排列和组合）

下面是一个完整的Python程序，包含了手工实现的排列和组合函数，并加了详细注释和测试用例：

# 手动实现排列（可指定选取个数）
def my_permutations(elements, length):
    result = []                       # 结果列表
    used = [False] * len(elements)    # 标记元素是否已用

    def backtrack(path):
        if len(path) == length:
            result.append(tuple(path))
            return
        for i in range(len(elements)):
            if not used[i]:
                used[i] = True
                path.append(elements[i])
                backtrack(path)
                path.pop()           # 回溯
                used[i] = False
    backtrack([])
    return result

# 手动实现组合（可指定选取个数）
def my_combinations(elements, length):
    result = []                       # 结果列表

    def backtrack(start, path):
        if len(path) == length:
            result.append(tuple(path))
            return
        for i in range(start, len(elements)):
            path.append(elements[i])
            backtrack(i + 1, path)   # 下一个从i+1开始
            path.pop()               # 回溯
    backtrack(0, [])
    return result

# -------- 测试 ----------
print("=== 测试排列 ===")
# 从 [1,2,3] 中选2个排列
perms = my_permutations([1, 2, 3], 2)
for p in perms:
    print(p)

print("\n=== 测试组合 ===")
# 从 ['苹果','香蕉','橘子','西瓜'] 中选3种水果的组合（生活中你选水果沙拉时的思考）
fruits = ['苹果', '香蕉', '橘子', '西瓜']
combs = my_combinations(fruits, 3)
for c in combs:
    print(c)

运行输出：

=== 测试排列 ===
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

=== 测试组合 ===
('苹果', '香蕉', '橘子')
('苹果', '香蕉', '西瓜')
('苹果', '橘子', '西瓜')
('香蕉', '橘子', '西瓜')

你看，排列有6种，组合只有4种——因为顺序不重要，所以('苹果','香蕉','橘子')和('苹果','橘子','香蕉')在组合里只算一种。

五、延伸与指引

回溯算法：上面两个函数都是“回溯法”的经典应用。回溯法专门用来解决“逐步构建答案，走不通就回头”的问题，比如八皇后问题、数独、迷宫寻路等。掌握了回溯，你就比别人多了一把解决问题的利器。
itertools模块：虽然我们自己实现了，但平时编程还是推荐用现成的itertools.permutations和itertools.combinations，因为它们由C语言实现，速度快、代码简洁。不过，当你理解背后的原理后，即使工具失灵，也不怕。
进阶练习：尝试修改代码，让排列和组合支持重复选取元素（即允许同一个元素被多次选择）。这时的算法叫做“可重复排列”和“可重复组合”（也叫多重集组合），比如密码锁中每个数字可以重复（如112、121等），你就需要把控制条件改一下。

现在，你可以用自己写的排列组合函数去算算“班级选班长、副班长有多少种可能”（排列），“有哪些委员组合”（组合），感受一下数学和编程结合的魅力吧！