c++ - 生成对象 vector 的所有可能排列

给定与网格上的城市位置相对应的坐标 vector ，如何生成这些点对象的每个排列？我怀疑将用户定义的类(在我的情况下为Point)与预定义的函数next_permutation一起使用存在问题。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Point
{
public:
double x, y;
Point(int x, int y);
friend ostream& operator<< (ostream &out, const Point &p);
};

Point::Point(int xCoord, int yCoord)
{
x = xCoord;
y = yCoord;
}

ostream& operator<< (ostream &out, const Point &p)
{
out << "(" << p.x << ", " << p.y << ")";
return out;
}

int main()
{
vector<Point> points = { {3,5}, {10,1}, {2,6} };

do
{
    for (Point pt : points)
    {
        cout << pt << " ";
    }
    cout << endl;
} while (next_permutation(points.begin(), points.end()));
}

最佳答案

有几件事，

首先要使用next_permutations，必须对容器进行排序。

其次，比较两个自定义对象的sort和next_permutations，您需要重载<运算符。

这样的事情应该工作:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Coords
{
 public:
    int x = 0;
    int y = 0;
    //This uses a simple lexicographical ordering, modify to suit your needs.
    bool operator <( const Coords& rhs )
    {
        if ( x == rhs.x )
        {
            return y < rhs.y;
        }
        else
        {
            return x < rhs.x;
        }
    }
};
vector<vector<Coords>> GetPermutaions( vector<Coords>& vec )
{
    vector < vector<Coords>> outVal ;
    //if you can guarantee vec will be sorted this can be omitted
    sort( vec.begin() , vec.end() );
    do
    {
        outVal.emplace_back( vec );
    } while ( next_permutation( vec.begin() , vec.end() ) );
    return outVal;
}

要记住的一件事是，此函数将使vec处于排序状态。如果需要原始状态，请创建vec的副本以进行排列。