CODEWITHSUNDEEP
c++stdstdvector
michip96
michip96

Reputation: 363

What is the best way to get a permutation index list of a given vector

In my application I solve a geometric problem on a given list of points.

0 x0 y0
1 x1 y1
...

The solution file should contain a specific ordering of the points which are represented as a list of their indexes.

1
0
...

After solving the problem I have a result = std::vector<Point>() vector of point objects in a certain order as well as the original list of points as an original = std::vector<Point>() vector. Both vectors naturally have the same size. To generate the output file I go through the result vector and search for the index of the point in the original vector. This is quite inefficient because it does need O(n^2) time. As a slight improvement I do the following:

std::ofstream out(filename);

std::vector<int> indices(instance.size);
std::iota(indices.begin(), indices.end(), 0);

for(auto &point : instance.result.points)
{
    for(std::size_t i=0; i<indices.size(); i++)
    {
        int id = indices[i];
        if(point == instance.points[id])
        {
            out << id << std::endl;
            indices.erase(indices.begin()+i);
            break;
        }
    }
}

out.close();

This allows me to not revisit the points that I already found before. Sadly for a 1 million point instance, this process exceeds my time limit and I don't want the export of my solution to take more time than solving the problem itself. Is there a way to efficiently get the indexes of a premutation of some vector in C++? The solution can use a lot of memory if desired.

Upvotes: 0

Views: 157

Answers (2)

Slava
Slava

Reputation: 44268

One of the simple to implement and quite efficient solution is to create a temporary std::unordered_map<Point,size_t> where key is the point and value is position inside original, then do lookup in that map. Details on how to use your (or library provided) data type as a key in std::unordered_map provided here

Upvotes: 2

Paul92
Paul92

Reputation: 9062

You can extend the Point structure to contain the original id, besides the position.

Upvotes: 1

Related Questions