2

我想探索二维点的所有排列(二维数组中的 x,y 坐标)我的二维点结构是:

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 个排列:

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

你有想法吗?

4

5 回答 5

5

next_permutationfalse当新排列在字典上不大于旧排列时。

由于您的排序表示(1,0)小于(0,2),因此该序列按{(1,0), (0,2)}字典顺序小于{(0,2), (1,0)},并且 next_permutation立即为false

你的四点例子背后也是同样的原因。

如果要遍历所有排列,则应首先对序列进行排序。

于 2013-10-15T12:18:17.753 回答
1

最后我找到了为什么即使打电话给sort,我也永远不会得到所有排列(见我的回答......),但再次感谢您的帮助。

std::sort在任何调用之前提到调用的所有答案next_permutation都是正确的(这就是为什么我对大多数答案投了赞成票)。但实际上,这里最重要的是要注意lexicographic顺序取决于您使用的比较运算符。

默认参数是bool operator < ( ... ),但使用我提供的实现(见下文),(1,3)等于(3,1)。

bool operator < ( pos_t& p2)
{
    return (x+y) < (p2.x+p2.y);
}

这就是为什么我永远不会得到排列(即对于 N 个不同的元素,我们得到 N!排列)

一个正确的运算符pos_t将是:

bool operator < ( pos_t const & p) const
{
  return (x < p.x) || ((x == p.x) && (y < p.y));
}

现在我们可以对所有排列进行排序、循环和收集。

std::sort(begin(treasurePos), end(treasurePos));
do {
  vector<pos_t> c;
  copy(begin(treasurePos), end(treasurePos), back_inserter(c));

  copy(begin(c), end(c), ostream_iterator<pos_t>(cout, " -> "));
  cout << endl;

  treasure_order.push_back(c);

} while ( std::next_permutation(begin(treasurePos),end(treasurePos)) );

cout << "we stored " << treasure_order.size() << " path to get all the treasure (=nbTreasure! = " << fact((int)treasurePos.size()) << ")" << endl;
于 2013-10-16T10:51:30.860 回答
1

在 molbdnil 答案之上。要获得所有排列,应对初始集进行排序。所以,这应该可以解决问题。

std::sort(begin(treasurePos), end(treasurePos));
do {
    copy(begin(treasurePos), end(treasurePos), ostream_iterator<pos_t>(cout, " -> "));
    cout << endl;
} while ( std::next_permutation(begin(treasurePos),end(treasurePos)) );
于 2013-10-15T12:22:29.707 回答
0

为了使 std::next_permutation 给出所有排列,您的初始向量应该在循环之前使用相同的比较器进行排序。

于 2013-10-15T12:17:12.880 回答
-1

来自cplusplus.com

将 [first,last) 范围内的元素重新排列为下一个字典顺序更大的排列。

可以根据它们在字典上相互比较的方式对不同的排列进行排序;第一个这样排序的可能排列(按字典顺序比较小于所有其他排列的排列)是所有元素按升序排序的排列,最大的排列是所有元素按降序排列的。

如果函数可以确定下一个更高的排列,它会重新排列元素并返回 true。如果这是不可能的(因为它已经是最大可能的排列),它会根据第一个排列(按升序排序)重新排列元素并返回 false。

所以基本上,如果你想让它工作,起始排列必须是最小的。

于 2013-10-15T12:20:39.870 回答