1. 简介
在本教程中，我们将介绍递归和迭代两种算法，用于生成带有重复的排列（Permutations with Repetition）。这类问题属于组合数学中的基础问题，与生成集合的所有 k-组合（k-combinations）类似。
2. 带重复的排列
带重复的排列是指从集合 A 中选择 k 个元素，按顺序组成元组，允许元素重复。我们称这样的元组为 k-元组（k-tuples）。
例如，集合 A = {1, 2, 3, 4, 5, 6, 7}，k = 4 时，以下都是有效的 4-元组：
(1,1,1,1)
(1,2,3,4)
(5,4,2,2)
如果我们集合 A 的大小为 n，则共有 n^k 个这样的排列。为了简化表示，我们通常将集合 A 表示为 {1, 2, ..., n}，因为任意 n 个元素的集合都可以通过映射转换成这个形式。
我们用简写形式如 1234 表示元组 (1,2,3,4)。
3. 递归算法生成重复排列
我们可以基于 k 进行归纳定义：
- 当 k = 0 时，唯一可能的排列是空元组
[]。 - 当 k > 0 时，我们可以将 {1, 2, ..., n} 中的每个数字作为前缀，添加到所有 k-1 长度的排列上，从而得到所有 k 长度的排列。
3.1. 伪代码
algorithm Find(n, k):
if k == 0:
return { [ ] }
else:
tuples_k_minus_1 = Find(n, k - 1)
tuples_k = empty set
for tuple in tuples_k_minus_1:
for i from 1 to n:
new_tuple = prepend i to tuple
tuples_k = tuples_k ∪ { new_tuple }
return tuples_k
3.2. 示例
假设 n = 5，k = 3：
Find(n, 2)会返回 25 个 2-元组，例如11, 12, ..., 55。- 接着对每个 2-元组前缀 1~5，得到所有 3-元组，共 125 个。
这种方式虽然逻辑清晰，但缺点也很明显：空间复杂度是 **O(n^k)**，对于大 k 来说不可行。
4. 迭代算法生成重复排列
为了避免一次性生成所有排列，我们可以采用迭代方式，按需生成下一个排列。这样可以将空间复杂度降低到 **O(k)**。
基本思路是：
- 初始化为第一个排列
[1, 1, ..., 1] - 不断调用
Next(x, n, k)获取下一个排列 - 直到返回
failure为止
4.1. 生成下一个排列的逻辑
我们从右往左查找第一个小于 n 的元素 x_j，将其加 1，然后将其右侧所有元素置为 1。如果所有元素都等于 n，则说明这是最后一个排列。
例如：
- 输入排列为
12737，n = 7 - 右侧连续为 7 的部分是
777 - 找到第一个小于 7 的元素是 2（位置为 2）
- 将 2 增为 3，右侧所有元素置为 1，得到
13111
4.2. 伪代码
algorithm Next(x, n, k):
j = k
while j >= 1 and x[j] == n:
j = j - 1
if j == 0:
return failure
for ℓ from j to k:
if x[ℓ] == n:
x[ℓ] = 1
else:
x[ℓ] = x[ℓ] + 1
return x
✅ 时间复杂度：O(k)
✅ 空间复杂度：O(k)
✅ 优势：适合内存受限场景，可按需处理排列
4.3. 示例
输入排列为 12777，n = 7：
- 找到最右边不是 7 的位置是 2（元素为 2）
- 加 1 得到 3，并将后面所有 7 替换为 1
- 得到新排列
13111
⚠️ 注意：如果使用 {0, 1, ..., n-1} 表示集合 A，Next() 的操作就相当于模 n 加法。
5. 总结
我们介绍了两种生成带重复排列的方法：
| 方法 | 特点 | 空间复杂度 |
|---|---|---|
| 递归算法 | 一次性生成所有排列 | O(n^k) |
| 迭代算法 | 按需生成下一个排列，节省内存 | O(k) |
✅ 推荐使用迭代算法，尤其在内存受限或只需处理部分排列时更合适。
❌ 如果只是想一次性获取所有排列，递归方法更简单直接，但要注意内存开销。