n要素からk要素のすべての組み合わせと順列を与えるためにC++で最も広く使用されている既存のライブラリは何ですか?
アルゴリズムではなく、既存のライブラリまたはメソッドを求めています。
ありがとう。
質問する
24803 次
5 に答える
39
ここで、dman と Charles Bailey によるソリューションをテストすることにしました。それらをそれぞれソリューション A および B と呼びます。私のテストでは、vector<int>サイズ = 100、一度に 5 の各組み合わせにアクセスしています。テストコードは次のとおりです。
テストコード
struct F
{
unsigned long long count_;
F() : count_(0) {}
bool operator()(std::vector<int>::iterator, std::vector<int>::iterator)
{++count_; return false;}
};
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double> sec;
typedef std::chrono::duration<double, std::nano> ns;
int n = 100;
std::vector<int> v(n);
std::iota(v.begin(), v.end(), 0);
std::vector<int>::iterator r = v.begin() + 5;
F f;
Clock::time_point t0 = Clock::now();
do
{
f(v.begin(), r);
} while (next_combination(v.begin(), r, v.end()));
Clock::time_point t1 = Clock::now();
sec s0 = t1 - t0;
ns pvt0 = s0 / f.count_;
std::cout << "N = " << v.size() << ", r = " << r-v.begin()
<< ", visits = " << f.count_ << '\n'
<< "\tnext_combination total = " << s0.count() << " seconds\n"
<< "\tnext_combination per visit = " << pvt0.count() << " ns";
}
すべてのコードは、2.8 GHz Intel Core i5 で clang++ -O3 を使用してコンパイルされました。
ソリューション A
解決策 A は無限ループになります。私がn非常に小さくしても、このプログラムは決して完成しません。その後、この理由で反対票を投じました。
ソリューション B
これは編集です。ソリューション B は、この回答を書いている途中で変更されました。最初は間違った答えを出していましたが、非常に迅速な更新により、正しい答えが得られるようになりました。次のように出力されます。
N = 100, r = 5, visits = 75287520
next_combination total = 4519.84 seconds
next_combination per visit = 60034.3 ns
ソリューション C
次に、ソリューション A に非常に似ているN2639のソリューションを試しましたが、正しく機能します。このソリューションを C と呼び、次のように出力します。
N = 100, r = 5, visits = 75287520
next_combination total = 6.42602 seconds
next_combination per visit = 85.3531 ns
ソリューション C は、ソリューション B よりも 703 倍高速です。
ソリューション D
最後に、ここで見つかったソリューション D があります。このソリューションは、異なる署名/スタイルを持ち、 と呼ばれfor_each_combination、 と同じように使用されますstd::for_each。上記のドライバー コードは、タイマー呼び出し間で次のように変更されます。
Clock::time_point t0 = Clock::now();
f = for_each_combination(v.begin(), r, v.end(), f);
Clock::time_point t1 = Clock::now();
ソリューション D の出力:
N = 100, r = 5, visits = 75287520
for_each_combination = 0.498979 seconds
for_each_combination per visit = 6.62765 ns
ソリューション D は、ソリューション C よりも 12.9 倍速く、ソリューション B よりも 9000 倍以上高速です。
私はこれを比較的小さな問題だと考えています.7,500 万回の訪問しかありません. 訪問数が数十億に増加するにつれて、これらのアルゴリズム間のパフォーマンスの不一致は拡大し続けています。ソリューション B はすでに扱いにくいです。ソリューション C は最終的に扱いにくくなります。ソリューション D は、私が認識しているすべての組み合わせにアクセスするための最もパフォーマンスの高いアルゴリズムです。
ソリューション D を示すリンクには、さまざまなプロパティ (循環、可逆など) を持つ順列を列挙してアクセスするための他のアルゴリズムもいくつか含まれています。これらの各アルゴリズムは、パフォーマンスを目標の 1 つとして設計されました。また、これらのアルゴリズムのいずれも、最初のシーケンスがソートされている必要がないことに注意してください。要素は である必要さえありませんLessThanComparable。
于 2011-03-13T00:08:38.577 に答える
20
組み合わせ:同じトピックに関するMark Nelson の記事next_combinationから 順列: 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-02-06T04:30:23.490 に答える
17
この回答は、最小限の実装作業ソリューションを提供します。大きな入力範囲の組み合わせを取得する場合、許容できるパフォーマンスが得られない可能性があります。
標準ライブラリにはa があり、そこから a とそれからstd::next_permutationa を自明に構築できます。next_k_permutationnext_combination
template<class RandIt, class Compare>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last, Compare comp)
{
std::sort(mid, last, std::tr1::bind(comp, std::tr1::placeholders::_2
, std::tr1::placeholders::_1));
return std::next_permutation(first, last, comp);
}
引数を特定の比較にスワップする関数オブジェクトを持っていないtr1::bindかboost::bind、構築する必要がある場合。もちろん、 のstd::lessバリアントのみに関心がある場合は、次を直接next_combination使用できます。std::greater
template<class RandIt>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits<RandIt>::value_type value_type;
std::sort(mid, last, std::greater< value_type >());
return std::next_permutation(first, last);
}
これは の比較的安全なバージョンですnext_combination。[mid, last)を呼び出した後のように、範囲が適切であることを保証next_combinationできる場合は、より単純なものを使用できます。
template<class BiDiIt, class Compare>
bool next_k_permutation(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
std::reverse(mid, last);
return std::next_permutation(first, last, comp);
}
これは、ランダム アクセス イテレータだけでなく、双方向イテレータでも機能します。
k-順列の代わりに組み合わせを出力するには、各組み合わせを 1 回だけ出力する必要があるため、順番に k-順列である場合にのみ組み合わせを返します。
template<class BiDiIt, class Compare>
bool next_combination(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
bool result;
do
{
result = next_k_permutation(first, mid, last, comp);
} while (std::adjacent_find( first, mid,
std::tr1::bind(comp, std::tr1::placeholders::_2
, std::tr1::placeholders::_1) )
!= mid );
return result;
}
bind代替手段は、パラメーター交換呼び出しの代わりに逆反復子を使用するか、比較が使用されているstd::greater場合は明示的に使用することです。std::less
于 2010-04-11T11:25:32.867 に答える
2
上記の@チャールズベイリー：
私は間違っているかもしれませんが、上記の最初の 2 つのアルゴリズムは最初と中間の間の重複を削除しないと思いますか? 使い方がわからないのかもしれません。
4 choose 2 例:
12 34
12 43 (ソート後)
13 24 (next_permutation 後)
13 42 (ソート後)
14 23 (next_permutation 後)
14 32 (ソート後)
21 34 (next_permutation 後)
そのため、返す前にイタリック体の値が正しいかどうかを確認するチェックを追加しましたが、あなたが書いた部分についてはまったく考えていなかったでしょう (非常にエレガントです! ありがとう!)。
完全にはテストされていません。大雑把なテストです..
template
bool next_combination(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits< RandIt >::value_type value_type;
std::sort(mid, last, std::greater< value_type >() );
while(std::next_permutation(first, last)){
if(std::adjacent_find(first, mid, std::greater< value_type >() ) == mid){
return true;
}
std::sort(mid, last, std::greater< value_type >() );
return false;
}
于 2011-01-06T01:58:55.347 に答える