Блог

Главная - Вопросы по программированию - Реализуйте следующую комбинацию — C_n_k на C с использованием вектора

Реализуйте следующую комбинацию — C_n_k на C с использованием вектора

#c #combinatorics

Вопрос:

Я застрял — не могу реализовать идеальный алгоритм для следующей комбинации для лексикографического порядка. Не могли бы вы, пожалуйста, сказать мне, где я ошибаюсь? Например, например, вектор a = {1,2,0,3,0,1,2,4}; nextPermutation(a); имеет переполнение кучи при доступе к элементу массива std::next. Как можно было бы улучшить этот код?

    void nextPermutation(vector<int>amp; perm) {
        auto temp1 = perm[0], temp2 = perm[0];
        int idx1 = -1, idx2 = -1;
        if (perm.size() == 1)
            return;
        if (perm.size() == 2)
        {
            reverse(perm.begin(), perm.end());
            return;
        }
        for (auto amp;v : perm)
        {
            if (amp;v - amp;perm[0] == perm.size())
                break;
            if (v < *(amp;v   1))
            {
                temp1 = v;
                idx1 = amp;v  - amp;perm[0];
                //cout << idx1 << endl;
            }
        }
        if (idx1 == -1)
        {
            reverse(perm.begin(), perm.end());
            return;
        }
        for (auto v = perm.begin(); v < perm.end(); v  )
        {
            if (*v > *next(perm.begin(), idx1))
            {
                temp2 = *v;
                idx2 = std::distance(perm.begin(), v);
                //cout << idx2 << endl;
            }
        }
        int temp = perm[idx1];
        perm[idx1] = perm[idx2];
        perm[idx2] = temp;
        reverse(perm.begin()   idx1   1, perm.end());
    }

Комментарии:

1. Не удается воспроизвести (может быть, покажите нам код, который вызывает вашу функцию?) Однако я думаю, что вам следует изменить свой первый for цикл (для определения idx1 ) на ту же форму, что и второй ( idx2 ) цикл, используя 1 в качестве 2-го аргумента to std::next . Работает на меня и выглядит намного безопаснее.

2. @AdrianMole ideone.com/DIpu11 Да, первый цикл в идеале должен найти последний x: пермь[x] Я неправильно использую amp;v — amp;perm[0] == perm.size() — я пытаюсь определить, достиг ли цикл последнего элемента, чтобы следующий, если не будет запущен; Я думаю, что есть простой способ проверить это.

3. for (auto v = perm.begin(); v < perm.end() - 1; v ) выполняется до предпоследнего элемента.

Метки: