Рубрики

Перестановки заданной строки с использованием STL

Перестановка, также называемая «номером компоновки» или «порядком», представляет собой перестановку элементов упорядоченного списка S в соответствие «один к одному» с самим S. Строка длиной n имеет n! перестановка.
Источник: Mathword

Ниже приведены перестановки строки ABC.
ABC ACB BAC BCA CBA CAB
Мы обсудили реализацию C, чтобы напечатать все перестановки данной строки, используя возвратный путь здесь . В этом посте обсуждается реализация C ++ с использованием STL.

Метод 1 (Использование rotate ())

Функция std :: rotate вращает элементы вектора / строки так, что переданный средний элемент становится первым. Например, если мы вызываем rotate для «ABCD» со средним значением в качестве второго элемента, строка становится «BCDA», а если мы снова вызываем rotate со средним значением в качестве второго элемента, строка становится «CDAB». Обратитесь к этому для примера программы.

Ниже приведена реализация C ++.

// C ++ программа для печати всех перестановок с
// дубликаты разрешены с использованием rotate () в STL
#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати перестановок строки str,
// out используется для хранения перестановок одна за другой

void permute(string str, string out)

{

    // Когда размер str становится 0, out имеет

    // перестановка (длина out равна n)

    if (str.size() == 0)

    {

        cout << out << endl;

        return;

    }

  

    // Один за другим переместить все символы в

    // начало out (или результат)

    for (int i = 0; i < str.size(); i++)

    {

        // Удалить первый символ из str и

        // добавить его в out

        permute(str.substr(1), out + str[0]);

  

        // Поворот строки вторым символом

        // движется в начало.

        rotate(str.begin(), str.begin() + 1, str.end());

    }

}

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

int main()

{

    string str = "ABC";

    permute(str, "");

    return 0;

}

Выход :

ABC
ACB
BCA
BAC
CAB
CBA

Способ 2 (с использованием next_permute ())

Мы можем использовать next_permute (), который изменяет строку так, чтобы она сохраняла лексикографически следующую перестановку. Если текущая строка является лексикографически наибольшей, то есть «CBA», тогда next_permute () возвращает false.

Сначала мы сортируем строку так, чтобы она была преобразована в лексикографически наименьшую перестановку. Затем мы по очереди вызываем next_permutation, пока он не вернет false.

// C ++ программа для печати всех перестановок с
// дубликаты разрешены с использованием next_permute ()
#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати перестановок строки str
// используя next_permute ()

void permute(string str)

{

    // Сортировка строки в лексикографическом

    // возрастающий порядок

    sort(str.begin(), str.end());

  

    // Продолжаем печатать следующую перестановку, пока

    // следующая перестановка

    do {

       cout << str << endl;

    } while (next_permutation(str.begin(), str.end()));

}

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

int main()

{

    string str = "CBA";

    permute(str);

    return 0;

}

Выход :

ABC
ACB
BCA
BAC
CAB
CBA

Обратите внимание, что второй метод всегда печатает перестановки в лексикографически отсортированном порядке независимо от входной строки.

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

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

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

Перестановки заданной строки с использованием STL

0.00 (0%) 0 votes