2D点的排列

Question

我想探索2d点的所有排列(2D阵列中的x,y坐标)我的2d点结构是:

struct pos_t {
    int x; int y; 
    pos_t(){x = 0 ; y = 0;} 
    pos_t(int X, int Y){x=X; y=Y;}
    pos_t(pos_t const & r) {x = r.x; y=r.y;}
    pos_t& operator=(pos_t const & r) {x = r.x; y=r.y; return *this;}
    bool operator < ( pos_t& p2)
    {
        return (x+y) < (p2.x+p2.y);
    }
    friend ostream& operator << (ostream &o, const pos_t& p)
    {
        return o << "(" << p.x << "," << p.y << ")";
    }
};

使用pos_t调用treasurePos(vector<pos_t>)的向量,我使用下面的代码迭代其他不同的排列并显示每个.

    do {
        copy(begin(treasurePos), end(treasurePos), ostream_iterator<pos_t>(cout, " -> "));
        cout << endl;
    } while ( std::next_permutation(begin(treasurePos),end(treasurePos)) );

但是在我的向量中有以下pos_t元素:(0,2)和(1,0)我只得到一个排列: (0,2) -> (1,0) ->

我希望有:

(0,2) -> (1,0) -> 
(1,0) -> (0,2) -> 

另一个例子,有4个点,我只得到2个permutatins:

(1,3) -> (2,2) -> (3,0) -> (3,1) -> 
(1,3) -> (2,2) -> (3,1) -> (3,0) -> 

你有个主意吗？

Answer 1

next_permutation是false当新的排列是不是字典序比老更大.

由于您的订货说,(1,0)小于(0,2),顺序{(1,0), (0,2)}是字典顺序小于{(0,2), (1,0)},并且 next_permutation是false马上.

你的四点例子背后也有同样的道理.

如果要查看所有排列,则应首先对序列进行排序.