排列去重问题

2026年03月21日 Dev-Env

排列去重问题

整理代码仓库的时候发现一段陈年代码，里面不可思议地套了6层for循环，而且注释上面还有着“未完成”的标记，这不禁让我产生疑问，“这是个什么神秘东西？”

检查后发现，这个代码似乎尝试输出“ecstre”的所有排列组合？为何如此大动干戈？

用排列组合计算答案

首先用排列组合算法计算答案应该是多少。

排列公式和全排列公式，从n个不同元素中取出m个： $P(n,m)=A^m_n=\frac{n!}{(n-m)!}$ 当m=n时 $P(n,n)=n!$

有重复元素的全排列：若一个集合中有n个元素，其中第i种元素重复 $n_i$ 次，且 $n_1+n_2+...+n_k=n$ ，则所有这些元素的全排列数目为 $\frac{n!}{n_{1}!n_{2}!\cdot\cdot\cdot n_{k}!}$

这道算法题是将6个字母ecstre全排列，其中有两个“e”是重复的元素，所以，可以先算出答案是： $P=\frac{6!}{2!}=\frac{720}{2}=360$

如何用算法思路解决问题？

思路一：

全排列：暴力排序，用6个嵌套的循环，冒6次泡；

去重：为了避免重复，将已经生成的结果存进一个字符串的数组，将每个结果挨个比对；

初学者写出这样的代码尚可谅解，现在写这样的东西不如拖出去乱棍打死；

这让我突然有点怀念以前那个环境了，这道题应该是出自XDOJ或者类似的地方；看似简单，实则引入了这样一个算法问题的基础：

如何将一个带有重复元素的序列进行全排列？

序：树在哪？

接下来要介绍的方法是“递归剪枝”和“字典序”；

提到“剪枝”，说明这里有一棵树，树在哪？

我们可以把这个需要全排列的数组，就以本题为例，这6个字符的全排列想象成一棵树，它的根结点为空，根结点的第一个子结点是字母e，而这个子结点的第一个子结点（也就是孙子结点）为c，如此可以按照e-c-s-t-r-e的顺序一直填充最左子结点直到叶子；

然后返回到根结点的子结点也就是第一个e的位置，它的子结点也可以是s，s下可以接一个c，于是一路到叶子我们又获取了一个e-s-c-t-r-e；

不难想象，路径上字符串中的每个位置上的字母只有一次出场机会，因此只要这棵树完整，我们就已经获得了所有的可能性，需要处理的麻烦事是识别出里面重复的部分；

当然，如果在纸面上方旁观，不难发现，由于排出的字符串以树的枝叶的形式出现，路径上的结点字母序相同的就是重复的字符串；如果人眼观察纸面倒是很好识别出来，但是对于计算机呢？

如果按照这样的思路处理，写出6层嵌套循环带一个需要每次与新结果比对的记录了所有已排列结果大表似乎是很自然的事情；

顺便一提，如果把字母排一下序，找找规律的话，似乎也能找到一点思路；排序之后，ceerst，把两个e的枝放在根结点相邻孩子的位置，并且按照类似的顺序继续排列它们的枝，它们雷同的枝就很好辨别出来了；

思路二：递归剪枝

/**
 * @brief 递归生成字符串 str[l..r] 的所有不重复排列，并打印
 * 
 * 该函数通过交换元素和回溯的方式，生成字符串 str 从索引 l 到 r（包含）的
 * 所有唯一排列。它通过剪枝避免因重复字符产生的重复排列。
 * 
 * @param str   字符数组（将被修改），当前处理的字符串
 * @param l     当前要固定的起始索引（0-based）
 * @param r     结束索引（包含）
 * @param count 指向整数计数器的指针，用于记录已输出的排列数（每输出一个排列自增1）
 * 
 * @note 调用前应确保 str 已排序，以便输出按字典序升序排列（非必须，但推荐）。
 * @note 递归深度为 r-l+1，对长字符串需注意栈溢出风险。
 * @note 函数直接打印排列，不返回结果集。
 */
void permute(char *str, int l, int r, int *count) {
    if (l == r) {
        printf("%4d %s\n", ++(*count), str);
        return;
    }
    for (int i = l; i <= r; i++) {
        // 检查从 l 到 i-1 是否有与 str[i] 相同的字符
        int duplicate = 0;
        for (int j = l; j < i; j++) {
            if (str[j] == str[i]) {
                duplicate = 1;
                break;
            }
        }
        if (duplicate) continue;   // 避免重复交换

        swap(&str[l], &str[i]);
        permute(str, l + 1, r, count);
        swap(&str[l], &str[i]);    // 回溯
    }
}

思路三：字典序

字典序其实比较好理解，就是把排序映射到数字化，本质上还是一种“哈希”和“鸽巢排序”思想；

ecstre是什么，字符串而已嘛，其实还可以是5 3 19 20 18 5这一串数字；

而数字天然有一种很有意思的性质，

我们能一眼看出一个数串的大小，并且能马上得知最大值和最小值，

因为最大的数串一定是从大到小排列一遍，最小的数串一定是从小到大排列一遍；

比如说对1 1 4 5 1 4进行全排列，那么，至少最小的一定是111445，最大的一定是544111；

同时数字还有第二个很奇妙的性质，那就是不重复性质，因为两个重复的数字一定相等，这真的很有意思；

配合上一条，一个“确定的”起点状态，和一个“确定的”终点状态，和一永不重复的性质，意味着什么？

意味着我们获得了不重复的全排列；

比如，一个数串1 1 4 5 1 4从最小到最大的变化过程中：

111445→111454→114145→114154→114415

很快就能注意到，推算数字位置的过程，就是在试图找出一个规律排列的过程；

只不过有很确凿的证据能告诉我，这一次排对了还是排错了；

这就是Next Permutation算法，

要获得字典序中的下一个数字，通常指的是对一个数字序列（如数组或字符串）求下一个更大的排列。经典的算法是 Next Permutation（下一个排列），其步骤如下：

从右向左找到第一个升序对，即找到最大的索引 i，使得 nums[i] < nums[i+1]。若不存在这样的 i，说明当前排列已经是最大字典序，直接反转整个序列得到最小排列。

从右向左找到第一个大于 nums[i] 的数，即找到最大的索引 j（j > i），使得 nums[j] > nums[i]。

交换 nums[i] 和 nums[j]。

反转从 i+1 到末尾的子序列，使其变为升序（因为原来它是降序的，反转后即最小）。

这个算法时间复杂度 O(n)，空间复杂度 O(1)。

伪代码(我对LLM说缩进看不清，让换成大括号，结果看起来像C)是：

NextPermutation(nums) {
    n = nums.length
    i = n - 2

    // 步骤1：从右向左找第一个升序对
    while (i >= 0 and nums[i] >= nums[i+1]) {
        i = i - 1
    }

    if (i >= 0) {
        // 步骤2：从右向左找第一个大于 nums[i] 的数
        j = n - 1
        while (nums[j] <= nums[i]) {
            j = j - 1
        }
        // 步骤3：交换
        swap(nums[i], nums[j])
    }

    // 步骤4：反转 i+1 到末尾
    left = i + 1
    right = n - 1
    while (left < right) {
        swap(nums[left], nums[right])
        left = left + 1
        right = right - 1
    }

    return nums
}

思想挺有意思，主要是判断的时候能用上现成的工具：“数数”；

当然，具体数的时候还是得用点算法知识；

Next Permutation是个O(n)算法。

附录

虽然这里没有用上，但还是提一下，组合公式是(n个不同元素中不考虑顺序地取出m个元素) $C(n,m)=\frac{n!}{m!(n-m)!}$ 就当复习了

Knighthana

2026/04/20

文章分类

文章归档

最新文章

排列去重问题

排列去重问题

用排列组合计算答案

如何用算法思路解决问题？

思路一：

序：树在哪？

思路二：递归剪枝

思路三：字典序

附录