Нахождение недоминируемых точек в 2D-векторе

Question

Мне нужно сгенерировать 100 случайных точек в n-мерном пространстве (для этой программы я установлю 2-мерные для лучшего понимания - поэтому 1 точка имеет 2 координаты) и найду недоминируемые точки. Что такое недоминируемая точка? Если у нас есть точки (x0,y0),...,(x99,y99), в паре i преобладает пара j, если xi<xj и yi<yj. Чтобы найти недоминируемые точки, мы можем сравнить их все друг с другом (не сравнивая одинаковые точки).

Итак, я подумал о создании двух 2D векторов, чтобы хранить в них одинаковые точки (points и temp), сравнить их друг с другом, и если в данный момент проверенная точка не является доминирующей среди всех остальных - положить его в nondominated контейнер. Проблема в том, что я не умею их сравнивать.

Вот небольшой фрагмент кода:

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <numeric>

using namespace std;

double genRand() {
    double temp = (double)rand() / RAND_MAX * 100.0 - 50.0;
    return temp;
}

void fill_row(vector<double> & row) {
    generate(row.begin(), row.end(), genRand);
}

void fill_matrix(vector<vector<double>> & matrix) {
    for_each(matrix.begin(), matrix.end(), fill_row);
}

int main()
{
    srand(time(NULL));

    vector<vector<double>> points(100, vector<double>(2));
    vector<vector<double>> temp(100, vector<double>(2));
    vector<vector<double>> nondominated;

    fill_matrix(points);
    copy(points.begin(), points.end(), temp.begin());

    return 0;
}

Примечание: я не могу использовать цикл в этой программе - только алгоритмы STL.

Answer 1

Использование remove_if:

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <numeric>

using namespace std;

vector< pair<double,double> > points(100);

double genRand()
{
    double temp = (double)rand() / RAND_MAX * 100.0 - 50.0;
    return temp;
}

void fill_row(pair<double,double> & row)
{
    row.first = genRand();
    row.second = genRand();
}

void fill_matrix(vector< pair<double,double> > & matrix)
{
    for_each(matrix.begin(), matrix.end(), fill_row);
}

bool IsDominated( pair<double,double>&  testpoint )
{
    // check if test point is dominated by any other point
    if ( any_of(points.begin(), points.end(), [ testpoint ](pair<double,double>& ip )
    {
        // is the test point dominated by iterated point
        // both x and y must be greated in order to dominate
        return ( ip.first > testpoint.first && ip.second > testpoint.second );
    }) )
        return true;

    // no other points dominated
    return false;
}

int main()
{
    srand(time(NULL));

    // generate some random points
    fill_matrix(points);

    // display points
    for_each( points.begin(), points.end(), []( pair<double,double>& ip )
    {
        cout << ip.first <<","<< ip.second <<" ";
    });
    cout << "\n";

    // remove the dominated points
    auto pend = remove_if(points.begin(), points.end(), IsDominated );
    pend--;

    std::cout << "\nUndominated points:\n";
    for_each( points.begin(), pend, []( pair<double,double>& ip )
    {
        cout << ip.first <<","<< ip.second <<" ";
    });

    return 0;
}

Для n измерений вам придется заменить pair<double,double> на ваш собственный класс.