mercredi 17 octobre 2018

range v3 knapsack-like combinations generator fails to compile

Trying to solve knapsack-like problem using range-v3. Wrote a combinations generator but it fails to compile.

#include <vector>
#include <range/v3/all.hpp>

ranges::any_view<ranges::any_view<int>>
generate_combinations(
    ranges::any_view<int, ranges::category::random_access> containers,
    const int total_volume )
{
    if( containers.empty() || total_volume <= 0 )
    {
        return ranges::view::single( ranges::view::empty<int>() );
    }

    auto head = containers.front();
    auto tail = ranges::view::tail( containers );

    auto result1 = generate_combinations( tail, total_volume - head )
        | ranges::view::transform( [head]( auto rng ) {
                return ranges::view::concat( ranges::view::single( head ), rng ); })
        | ranges::view::filter( [total_volume]( auto rng ) {
                return ranges::accumulate( rng, 0 ) == total_volume; });

    auto result2 = generate_combinations( tail, total_volume );

    auto result = ranges::view::concat( result1, result2 );

    return result;
}

int main() {
    std::vector<int> containers { 20, 15, 10, 5, 5 };
    return generate_combinations( containers, 25 );
}

It fails with some pretty big error message. And as far as I see the essence of it is:

error: no type named ‘type’ in ‘struct ranges::v3::common_reference<ranges::v3::concat_view<ranges::v3::single_view<int>, ranges::v3::any_view<int, (ranges::v3::category)1, void> >, ranges::v3::any_view<int, (ranges::v3::category)1, void> >’
     using _t = typename T::type;

Looks like there is some problem with concating result1 and result2. How could this problem be fixed? And what is most idiomatic way to write this kind of algorithm using range-v3?

Aucun commentaire:

Enregistrer un commentaire