0
Follow
0
View

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

dkzhu120 注册会员
2023-01-25 20:49

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, original, original };
ValueType p2 { original, original, original };

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;
}
``````

Publish Time
2023-01-25 20:49
Update Time
2023-01-25 20:49