lundi 24 septembre 2018

partitioning a range of sorted elements into adjacent groups

I have a sorted list of items below. I need to determine how to pick item pairs from this list such that the difference between them exceeds some fixed value (for example 5 in the example below). This should therefore result in partitioning the list into adjacent ranges (no element left out).

I figured out a brute force way of doing this (see live COLIRU demo) as follows but I am sure there must be a more elegant solution - for example using std::adjacent_find or some range based search in a loop or some sort - but I cannot figure it out.

The live demo shows that the list of values { 100, 104, 108, 112, 116, 120 } results in adjacent ranges

{100,108}
{108,116}
{116,120}

The code to do this is as follows:

int main()
{
    std::vector<int> elements = { 100, 104, 108, 112,  116, 120 };
    std::vector<std::pair<int, int>> result;
    auto current = elements.begin();
    while (current != std::prev(elements.cend())) {
        auto next = std::next(current);
        while ((*next - *current < 5) &&
            (next != std::prev(elements.cend()))) {
            ++next;
        }
        result.emplace_back(*current, *next);
        current = next;
    }
    std::transform( result.cbegin(), result.cend(), std::ostream_iterator<std::string>(std::cout, "\n"), 
        [](const auto& next){ return std::string("{") + std::to_string(next.first) + ',' +  std::to_string(next.second) + '}'; } );  
}

Aucun commentaire:

Enregistrer un commentaire