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

Question

std :: next_permutation (и std :: prev_permutation) переставляют все значения в диапазоне [first, last), заданные для общего числа n! перестановки (при условии, что все элементы уникальны).

возможно ли написать такую ​​функцию:

template<class Iter>
bool next_permutation(Iter first, Iter last, Iter choice_last);

Это переставляет элементы в диапазоне [first, last), но выбирает только элементы в диапазоне [first, choice_last). то есть у нас может быть 20 элементов, и мы хотим перебрать все перестановки из 10 вариантов из них, 20 вариантов P 10 против 20 P 20.

• Iter - это итератор произвольного доступа для моих целей, но если он может быть реализован как двунаправленный итератор, то отлично!
• Чем меньше объем внешней памяти, тем лучше, но для моих целей это не имеет значения.
• Выбранные элементы на каждой итерации вводятся в первые элементы последовательности.

Можно ли реализовать такую ​​функцию? Кто-нибудь знает какие-либо существующие реализации?

Вот по сути то, что я делаю, чтобы взломать это. Предложения о том, как это улучшить, также приветствуются.

• Начните с вектора V из N элементов, из которых я хочу посетить каждую перестановку из R элементов, выбранных из нее (R <= N).
• Построить вектор I длины R со значениями { 0, 1, 2, ... R - 1 }, который будет служить индексом для элементов V
• На каждой итерации строится вектор C длины R со значениями { V[I[0]], V[I[1]], ... V[I[R - 1]] }
• Сделайте что-нибудь со значениями в C.
• Примените функцию для перестановки элементов I и повторите итерацию, если это было возможно.

Эта функция выглядит так:

bool NextPermutationIndices(std::vector<int> &I, int N)
{
    const int R = I.size();
    for (int i = R - 1; ; --i) {
        if (I[i] < N - R + i) {
            ++I[i];
            return true;
        }

        if (i == 0)
            return false;

        if (I[i] > I[i-1] + 1) {
            ++I[i-1];
            for (int j = i; j < R; ++j)
                I[j] = I[j-1] + 1;
            return true;
        }
    }
}

Эта функция очень сложна из-за всех возможных ошибок, связанных с ошибкой, а также все, что ее использует, сложнее, чем, вероятно, необходимо.

---

EDIT:

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

template<class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first,
                              BidirectionalIterator middle,
                              BidirectionalIterator last)
{
    std::reverse(middle, last);
    return std::next_permutation(first, last);
}

Плюс там есть комбинированный алгоритм, который работает аналогичным образом. Однако реализация этого гораздо сложнее.

Answer 1

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

Answer 2

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

---

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

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

Answer 3

Для чего стоит, вот такая реализация.

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

Одним из преимуществ этого способа перед этого ответа является то, что этот способ не посещает перестановки в лексикографическом порядке, что может (но, вероятно, не важно) иметь значение. Также иногда бывает сложно использовать 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;
}

Answer 4

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

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

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

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