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

Question

Я хочу сделать функцию для вывода всех возможных перестановок из входной строки в лексикографическом порядке.

У меня есть следующий код:

void permutations_print(char *permutations, int index, int length) { 
    if (index == length) { 
     printf("\"%s\"\n", permutations); 
    } 
    for (int i = index; i < length; i++) { 
     rotate(permutations, i, index); 
     permutations_to_array(permutations, index + 1, length); 
     rotate_back(permutations, index, i); 
    } 
} 

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

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

входной строка подстановки permutations_print сортируется.

Он работает без каких-либо проблем с перестановками только с уникальными символами, но мне нужно, чтобы он работал и для персонажей, не являющихся уникальными строками, любыми идеями по его настройке/модификации/работе? Я должен использовать рекурсию и не должен использовать какую-либо сортировку, и я не должен хранить ее в любом массиве, просто печатаю. И я хочу напечатать все, даже дубликаты.

Answer 1

Предупреждение: не программист на C, поэтому мой код определенно может быть улучшен.

Вы можете сделать это итеративно с чем-то вроде этого:

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

void swap(char* array, int i, int j); 
void reverse(char* array, int left, int right); 
bool nextPermutation(char* array, int n); 
int compareCharacters(const void * a, const void * b); 
void printPermutations(char *permutations, int length); 

int main() { 
    char myArray[] = "hey"; 
    printPermutations(myArray, 3); 

    return 0; 
} 

void printPermutations(char *array, int length) { 
    qsort(array, length, sizeof(char), compareCharacters); 
    *(array + length) = '\0'; 

    do { 
     printf("%s\n", array); 
    } while (nextPermutation(array, length)); 
} 

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

bool nextPermutation(char* array, int n) { 
    if (n <= 1) { 
     return false; 
    } 

    // Find index, swapIndex1, of rightmost number that has a number greater than it 
    int swapIndex1; 

    for (swapIndex1 = n - 2; swapIndex1 >= 0; --swapIndex1) { 
     if (array[swapIndex1] < array[swapIndex1 + 1]) { 
      break; 
     } 
    } 

    if (swapIndex1 == -1) { 
     return false; 
    } 

    // Find index, swapIndex2, of smallest number to the right of that and greater than it 
    int swapIndex2 = swapIndex1 + 1; 
    int minToRight = array[swapIndex2]; 

    for (int i = swapIndex2 + 1; i < n; ++i) { 
     if (array[i] <= minToRight && array[i] > array[swapIndex1]) { 
      minToRight = array[i]; 
      swapIndex2 = i; 
     } 
    } 

    // Swap values at swapIndex1 and swapIndex2 
    swap(array, swapIndex1, swapIndex2); 

    // Reverse values from swapIndex1+1 to n-1 
    reverse(array, swapIndex1 + 1, n - 1); 

    return true; 
} 

void swap(char* array, int i, int j) { 
    char temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
} 

void reverse(char* array, int left, int right) { 
    for (; left < right; ++left, --right) { 
     swap(array, left, right); 
    } 
} 

Алгоритм описан here. См. Раздел комментариев для примера/объяснения или см. Транскрипцию ниже:

Давайте сделаем вид, что находим следующую большую перестановку цифр от 1 до 9.

Например, предположим, что мы имеем: 123479865

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

Что это означает, что мы должны сделать по крайней мере, на одну цифру, большую, чем в настоящее время. Если бы у нас был наш выбор, мы бы хотели сделать самую правую цифру больше, поскольку это приведет к наименьшему изменению. Если бы мы сделали большее число слева, это привело бы к большему изменению стоимости.

например: 12347986 => 12347986 гораздо меньше изменений, чем 23479865 => 23479865.

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

Примечание: мы не можем поменять число (например, 5) на число слева (например, 6), потому что тогда мы будем уменьшать значение цифры слева от нас, что сделало бы наше общее число меньше , Например, если мы заменили 5 на 6, мы получим 1234798 , который меньше 1234798 . Таким образом, мы всегда поменяем номер справа от нас.

Итак, давайте рассмотрим 123479865, начиная с самой правой цифры.

Нет ничего большего, чем 5 справа от 5, поэтому мы не можем сделать 5 больше.

Теперь давайте рассмотрим 6. Нет ничего большего, чем 6 справа от 6, поэтому мы не можем сделать 6 больше.

Теперь давайте рассмотрим 8. Нет ничего большего, чем 8 справа от 8, поэтому мы не можем сделать 8 больше.

Теперь давайте рассмотрим 9. Нет ничего большего, чем 9 справа от 9, поэтому мы не можем сделать 9 больше.

Теперь рассмотрим 7. Есть несколько чисел справа от 7, которые больше 7, а именно: 9 и 8. Поэтому мы можем сделать 7 больше. Мы хотим сделать его больше на наименьшую сумму, поэтому мы должны поменять его наименьшим значением, которое больше 7. Другими словами, мы должны поменять 7 на 8. Это дает нам: 1234 65 .

число 123489765 больше, чем 123479865, но мы действительно можем сделать его меньше, сохраняя при этом, что это больше, чем 123479865. мы можем сделать это, потому что мы теперь имеем бесконечную свободу менять любой из следующих цифр: 12348 (что-либо справа от 8). Эти цифры могут быть как можно меньше, потому что 8 слева от них гарантируют, что новое число всегда больше.

Лучший способ сделать цифры 9765 меньше - сортировать их в порядке возрастания, давая нам 5679. Сортировка работает, потому что самые левые значения места вносят наибольший вклад в общее значение. Поэтому мы хотим, чтобы самые левые цифры были наименьшими цифрами.

Это оставляет нам 12348 , что является нашим ответом.

Примечание: нам действительно не нужно сортировать числа справа от 8. Мы можем фактически изменить порядок, потому что мы знаем, что числа с правой стороны до 8 находятся в порядке возрастания (поскольку ранее мы остановились первый раз мы получили число, которое было меньше его предыдущего номера).