Searching for overlapping integers in different indexes of tuples in a vector

I was wondering how one can search for overlaps in a vector of tuples.

For example, I have the vector<tuple<int, int, int>> combo;, and the elements of the vector is:

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

Here, you can tell that the bottom 8 tuples are just repeats of the first 4, except the integers are reordered in a different way. I want to find the non-overlapping combinations of the elements, not the permutations of the elements.

If the 1st index of the tuple is called , second if called , and third is called , then in other words, left, middle, and right can overlap with itself, but not with the other 2 indexes.

Searching for overlapping integers in different indexes of tuples in a vector

Convert the elements to a canonical representation. This allows you use a set data structure or similar to identify duplicates.

I'm assuming here you're trying to find permutations that do not result in one of the elements remaining in place, i.e. for values { a, b, c} the matching permutations would be

{ a, b, c }
{ b, c, a }
{ c, a, b }

Furthermore I'm assuming even if multiple values are the same, they could be considered as listed in any order, i.e. { 1, 1, 2 } would match { 1, 2, 1 } even though the first element remains equal, since we could consider the first element to be the second one in the original.

This allows us use the lexicographically minimal alternative that as the canonical representation.

The following code uses std::array for convenience.

#include 
#include 
#include 
#include 

using ValueType = std::array;

constexpr ValueType ToCanonical(ValueType const& original)
{
    ValueType p1{ original[1], original[2], original[0] };
    ValueType p2 { original[2], original[0], original[1] };

    return (std::min)({ original, p1, p2 });
}

int main(void) {
    std::vector const values
    {
        {10, 101, 1},
        {10, 102, 2},
        {12, 102, 3},
        {14, 90, 4},
        {1, 10, 101},
        {2, 10, 102},
        {3, 12, 102},
        {4, 14, 90},
        {101, 1, 10},
        {102, 2, 10},
        {102, 3, 12},
        //{90, 4, 14},
        //{10, 101, 1},
        //{101, 10, 1},
        //{10, 1, 101},
        //{1, 101, 10},
        //{1, 1, 2},
        //{1, 2, 1},
        //{2, 1, 1},
    };


    std::map indices;

    for (size_t i = 0; i != values.size(); ++i)
    {
        auto insertResult = indices.try_emplace(ToCanonical(values[i]), i);
        if (!insertResult.second)
        {
            std::cout << "The element at index " << i << " is a duplicate of the element at index " << insertResult.first->second << '\n';
        }
    }
    return 0;
}

Searching for overlapping integers in different indexes of tuples in a vector

Searching for overlapping integers in different indexes of tuples in a vector

0 Comment

0 Comment

About the Author

Question Info

Related Question

Kotlin序列化对象到YAML，其中YAML节点应该是一个值

如何检测Linux中没有提交到dbus的蓝牙事件?

linux环境VCS使用

我如何去寻找Kotlin应用程序的最小最大值

How to rotate a label in a zpl 90 degrees (php)?

Spring集成-自定义WebFlux OutboundGateway使用的objectapper

dotnet 6 blazor项目部署到linux后，自动退出的问题？

Linux系统启动流程分析，是否有人能够详细的阐述一下？

ArrayIndexOutOfBoundsException:数组长度为3的索引3越界.主要(复制)

winform将listview里的数据导出到excel里问题求解？