Как обновить ранги для некоторого подмножества?

У меня есть входные данные, состоящие из рангов в каком-то соревновании (скажем, марафоне) со значениями в диапазоне [0, N). Существует несколько подконкурсов (например, основанных на возрасте, поле и т. д.), которые интересны только для подмножества team и не подходят для другого подмножества not_eligible.

Я ищу эффективный алгоритм (желательно написанный в терминах стандартной библиотеки), который будет обновлять ранги. Пример:

auto team = std::vector<int>{ 1, 2, 9, 13 };
auto not_eligible = std::vector<int>{ 8, 10, 12 };
std::vector<int> result;

// some algorithm

assert(result == std::vector<int>{ 1, 2, 8, 10 });

Поскольку только 1 участник ниже № 9 (т.е. № 8) не имел права, рейтинг № 9 уменьшается на 1, а также потому, что до № 13 было 3 не соответствующих требованиям финишера (т. е. № 8, № 10 и № 12). , этот рейтинг обновляется на 3 с № 13 до № 10 для этого конкретного подконкурса.

Примечание 8 и 10 являются частью result, но не потому, что они были объединены из non_eligible, а потому, что их ранги были взяты 9 и 13 из team.

Как я могу добиться вышеперечисленного, используя комбинацию стандартных алгоритмов? Я надеялся, что смогу сделать это со сложностью O(N + M) для входных диапазонов длины N и M (например, через 5-ногий std::transform).

ОБНОВЛЕНИЕ: меня также интересует обратный алгоритм: учитывая рейтинг подконкурса, как обновить рейтинги претендентов в подконкурсе при добавлении ранее не подходящих участников?


c++ algorithm ranking c++11 stl
person TemplateRex    schedule 07.02.2014    source источник
comment
@close избиратель: пожалуйста, задавайте уточняющие вопросы, чтобы я мог уточнить. Я думаю, что вопрос достаточно хорошо сформулирован!   -  person TemplateRex    schedule 07.02.2014
comment
Обратите внимание, что ваш пример немного вводит в заблуждение, так как часть результата 8, 10 находится внутри not_eligible. Вы можете изменить not_eligible на что-то вроде {5, 11, 12}.   -  person Jarod42    schedule 07.02.2014
comment
@Jarod42 tnx, не заметил, но вообще это часть алгоритма. Обновлено с примечанием, спасибо!   -  person TemplateRex    schedule 07.02.2014

Ответы (2)


arrow_upward
1
arrow_downward

На самом деле нет очевидного способа использовать существующие algorithm; вам лучше взять пример кода для merge и адаптировать его:

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt update_ranks(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    typename std::iterator_traits<InputIt1>::value_type adjust = {};
    while (first1 != last1) {
        if (first2 != last2 && *first2 < *first1) {
            ++adjust;
            ++first2;
        } else {
            *d_first = *first1 - adjust;
            ++first1;
            ++d_first;
        }
    }
    return d_first;
}

Для обратного снова должна работать адаптация merge.

person ecatmur    schedule 07.02.2014
comment
часть adjust={} у меня не компилируется: coliru.stacked-crooked.com/a/026228549fc3bc65 - person TemplateRex; 07.02.2014
comment
@TemplateRex да, decltype не всегда делает то, что вы хотите. Изменено для использования iterator_traits. - person ecatmur; 07.02.2014
comment
tnx, +1, потому что это работает, но теперь я вдохновился адаптировать его к одному вызову std::transform :-) - person TemplateRex; 07.02.2014

arrow_upward
1
arrow_downward

Мне удалось найти простую обертку вокруг трехногой версии std::transform, как для исходной, так и для обратной задачи (оба алгоритма O(N + M) во входных последовательностях)

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt remove_ranks(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    auto delta = 0;
    return std::transform(first1, last1, d_first, 
        [&, first2](int rank) mutable {
        while (first2 != last2 && rank > *first2) { ++first2; ++delta; }
        return rank - delta;
    });
}

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt insert_ranks(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    auto delta = 0;
    return std::transform(first1, last1, d_first, 
        [&, first2](int rank) mutable {
        while (first2 != last2 && rank + delta >= *first2) { ++first2; ++delta; }
        return rank + delta;
    });
}

Живой пример

person TemplateRex    schedule 07.02.2014