如何在C++元组向量中查找跨索引重叠整数并排除排列重复项

问题说明 #

待处理对象为vector<tuple<int, int, int>> combo;类型的三元组向量，其中存在大量同组三个值重排生成的排列重复项，需要过滤这类重复、保留唯一值组合，筛选规则如下：

• 三元组三个索引位置按顺序定义为left（第0位）、middle（第1位）、right（第2位）
• 三个位置各自的内部取值允许重复，但任意取值不能同时出现在另外两个索引位置上。

核心思路 #

排列重复的本质是重复条目和原条目包含的三个值完全一致，仅存放顺序不同，只要给每组相同的三个值生成不随顺序变化的唯一标识，即可完成去重：

• 对每个三元组，取出left、middle、right三个位置的值后做排序，生成固定顺序的键。同一组三个值不管怎么排列，排序后生成的键完全相同
• 用集合存储已经出现过的键，遍历原向量时，只有当前元组对应的键未在集合中出现过，才把这条元组加入结果集，同时将键存入集合；已经存在对应键的元组直接跳过
• 去重后的结果天然符合筛选规则：每个位置内部允许同值重复（比如left位可以多次出现10），且单个值不会跨另外两个索引位置出现。

代码实现 #

#include <vector>
#include <tuple>
#include <set>
#include <algorithm>

std::vector<std::tuple<int, int, int>> filter_permutation_duplicates(std::vector<std::tuple<int, int, int>>& combo) {
    std::vector<std::tuple<int, int, int>> filtered_result;
    std::set<std::tuple<int, int, int>> recorded_keys;

    for (const auto& entry : combo) {
        int val0 = std::get<0>(entry);
        int val1 = std::get<1>(entry);
        int val2 = std::get<2>(entry);
        
        // 生成排序后的归一化键，屏蔽排列顺序的影响
        int val_arr[3] = {val0, val1, val2};
        std::sort(val_arr, val_arr + 3);
        auto unique_key = std::make_tuple(val_arr[0], val_arr[1], val_arr[2]);

        // 兼容C++20之前版本可以把判断条件改为 recorded_keys.find(unique_key) == recorded_keys.end()
        if (!recorded_keys.contains(unique_key)) {
            recorded_keys.insert(unique_key);
            filtered_result.push_back(entry);
        }
    }
    return filtered_result;
}

测试效果 #

传入给出的示例数据执行后，返回结果仅保留4条非重复元组，后8条排列生成的重复项会被全部过滤：

{10, 101, 1},
{10, 102, 2},
{12, 102, 3},
{14, 90, 4}

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