0

一連の番号を指定して、考えられるすべてのパスを見つける必要があるという小さな問題があります。たとえば、番号1、2、3があるとします。可能なすべての組み合わせを見つける必要があります。この単純なケースの結果は次のとおりです
。path_1 = 1path_2 = 2 path_3 = 3 path_4 = 1、2 path_5 = 1、3 path_6 = 2、3 path_7 = 1、2、3






パスの数が（2 ^ n）-1であることは簡単にわかります。したがって、3つの要素の場合は7になります。少数の要素に対してこれを手作業で行うのは非常に簡単ですが、数が大きくなるにつれて、それはますます難しくなります。

誰かがこの問題にブーストグラフライブラリを使用できると提案しましたが、十分な経験がないため、その方法がよくわかりません。どんな助けでも大歓迎です。

前もって感謝します

4

1 に答える 1

0 
template< class It >
void compute_all_possible_paths( path_collection_t& res, It b, It e ) {
    std::size_t curVecSize = res.size();
    for( std::size_t i = 0; i < curVecSize; i++ ) {
        path_t p;
        p.reserve( res[i].size() + 1 );
        std::copy( res[i].begin(), res[i].end(), std::back_inserter(p) );
        p.push_back( *b );
        res.push_back( p );
    }
    path_t p;
    p.push_back( *b );
    res.push_back( p );
    if( ++b == e ) return ;
    compute_all_possible_paths( res, b, e );
}
于 2012-10-18T22:53:12.027 に答える