Рубрики

Распечатать все перестановки в отсортированном (лексикографическом) порядке

Комбинаторика, Математика, Строки

Получив строку, выведите все ее перестановки в отсортированном порядке. Например, если входной строкой является «ABC», то вывод должен быть «ABC, ACB, BAC, BCA, CAB, CBA».

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

Ниже приведены шаги для печати перестановок лексикографического союзника.

1. Сортируйте данную строку в неубывающем порядке и распечатайте ее. Первая перестановка — это всегда строка, отсортированная в неубывающем порядке.

2. Начните генерировать следующую более высокую перестановку. Делать это до следующей более высокой перестановки невозможно. Если мы достигнем перестановки, в которой все символы отсортированы в порядке возрастания, то эта перестановка будет последней перестановкой.

Шаги для генерации следующей более высокой перестановки:
1. Возьмите ранее напечатанную перестановку и найдите в ней самый правый символ, который меньше, чем его следующий символ. Давайте назовем этот персонаж «первым персонажем».

2. Теперь найдите потолок «первого персонажа». Потолок — это самый маленький символ справа от «первого символа», который больше, чем «первый символ». Давайте назовем символ ceil «вторым персонажем».

3. Поменяйте местами два символа, найденные в 2 предыдущих шагах.

4. Сортируйте подстроку (в неубывающем порядке) после исходного индекса «первого символа».

Рассмотрим строку «ABCDEF». Пусть ранее напечатанная перестановка будет «DCFEBA». Следующая перестановка в отсортированном порядке должна быть «DEABCF». Давайте разберемся с вышеуказанными шагами, чтобы найти следующую перестановку. «Первый символ» будет «C». «Второй персонаж» будет «E». После обмена этими двумя мы получаем «DEFCBA». Последний шаг — сортировка подстроки после исходного индекса символа «первый символ». Наконец, мы получаем «DEABCF».
Ниже приведена реализация алгоритма.

C ++

// C ++ Программа для печати всех перестановок
// строки в отсортированном порядке.
#include <bits/stdc++.h>

using namespace std;

  
/ * Следующая функция необходима для библиотечной функции qsort (). обращаться
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

int compare (const void *a, const void * b) 

{ return ( *(char *)a - *(char *)b ); } 

  
// Вспомогательная функция два поменяет местами два символа a и b

void swap (char* a, char* b) 

{ 

    char t = *a; 

    *a = *b; 

    *b = t; 

} 

  
// Эта функция находит индекс наименьшего символа
// который больше 'first' и присутствует в str [l..h]

int findCeil (char str[], char first, int l, int h) 

{ 

    // инициализируем индекс элемента потолка

    int ceilIndex = l; 

  

    // Теперь перебираем остальные элементы и находим

    // наименьший символ больше первого

    for (int i = l+1; i <= h; i++) 

    if (str[i] > first && str[i] < str[ceilIndex]) 

            ceilIndex = i; 

  

    return ceilIndex; 

} 

  
// Распечатать все перестановки str в отсортированном порядке

void sortedPermutations ( char str[] ) 

{ 

    // Получить размер строки

    int size = strlen(str); 

  

    // Сортировка строки в порядке возрастания

    qsort( str, size, sizeof( str[0] ), compare ); 

  

    // Печать перестановок одна за другой

    bool isFinished = false; 

    while ( ! isFinished ) 

    { 

        // распечатать эту перестановку

        cout << str << endl; 

  

        // Находим самый правый символ, который

        // меньше, чем его следующий символ.

        // Давайте назовем это 'first char'

        int i; 

        for ( i = size - 2; i >= 0; --i ) 

        if (str[i] < str[i+1]) 

            break; 

  

        // Если такого символа нет, все

        // отсортировано по убыванию, значит мы

        // только что напечатали последнюю перестановку и все готово.

        if ( i == -1 ) 

            isFinished = true; 

        else

        { 

            // Находим ячейку первого символа в

            // справа от первого символа.

            // Ceil персонажа самый маленький

            // символ больше его

            int ceilIndex = findCeil( str, str[i], i + 1, size - 1 ); 

  

            // Поменять местами первый и второй символы

            swap( &str[i], &str[ceilIndex] ); 

  

            // Сортировка строки справа от 'first char'

            qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare ); 

        } 

    } 

} 

  
// Программа драйвера для проверки вышеуказанной функции

int main() 

{ 

    char str[] = "ABCD"; 

    sortedPermutations( str ); 

    return 0; 

} 

  
// Это код, предоставленный rathbhupendra

С

// Программа для печати всех перестановок строки в отсортированном порядке.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

  
/ * Следующая функция необходима для библиотечной функции qsort (). обращаться

   http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

int compare (const void *a, const void * b)

{  return ( *(char *)a - *(char *)b ); }

  
// Вспомогательная функция два поменяет местами два символа a и b

void swap (char* a, char* b)

{

    char t = *a;

    *a = *b;

    *b = t;

}

  
// Эта функция находит индекс наименьшего символа
// который больше 'first' и присутствует в str [l..h]

int findCeil (char str[], char first, int l, int h)

{

    // инициализируем индекс элемента потолка

    int ceilIndex = l;

  

    // Теперь перебираем остальные элементы и находим

    // наименьший символ больше первого

    for (int i = l+1; i <= h; i++)

      if (str[i] > first && str[i] < str[ceilIndex])

            ceilIndex = i;

  

    return ceilIndex;

}

  
// Распечатать все перестановки str в отсортированном порядке

void sortedPermutations ( char str[] )

{

    // Получить размер строки

    int size = strlen(str);

  

    // Сортировка строки в порядке возрастания

    qsort( str, size, sizeof( str[0] ), compare );

  

    // Печать перестановок одна за другой

    bool isFinished = false;

    while ( ! isFinished )

    {

        // распечатать эту перестановку

        printf ("%s \n", str);

  

        // Находим самый правый символ, который меньше его следующего

        // персонаж. Давайте назовем это «первый символ»

        int i;

        for ( i = size - 2; i >= 0; --i )

           if (str[i] < str[i+1])

              break;

  

        // Если такого символа нет, все отсортированы в порядке убывания,

        // означает, что мы только что напечатали последнюю перестановку и все готово.

        if ( i == -1 )

            isFinished = true;

        else

        {

            // Находим ячейку 'first char' справа от первого символа.

            // Ceil символа - самый маленький символ, больше чем это

            int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );

  

            // Поменять местами первый и второй символы

            swap( &str[i], &str[ceilIndex] );

  

            // Сортировка строки справа от 'first char'

            qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );

        }

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char str[] = "ABCD";

    sortedPermutations( str );

    return 0;

}


Выход:

ABCD
ABDC
....
....
DCAB
DCBA

Верхняя граница сложности времени вышеупомянутой программы O (n ^ 2 xn!). Мы можем оптимизировать шаг 4 вышеупомянутого алгоритма для нахождения следующей перестановки. Вместо сортировки подмассива после «первого символа» мы можем перевернуть подмассив, потому что подмассив, который мы получаем после замены, всегда сортируется в порядке возрастания. Эта оптимизация усложняет время как O (nxn!). Смотрите следующий оптимизированный код.

C ++

#include <bits/stdc++.h>

using namespace std; 

  
// Оптимизированная версия, которая использует реверс вместо сортировки для
// найти следующую перестановку

  
// Вспомогательная функция для обращения строки str [l..h]

void reverse(char str[], int l, int h) 

{ 

    while (l < h) 

    { 

        swap(&str[l], &str[h]); 

        l++; 

        h--; 

    } 

} 

  
// Распечатать все перестановки str в отсортированном порядке

void sortedPermutations ( char str[] ) 

{ 

    // Получить размер строки

    int size = strlen(str); 

  

    // Сортировка строки в порядке возрастания

    qsort( str, size, sizeof( str[0] ), compare ); 

  

    // Печать перестановок одна за другой

    bool isFinished = false; 

    while ( ! isFinished ) 

    { 

        // распечатать эту перестановку

        cout << str << endl; 

  

        // Находим самый правый символ, который

        // меньше, чем его следующий символ.

        // Давайте назовем это 'first char'

        int i; 

        for ( i = size - 2; i >= 0; --i ) 

        if (str[i] < str[i+1]) 

            break; 

  

        // Если такого символа нет, все

        // отсортированы в порядке убывания,

        // означает, что мы только что напечатали последний

        // перестановка и все готово.

        if ( i == -1 ) 

            isFinished = true; 

        else

        { 

            // Находим ячейку первого символа в

            // справа от первого символа.

            // Ceil персонажа является

            // наименьший символ больше его

            int ceilIndex = findCeil( str, str[i], i + 1, size - 1 ); 

  

            // Поменять местами первый и второй символы

            swap( &str[i], &str[ceilIndex] ); 

  

            // перевернуть строку справа от 'first char'

            reverse( str, i + 1, size - 1 ); 

        } 

    } 

} 

  
// Этот код предоставлен rathbhupendra

С

// Оптимизированная версия, которая использует реверс вместо сортировки для
// найти следующую перестановку

  
// Вспомогательная функция для обращения строки str [l..h]

void reverse(char str[], int l, int h)

{

   while (l < h)

   {

       swap(&str[l], &str[h]);

       l++;

       h--;

   }

}

  
// Распечатать все перестановки str в отсортированном порядке

void sortedPermutations ( char str[] )

{

    // Получить размер строки

    int size = strlen(str);

  

    // Сортировка строки в порядке возрастания

    qsort( str, size, sizeof( str[0] ), compare );

  

    // Печать перестановок одна за другой

    bool isFinished = false;

    while ( ! isFinished )

    {

        // распечатать эту перестановку

        printf ("%s \n", str);

  

        // Находим самый правый символ, который меньше его следующего

        // персонаж. Давайте назовем это «первый символ»

        int i;

        for ( i = size - 2; i >= 0; --i )

           if (str[i] < str[i+1])

              break;

  

        // Если такого символа нет, все отсортированы в порядке убывания,

        // означает, что мы только что напечатали последнюю перестановку и все готово.

        if ( i == -1 )

            isFinished = true;

        else

        {

            // Находим ячейку 'first char' справа от первого символа.

            // Ceil символа - самый маленький символ, больше чем это

            int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );

  

            // Поменять местами первый и второй символы

            swap( &str[i], &str[ceilIndex] );

  

            // перевернуть строку справа от 'first char'

            reverse( str, i + 1, size - 1 );

        }

    }

}

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

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

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

Распечатать все перестановки в отсортированном (лексикографическом) порядке

0.00 (0%) 0 votes