Рубрики

Лексикографически следующая перестановка в C ++

По заданному слову найдите лексикографически большую его перестановку. Например, лексикографически следующая перестановка «gfg» — это «ggf», а следующая перестановка «acb» — «bac».

Примечание: в некоторых случаях следующего лексикографически большего слова может не существовать, например, «aaa» и «edcba»

В C ++ есть специальная функция, которая спасает нас от большого количества кода. Это в файле #include <алгоритм>. Функция является следующей_перестановкой (a.begin (), a.end ()). Он возвращает 'true', если функция может переставить объект в виде лексикографически большей перестановки. В противном случае функция возвращает значение «ложь».

Давайте посмотрим на фрагмент кода здесь:

// Находим следующую лексикографически
// большая перестановка слова

  
#include <algorithm>
#include <iostream>

  

using namespace std;

  

int main()

{

    string s = { "gfg" };

    bool val

        = next_permutation(s.begin(),

                           s.end());

    if (val == false)

        cout << "No Word Possible"

             << endl;

    else

        cout << s << endl;

    return 0;

}

Выход:

ggf

Эта же программа может быть реализована без использования STL . Ниже приведен фрагмент кода для того же. Идея основана на следующих фактах:
1) Последовательность, отсортированная в порядке убывания, не имеет следующей перестановки. Например, edcba ”не имеет следующей перестановки.
2) Для последовательности, которая не отсортирована в порядке убывания, например, «abedc», мы можем выполнить следующие шаги.
……… .a) Пройдите справа и найдите первый пункт, который не следует по убыванию. Например, в «abedc» символ «b» не следует в порядке убывания.
……… .b) Поменяйте местами найденный персонаж с ближайшим большим (или наименьшим большим) элементом справа от него. В случае «abedc» мы имеем «c» в качестве ближайшего большего элемента. После замены «b» и «c» строка становится «acedb».
……… .c) После замены отсортируйте строку после позиции символа, найденной на шаге a . После сортировки подстроки «edb» в «acedb» мы получаем « acbed », который является необходимой следующей перестановкой.

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

// Находим следующую лексикографически
// большая перестановка слова

  
#include <iostream>

  

using namespace std;

  

void swap(char* a, char* b)

{

    if (*a == *b)

        return;

    *a ^= *b;

    *b ^= *a;

    *a ^= *b;

}

void rev(string& s, int l, int r)

{

    while (l < r)

        swap(&s[l++], &s[r--]);

}

  

int bsearch(string& s, int l, int r, int key)

{

    int index = -1;

    while (l <= r) {

        int mid = l + (r - l) / 2;

        if (s[mid] <= key)

            r = mid - 1;

        else {

            l = mid + 1;

            if (index == -1 || s[index] >= s[mid])

                index = mid;

        }

    }

    return index;

}

  

bool nextpermutation(string& s)

{

    int len = s.length(), i = len - 2;

    while (i >= 0 && s[i] >= s[i + 1])

        --i;

    if (i < 0)

        return false;

    else {

        int index = bsearch(s, i + 1, len - 1, s[i]);

        swap(&s[i], &s[index]);

        rev(s, i + 1, len - 1);

        return true;

    }

}

  
// Код драйвера

int main()

{

    string s = { "gfg" };

    bool val = nextpermutation(s);

    if (val == false)

        cout << "No Word Possible" << endl;

    else

        cout << s << endl;

    return 0;

}
// Этот код предоставлен Mysterious Mind

Выход:

ggf

Сложность времени:

  1. В худшем случае первый шаг next_permutation занимает O (n) времени.
  2. Двоичный поиск занимает O (logn) время.
  3. Обратное время занимает O (n).

Общая сложность по времени составляет O (n).
Где n — длина строки.

Ссылка: http://www.cplusplus.com/reference/algorithm/next_permutation/

Эта статья предоставлена Харшитом Гуптой . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Лексикографически следующая перестановка в C ++

0.00 (0%) 0 votes