2

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) 順列は 1 つしか得られません。(0,2) -> (1,0) ->

私は持っていると思っていました：

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

別の例では、2 つの順列しか得られない 4 つのポイントがあります。

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

アイデアはありますか？

4

5 に答える 5

5

next_permutation新しい順列がfalse古い順列よりも辞書編集的に大きくない場合です。

あなたの順序(1,0)は より小さいと言っているので(0,2)、シーケンス{(1,0), (0,2)}は辞書編集的に より小さく{(0,2), (1,0)}、 すぐですnext_permutation。false

同じ理由が、あなたの 4 ポイントの例の背後にあります。

すべての順列を調べたい場合は、最初にシーケンスをソートする必要があります。

于 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 に答える
0

std::next_permutation を作成してすべての順列を与えるには、最初のベクトルをループの前に同じコンパレータでソートする必要があります。

于 2013-10-15T12:17:12.880 に答える