Можно ли написать функцию, подобную next_permutation, но которая переставляет только r значений вместо n?

Для перебора перестановок nPk я использовал алгоритм for_each_permutation(), представленный в этой старой статье CUJ. . Он использует хороший алгоритм Кнута, который вращает элементы на месте, оставляя их в исходном порядке в конце. Таким образом, он соответствует вашим требованиям к внешней памяти. Это также работает для двунаправленных итераторов. Это не соответствует вашему требованию выглядеть как next_permutation(). Однако я думаю, что это победа — мне не нравятся API с отслеживанием состояния.

Исходный код генератора комбинаций Java находится по адресу http://www.merriampark.com/comb.htm. Удалите идиомы Java, и это почти то, что вы ищете, реализованное в виде генератора, чтобы контролировать использование вашей памяти.

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

(Примечание: этот вопрос связан с "алгоритмом группировки", но не совсем повторяется, поскольку этот вопрос просит решить ее в общем случае.)

Алгоритмическое упрощение состояло бы в том, чтобы разделить это на два отдельных шага.

• Создайте список всех возможных вариантов выбора элементов R из исходных данных.
• Для каждого из этих вариантов создайте все возможные перестановки выбранных элементов.

Чередуя эти операции, вы можете избежать выделения промежуточных списков.

Выбор можно реализовать на двунаправленном итераторе, пропуская невыбранные элементы. Сгенерируйте все выборки, например. путем перестановки последовательности из R единиц и (N-R) нулей. Это потребует O(N) дополнительной памяти, но позволит вам переставить исходную последовательность на месте.

Что бы это ни стоило, вот реализация, которая работает.

Это требует, чтобы элементы выше выбора начинались в отсортированном порядке. Он работает только в том случае, если в последовательности нет повторяющихся элементов (если они есть, он пропускает некоторые перестановки и не заканчивается правильной перестановкой). Также могут отсутствовать некоторые пограничные случаи, поскольку я не проверял его тщательно, поскольку у меня нет планов его фактического использования.

Одно из преимуществ этого способа над этот ответ заключается в том, что таким образом не используются перестановки в лексикографическом порядке, что может (но, вероятно, не) быть важным. Также неудобно иногда использовать boost::bind для создания функтора для передачи for_each.

template<class Iter>
bool next_choice_permutation(Iter first, Iter choice, Iter last)
{
    if (first == choice)
        return false;

    Iter i = choice;
    --i;
    if (*i < *choice) {
        std::rotate(i, choice, last);
        return true;
    }

    while (i != first) {
        Iter j = i;
        ++j;
        std::rotate(i, j, last);
        --i;
        --j;
        for (; j != last; ++j) {
            if (*i < *j)
                break;
        }
        if (j != last) {
            std::iter_swap(i, j);
            return true;
        }
    }
    std::rotate(first, ++Iter(first), last);
    return false;
}