Все возможные пути в серии чисел
У меня есть небольшая проблема, где мне нужно найти все возможные пути, используя набор чисел. Например, допустим, у нас есть номера 1, 2 и 3. Мне нужно найти все возможные комбинации. Результат для этого простого случая:
path_1 знак равно 1
path_2 знак равно 2
path_3 знак равно 3
path_4 знак равно 1, 2
path_5 знак равно 1, 3
path_6 знак равно 2, 3
path_7 знак равно 1, 2, 3
Легко видеть, что число путей (2 ^ п) -1, так для 3 элементов, это 7 и так далее. Это довольно просто сделать вручную для небольшого числа элементов, но по мере того, как числа становятся большими, становится все сложнее и сложнее.
Кто-то предположил, что я могу использовать библиотеку надстрочных графов для этой проблемы, но я не совсем уверен, как это сделать, потому что у меня недостаточно опыта с этим. Любая помощь приветствуется.
заранее спасибо
Решение
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 );
}
Другие решения
Других решений пока нет …