7

next_permutation のような一連の値の次の組み合わせを提供する同等のライブラリまたは関数はありますか?

4

6 に答える 6

10

組み合わせ：同じトピックに関するMark Nelsonの記事から、next_combination http://marknelson.us/2002/03/01/next-permutation
順列：STLからstd::next_permutationがあります。

 template <typename Iterator>
 inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
 {
    if ((first == last) || (first == k) || (last == k))
       return false;
    Iterator itr1 = first;
    Iterator itr2 = last;
    ++itr1;
    if (last == itr1)
       return false;
    itr1 = last;
    --itr1;
    itr1 = k;
    --itr2;
    while (first != itr1)
    {
       if (*--itr1 < *itr2)
       {
          Iterator j = k;
          while (!(*itr1 < *j)) ++j;
          std::iter_swap(itr1,j);
          ++itr1;
          ++j;
          itr2 = k;
          std::rotate(itr1,j,last);
          while (last != j)
          {
             ++j;
             ++itr2;
          }
          std::rotate(k,itr2,last);
          return true;
       }
    }
    std::rotate(first,k,last);
    return false;
 }
于 2010-07-02T11:36:06.653 に答える
7

私は一つも知りません。基本的な考え方は、要素をビット配列として表すことです。たとえば、集合 S があります。

S = {a, b, c}
[i, j, k] // a is the first bit, b is the second bit, c is the third bit

S の Power Set を生成するには (単純な加算を使用して、サイズ == 3 ビットのすべての数値を生成するだけです):

000 // {}
001 // {c}
010 // {b}
011 // {b, c}
100 // {a}
101 // {a, c}
110 // {a, b}
111 // {a, b, c}

あなたがしなければならないことは、どのビットが設定されているかを見つけて、それらをセットの要素に関連付けることだけです。

最後に、すべての要素を使用したい場合に生成できる組み合わせが 1 つあります。その組み合わせはそれ自体のセットです。組み合わせでは順序は重要ではないため、要素の数 n について話していることは確かです。0 <= n <= size(S)

于 2010-04-21T19:46:50.440 に答える
1

これを行う必要があるときに、このライブラリを使用しました。と非常によく似たインターフェースを備えているstd::next_permutationため、以前に使用したことがある場合は簡単に使用できます。

于 2010-04-21T21:21:22.903 に答える
1

累乗セット (つまり、すべてのサイズのすべての組み合わせ) の列挙では、2 進インクリメント アルゴリズムの適応を使用できます。

template< class I, class O > // I forward, O bidirectional iterator
O next_subset( I uni_first, I uni_last, // set universe in a range
    O sub_first, O sub_last ) { // current subset in a range
    std::pair< O, I > mis = std::mismatch( sub_first, sub_last, uni_first );
    if ( mis.second == uni_last ) return sub_first; // finished cycle

    O ret;
    if ( mis.first == sub_first ) { // copy elements following mismatch
        std::copy_backward( mis.first, sub_last, ++ (ret = sub_last) ); 
    } else ret = std::copy( mis.first, sub_last, ++ O(sub_first) ); 
    * sub_first = * mis.second; // add first element not yet in result
    return ret; // return end of new subset. (Output range must accommodate.)
}

双方向反復子の要件は残念であり、回避することができます。

同一の要素 (マルチセット) を処理するようにするつもりでしたが、寝る必要があります :v( .

使用法：

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

char const *fruits_a[] = { "apples", "beans", "cherries", "durian" };
vector< string > fruits( fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a );

int main() {
    vector< string > sub_fruits( fruits.size() );
    vector< string >::iterator last_fruit = sub_fruits.begin();

    while ( 
        ( last_fruit = next_subset( fruits.begin(), fruits.end(),
                     sub_fruits.begin(), last_fruit ) )
            != sub_fruits.begin() ) {
        cerr << "size " << last_fruit - sub_fruits.begin() << ": ";
        for ( vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit ) {
            cerr << * fit << " ";
        }
        cerr << endl;
    }
}

編集:マルチセットのバージョンは次のとおりです。セットを並べ替える必要はありませんが、同一の要素をグループ化する必要があります。

#include <iterator>
#include <algorithm>
#include <functional>

template< class I, class O > // I forward, O bidirectional iterator
I next_subset( I uni_first, I uni_last, // set universe in a range
    O sub_first, O sub_last ) { // current subset in a range
    std::pair< O, I > mis = std::mismatch( sub_first, sub_last, uni_first );
    if ( mis.second == uni_last ) return sub_first; // finished cycle

    typedef std::reverse_iterator<O> RO;
    mis.first = std::find_if( RO(mis.first), RO(sub_first), std::bind1st(
        std::not_equal_to< typename std::iterator_traits<O>::value_type >(),
        * mis.second ) ).base(); // move mis.first before identical grouping

    O ret;
    if ( mis.first != sub_first ) { // copy elements after mismatch
        ret = std::copy( mis.first, sub_last, ++ O(sub_first) );
    } else std::copy_backward( mis.first, sub_last, ++ (ret = sub_last) );

    * sub_first = * mis.second; // add first element not yet in result
    return ret;
}

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

char const *fruits_a[] = { "apples", "apples", "beans", "beans", "cherries" };
vector< string > fruits( fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a );

int main() {
    vector< string > sub_fruits( fruits.size() );
    vector< string >::iterator last_fruit = sub_fruits.begin();

    while (
        ( last_fruit = next_subset( fruits.begin(), fruits.end(),
                                    sub_fruits.begin(), last_fruit )
        ) != sub_fruits.begin() ) {
        cerr << "size " << last_fruit - sub_fruits.begin() << ": ";
        for ( vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit ) {
            cerr << * fit << " ";
        }
        cerr << endl;
    }
}

出力：

size 1: apples 
size 2: apples apples 
size 1: beans 
size 2: apples beans 
size 3: apples apples beans 
size 2: beans beans 
size 3: apples beans beans 
size 4: apples apples beans beans 
size 1: cherries 
size 2: apples cherries 
size 3: apples apples cherries 
size 2: beans cherries 
size 3: apples beans cherries 
size 4: apples apples beans cherries 
size 3: beans beans cherries 
size 4: apples beans beans cherries 
size 5: apples apples beans beans cherries
于 2010-04-22T06:20:16.363 に答える
0

選択の余地がなく、独自の機能を実装する場合、この恐怖が少し役立つか、その質問に対する答えの中で他の恐怖が役立つ可能性があります。

n から k 個の要素のすべての組み合わせを返すアルゴリズム

少し前に書いたので、全体像はわかりません:)、しかし基本的な考え方は次のとおりです。元のセットがあり、現在の組み合わせは、選択された要素へのイテレータのベクトルです。次の組み合わせを取得するには、セットを右から左にスキャンして「バブル」を探します。「バブル」とは、選択されていない 1 つ以上の隣接する要素を意味します。「泡」はすぐ右側にあるかもしれません。次に、組み合わせで、「バブル」の左側にある最初の要素と、セットの右側にある組み合わせの他のすべての要素を、「バブル」の先頭から始まる隣接する要素のサブセットと交換します。バブル"。

于 2010-04-21T22:08:38.670 に答える
0

これC++ "next_combination"を見つけたグーグル。

  • *(end - 1) より小さい要素が見つかるまで、「mid」から逆方向に検索します。これは、インクリメントする必要がある要素です。これを「head_pos」と呼びます。
  • *head_pos よりもまだ大きい最後の要素が見つかるまで、「end」から逆方向に検索します。「tail_pos」と呼びます。
  • head_pos と tail_pos を入れ替えます。[head_pos + 1, mid[ および [tail_pos + 1, end[] の要素を昇順で並べ替えます。
于 2010-04-21T19:37:31.363 に答える