统计无相邻重复的优美排列数的C++代码优化方法

• 给定一个整数数组，数组中每个整数最多出现2次，需要统计该数组对应的优美排列总数量。
• 优美排列定义：排列中不存在相邻位置元素值相等的情况，即对于任意下标i ∈ [0, n-2]，都满足P[i] != P[i+1]。

struct hashFunction
{
    size_t operator()(const vector<int>& myVector) const
    {
        std::hash<int> hasher;
        size_t answer = 0;
        for (int i : myVector)
        {
            answer ^= hasher(i) + 0x9e3779b9 +
                (answer << 6) + (answer >> 2);
        }
        return answer;
    }
};

bool beautiful(vector<int>& ds)
{
    for (int i = 0; i < ds.size(); i++)
    {
        if (ds[i] == ds[i + 1])
        {
            return false;
        }
    }
    return true;
}

void permutation(vector<int>& arr, int index,
    unordered_set<vector<int>, hashFunction>& unorderedsetOfVectors)
{
    if (unorderedsetOfVectors.find(arr) != unorderedsetOfVectors.end()) return;
    if (index == arr.size())
    {
        if (beautiful(arr) == true)
        {
            unorderedsetOfVectors.insert(arr);
            return;
        }
    }

    for (int i = index; i < arr.size(); i++)
    {
        swap(arr[index], arr[i]);
        permutation(arr, index + 1, unorderedsetOfVectors);
        swap(arr[index], arr[i]);
    }
}

int permutations(vector<int> arr)
{
    unordered_set<vector<int>, hashFunction> unorderedsetOfVectors;
    permutation(arr, 0, unorderedsetOfVectors);
    return unorderedsetOfVectors.size() % 1000000007;
}

• 时间复杂度过高：暴力枚举所有全排列的复杂度是O(n!)，数组长度超过10之后运算量就会达到千万级，几乎无法运行。
• 无效计算太多：等排列完全生成后才校验是否符合优美排列规则，大量存在相邻相等元素的无效排列也被完整生成，浪费算力。
• 去重逻辑低效且有风险：用unordered_set存储所有生成的排列来去重，内存开销极高，自定义哈希函数还存在哈希碰撞导致结果错误的可能。
• 存在代码bug：beautiful函数的循环条件写为i < ds.size()，当i取到最后一个元素下标时，访问ds[i+1]会触发数组越界。

1. 回溯剪枝+同层去重（适合n≤15的小规模场景） #

• 提前剪枝：每次向当前排列末尾添加元素时，直接判断新元素和排列最后一个元素是否相等，相等就跳过这个分支，不用等排列生成完再校验，能砍掉90%以上的无效分支。
• 排序后同层去重：先把原数组排序，回溯选数时如果当前元素和同层上一个选过的元素值相同，直接跳过，从根源避免生成重复排列，完全不需要用集合存储所有排列，内存开销直接降到O(n)级别。

优化后的回溯实现代码：

#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;

void backtrack(vector<int>& arr, vector<bool>& used, int lastNum, int& res, int depth) {
    if (depth == arr.size()) {
        res = (res + 1) % MOD;
        return;
    }
    for (int i = 0; i < arr.size(); i++) {
        if (used[i]) continue;
        // 同层重复元素剪枝，避免生成重复排列
        if (i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue;
        // 相邻相等剪枝，不符合优美排列要求直接跳过
        if (arr[i] == lastNum) continue;

        used[i] = true;
        backtrack(arr, used, arr[i], res, depth + 1);
        used[i] = false;
    }
}

int countBeautifulPerm(vector<int> arr) {
    sort(arr.begin(), arr.end());
    vector<bool> used(arr.size(), false);
    int res = 0;
    // 初始lastNum传入数组中不可能出现的值即可，这里示例用-1e9-1，可根据实际数据范围调整
    backtrack(arr, used, -1000000001, res, 0);
    return res;
}

2. 容斥原理（适合n≥15的大规模场景） #

如果数组长度更大，回溯法依然会有性能瓶颈，可以利用「每个元素最多出现2次」的条件，用容斥原理直接计算，时间复杂度可以降到O(n)。
假设数组总长度为n，其中有k个元素各出现2次，剩余n-2k个元素各出现1次，公式为：
$$ans = \sum_{i=0}^{k} (-1)^i * \binom{k}{i} * \frac{(n-i)!}{2^{k-i}}$$

公式解释：我们枚举强制相邻的重复元素对数i，选i对重复元素绑定为单个整体，此时总元素个数为n-i，其中剩余k-i对未绑定的重复元素会产生重复排列，因此要除以2的(k-i)次方去重；最后按照容斥规则，i为偶数时加、i为奇数时减，累加结果就是最终答案。
只需要预处理阶乘、组合数、2的幂次的模值，就可以在O(k)时间内算出结果，n到1e5级别都可以轻松处理。

内容的提问来源于stack exchange，提问作者dipanshu Srivastava