Печать всей перестановки в лексикографическом порядке

Ответ 1

В C

Там довольно простое описание алгоритма (плюс реализация) в geeksforgeeks:

С учетом строки напечатайте все перестановки в отсортированном порядке. Для Например, если строка ввода - "ABC", тогда вывод должен быть "ABC, ACB, BAC, BCA, CAB, CBA".

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

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

• Отсортируйте заданную строку в неубывающем порядке и распечатайте ее. Первой перестановкой всегда является строка, отсортированная в неубывающем порядке.

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

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

2. Теперь найдите потолок" первого символа ". Потолок - это наименьший символ справа от" первого символа ", который больше чем" первый символ ". Назовем символ ceil как" второй характер.

3. Смените два символа, найденных в 2-х шагах.

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

Я обновил его ниже:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void swap(char* left, char* right)
{
    char temp = *left;
    *left = *right;
    *right = temp;
}
int compare (const void * a, const void * b)
{
  return ( *(char*)a - *(char*)b );
}
void PrintSortedPermutations(char* inStr)
{
    // Re-implementation of algorithm described here:
    // http://www.geeksforgeeks.org/lexicographic-permutations-of-string/
    int strSize = strlen(inStr);
    // 0. Ensure input container is sorted
    qsort(inStr, strSize, sizeof(char), compare);


    int largerPermFound = 1;
    do{
        // 1. Print next permutation
        printf("%s\n", inStr);
        // 2. Find rightmost char that is smaller than char to its right
        int i;
        for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){}

        // if we couldn't find one, we're finished, else we can swap somewhere
        if (i > -1)
        {
            // 3 find character at index j such that 
            // inStr[j] = min(inStr[k]) && inStr[k] > inStr[i] for all k > i
            int j = i+1;
            int k;
            for(k=j;k<strSize && inStr[k];++k)
            {
                if (inStr[k] > inStr[i] && inStr[k] < inStr[j])
                    j = k;
            }

            // 3. Swap chars at i and j
            swap(&inStr[i], &inStr[j]);

            // 4. Sort string to the right of i
            qsort(inStr+i+1, strSize-i-1, sizeof(char), compare);
        }
        else
        {
            largerPermFound = 0;
        }
    }while(largerPermFound);
}

int main(void) {
    char str[] = "abc";

    PrintSortedPermutations(str);
    return 0;
}

Выход

abc
acb
bac
bca
cab
cba

Живая демонстрация

В С++

std::next_permutation из библиотеки <algorithm> сделает это за вас, просто убедитесь, что вы сначала сортируете свой контейнер:

Возвращаемое значение

true, если функция может переупорядочить объект как лексикографию большая перестановка. В противном случае функция возвращает false для указания что договоренность не больше, чем предыдущая, но самая низкая возможно (отсортировано в порядке возрастания).

Например:

std::string myStr = "abc";
std::stable_sort(std::begin(myStr), std::end(myStr));
do {
    for(auto&& element : myStr)
        std::cout << element << " ";
    std::cout << std::endl;
} while (std::next_permutation(std::begin(myStr), std::end(myStr)));

Вывод:

a b c
a c b
b a c
b c a
c a b
c b a

Живая демонстрация

Ответ 2

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

Вот два решения.

Решение 1)

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

Например, вот рекурсивная версия на Python

def permute(done, remaining):
  if not remaining:
    print done
    return

  sorted_rem = sorted(remaining)
  l = len(sorted_rem)

  for i in xrange(0, l):
    c = sorted_rem[i]

    # Move to c to done portion.
    done.append(c)
    remaining.remove(c)

    # Permute the remaining
    permute(done, remaining)

    # Put c back.
    remaining.append(c)
    # Remove from done.
    del done[-1]

permute([], [1,2,3,4])

Вот оно.

Решение 2)

Хотя Решение 1 работает и его легко понять, я подозреваю, что мы можем тратить время на сортировку. Это решение ближе к тому, что у вас есть.

Рекурсия - это в основном скрытая математическая индукция, и этот способ мышления очень полезен для понимания того, как писать рекурсивные программы.

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

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

// By induction assumption, permute(a, i, n)
// goes through all the permutations of a[i], ..., a[n-1]
// in lexicographic order, by modifying a itself.
void permute(char *a, int i, int n) {
    if (i == (n-1)) {
       printf("%s\n", a);
      return;
    }

    int j;
    // We pick the n-i posibilities for the position a+i, then recursively
    // compute the permutations of a[i+1], ..., a[n-1]
    // So first pick the smallest possible for a+i, recurse.
    // Then the next possible for a+i, then recurse etc.

    for (j = i; j < n; j++) {
      permute(a, i+1, n);
      // By our induction assumption, at this point, 
      // a[i+1], a[i+2], .., a[n-1]
      // must be the lexicographically the largest possible!

      // So now reverse that portion.
      reverse(a+i+1, a+n-1);

      // Now we need to pick the lexicographically next element for
      // position a+i. This is nothing but the element which is just
      // larger than the current a+i.

      int k = i+1;
      while(k < n && a[i] > a[k]) {
        k++;
      }

      if (k >= n) {
        continue;
      }
      // Choose the next value for a+i.
      swap(a+i, a+k);
    }
    // Notice that the portion a[i+1], ..., a[n-1]  is sorted increasing.
    // when the loop exits. Also a[i] will be the largest element.
    // We need to reverse so that a[i], .., a[n-1] is the lexicographically
    // largest permutation to  maintain the induction (recursion) assumption.
    reverse(a+i+1, a+n-1);
}

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

Кстати, общим итерационным алгоритмом для генерации перестановок в лексикографическом порядке является алгоритм Нараяны Пандиты, упоминаемый другими, но не по имени.

Смотрите эту ссылку: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Это то, что использует std::next из C++ и множество других библиотек.

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

Ответ 3

IMHO, было бы проще сначала отсортировать символы строки, потому что количество перестановок (n!) всегда больше (или равно для n = 1 или 2), чем количество символов.

И вы были недалеко от решения, но вы должны повернуть, а не своп. Вот небольшая вариация, которая возвращает массив динамически выделенных строк, которые печатаются в основном:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int char_compare(const void *a, const void *b) {
    return (*((char *) a)) - (*((char *) b));
}

int fact(int n) {
    int f = 1;
    while (n > 0) {
        f *= n--;
        if (f < 0) return 0;
    }
    return f;
}

void rotateback(char *a, int i, int j) {
    int k;
    char tmp;
    tmp = a[i];
    for(k=i; k<j; k++) {
        a[k] = a[k+1];
    }
    a[j] = tmp;
}

void rotate(char *a, int i, int j) {
    int k;
    char tmp;
    tmp = a[j];
    for(k=j; k>i; k--) {
        a[k] = a[k-1];
    }
    a[i] = tmp;
}

void permute(char *a, int i, int n, char ***permuts) {
    int j;
    if (i == (n-1)) {
        **permuts = strdup(a);  // store a copy of the string
        *permuts += 1;          // and point to next location
    }
   else {
       for (j = i; j < n; j++) {
           rotate(a, i, j);
           permute(a, i+1, n, permuts);
           rotateback(a, i, j);
       }
   }
}
char ** permutations(const char *str_orig) {
    int i, j;
    size_t n = strlen(str_orig);
    size_t fact_n = fact(n);
    char ** permuts, **work;

    char * str = strdup(str_orig); // get a local copy
    qsort(str, n, 1, char_compare); // and sort it

    permuts = work = calloc(fact_n, sizeof(char *)); // allocate n! pointers

    permute(str, 0, n, &work);
    return permuts;
}

int main() {
    char str[] = "cab";
    int i;

    char **permuts = permutations(str);

    for (i=0; i<fact(strlen(str)); i++) {
        printf("\"%s\"\n", permuts[i]);
        free(permuts[i]);
    }
    free(permuts);
    return 0;
}

Вывод корректно:

"abc"
"acb"
"bac"
"bca"
"cab"
"cba"

Ответ 4

Еще один поворот в лексических строковых перестановках заключается в том, чтобы сохранить перестановку в динамически распределенном массиве указателей на строку и передать массив в qsort, чтобы обеспечить вывод в лексическом порядке. Поскольку перестановки растут экспоненциально, особенно важны проверки на исчерпание памяти после каждого выделения. Размер строки ниже ограничен 16 символами, что может привести к исчерпанию памяти в зависимости от объема доступной памяти.

Обновлено, передающее адрес массива для хранения перестановок строк, требуется для перераспределения для работы в рекурсивной функции.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXS 128
#define MAXC 16

size_t maxs;

void swap (char *x, char *y);
int cmp_pa (const void * a, const void * b);
char **realloc_char (char **sp, size_t *n);
void permute_pa (char ***pa, size_t *idx, char *a, int i, int n);

int main (int argc, char **argv)
{
    size_t i = 0;
    size_t idx = 0;
    size_t len = 0;
    char a[MAXC] = {0};
    char **pa = NULL;

    maxs = MAXS;                            /* initialize realloc counter   */

    if (argc > 1)                           /* set string to permute        */
        strcpy (a, argv[1]);
    else
        strcpy (a, "abc");

    len = strlen (a);                       /* lenght to permute or MAXC    */
    if (len > MAXC) len = MAXC;

    if (!(pa = calloc (MAXS, sizeof *pa)))  /* allocate MAXS pointers       */
        return 1;

    permute_pa (&pa, &idx, a, 0, len - 1);  /* call permute function        */

    printf ("\n no of permutations : %zu\n\n", idx);
    printf (" unsorted permutations of %s\n\n", a);

    for (i = 0; i < idx; i++)
        printf (" %s\n", pa[i]);

    qsort (pa, idx, sizeof *pa, cmp_pa);    /* sort array of permutations   */

    printf ("\n sorted permutations of %s\n\n", a);

    for (i = 0; i < idx; i++)
        printf (" %s\n", pa[i]);

    for (i = 0; i < idx; i++)               /* free all allocated memory    */
        free (pa[i]);
    free (pa);

    return 0;
}

/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* qsort compare function */
int cmp_pa (const void * a, const void * b)
{   return strcmp (*(char**)a, *(char**)b); }

/* realloc an array of pointers to strings setting memory to 0. */
char **realloc_char (char **sp, size_t *n)
{
    char **tmp = realloc (sp, 2 * *n * sizeof *sp);
    if (!tmp) {
        fprintf (stderr, "Error: struct reallocation failure.\n");
        // return NULL;
        exit (EXIT_FAILURE);
    }
    sp = tmp;
    memset (sp + *n, 0, *n * sizeof *sp); /* memset new ptrs 0 */
    *n *= 2;

    return sp;
}

/* Function to store permutations of string in array of pointers-to-string
This function takes five parameters:
1. allocated array of pointers-to-string
2. pointer to array index
3. string to permute
4. starting index of the string (zero based)
5. ending index of the string. (zero based)
*/
void permute_pa (char ***pa, size_t *idx, char *a, int i, int n)
{
    int j;
    if (i == n) {
        (*pa)[*idx] = strdup (a);
        if (!(*pa)[*idx]) {
            fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
            exit (EXIT_FAILURE);
        }
        (*idx)++;
        if (*idx == maxs)
            *pa = realloc_char (*pa, &maxs);
    }
    else {
        for (j = i; j <= n; j++) {
            swap ((a+i), (a+j));
            permute_pa (pa, idx, a, i+1, n);
            swap ((a+i), (a+j));
        }
    }
}

Выход

$ ./bin/str_permute_lex

 no of permutations : 6

 unsorted permutations of abc

 abc
 acb
 bac
 bca
 cba
 cab

 sorted permutations of abc

 abc
 acb
 bac
 bca
 cab
 cba

Проверка ошибок памяти

$ valgrind ./bin/str_permute_lex
==29709== Memcheck, a memory error detector
==29709== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==29709== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==29709== Command: ./bin/str_permute_lex
==29709==

 no of permutations : 6

 <snip>

==29709==
==29709== HEAP SUMMARY:
==29709==     in use at exit: 0 bytes in 0 blocks
==29709==   total heap usage: 7 allocs, 7 frees, 1,048 bytes allocated
==29709==
==29709== All heap blocks were freed -- no leaks are possible
==29709==
==29709== For counts of detected and suppressed errors, rerun with: -v
==29709== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

Ответ 5

Основная идея состоит в том, чтобы начать с нашей основной строки как "и оставшейся строки как" abc" (или любой, который вы хотите).

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

Повторяйте то же самое, пока не получите длину n (длина основной строки).

Хорошо, объяснение не ясно, но следите за кодом. Все будет ясно.

#include<iostream>

void perm(std::string sub, std::string rem, int n)
{
    if(n==0)
        //print if n is zero i.e length achieved
        std::cout<<sub<<"\n";

    for(int i=0; i<n; i++)
        //append a character and pass remaining to rem string
        perm(sub + rem[i] , rem.substr(0,i) + rem.substr(i+1,n-1), n-1);
}

int main()
{
    perm("", "abc", 3);
}

Выход

abc
acb
bac
bca
cab
cba

Ответ 6

Это добровольно ответ, который отвечает не на этот вопрос.

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

Это может быть простая рекурсивная реализация C, чтобы получить все перестановки в лексикографическом порядке. Он не оптимизирован, но его легко понять и реализовать:

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

Конкретная реализация:

#include <stdio.h>

#define SIZE 4

void disp(int *fullarr, int n, int * begin, int pos) {
    int i, j;
    int found;
    if (pos == n) {
        for(i=0; i< n; i++) {
            printf("%2d", begin[i]);
        }
        printf("\n");
        return;
    }
    for (i=0; i<n; i++) {
        found = 0;
        for (j=0; j<pos; j++) {
            if (fullarr[i] == begin[j]) {
                found = 1;
                break;
            }
        }
        if (! found) {
            begin[pos] = fullarr[i];
            disp(fullarr, n, begin, pos+1);
        }
    }
}

int main() {
    int i;
    int fullarr[SIZE], begin[SIZE];
    for (i=0; i<SIZE; i++) {
        fullarr[i] = i;
    }
    disp(fullarr, SIZE, begin, 0);
    return 0;
}

Ответ 7

void permute(string str,int index)
{
 if(index ==  str.size())
 {
    cout<<str<<" ";
    return;
 }
 else
 {
    for(int j=index;j<str.size();j++)
    {
        if(str[index] <= str[j]) // swap only in sorted order 
        swap(str[j],str[index]);
        permute(str,index+1);
        if(str[index] <= str[j]) // swap only in sorted order 
        swap(str[j],str[index]);
    }
 }
}
int main()
{
 int t; 
 string str;
    scanf("%d",&t);
    while(t--){
        // scanf("%d",&n);
        cin>>str;
        sort(str.begin(),str.end());
        permute(str,0);
        cout<<endl;

    }
  return 0;
}