c - 不具有唯一字符的字典顺序排列

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 .请参阅评论部分以获取示例/解释，或查看下面的转录:

Let's pretend we're finding the next largest permutation of digits from 1-9.

For example, suppose we have: 123479865

We want to find the smallest number greater than 123479865 that can be obtained by rearranging the digits of 123479865.

What this means is that we have to make at least one digit bigger than it currently is. If we had our choice, we would want to make the rightmost digit bigger since that will result in the smallest change. If we were to make a left number bigger, it would result in a bigger change in value.

e.g.: 123479865 => 123479866 is a much smaller change than 123479865 => 223479865.

Therefore, we want to find the farthest digit to the right that we can make bigger. In order to make a digit bigger, we have to find another number bigger than it within our sequence and then swap the two.

Note: we cannot swap a number (e.g., 5) with a number to its left (e.g., 6), because then we would be decreasing the value of a digit to our left, which would make our overall number smaller. For example, if we swapped 5 with 6, we would get 123479856, which is smaller than 123479865. Thus, we always swap with a number to our right.

So let's go through 123479865, starting with the rightmost digit.

There is nothing bigger than 5 to the right of 5, so we can't make 5 bigger.

Now let's consider 6. There is nothing bigger than 6 to the right of 6, so we can't make 6 bigger.

Now let's consider 8. There is nothing bigger than 8 to the right of 8, so we can't make 8 bigger.

Now let's consider 9. There is nothing bigger than 9 to the right of 9, so we can't make 9 bigger.

Now let's consider 7. There are a few numbers to the right of 7 that are bigger than 7, namely: 9 and 8. Therefore, we can make 7 bigger. We want to make it bigger by the least amount, so we should swap it with the smallest value that is bigger than 7. In other words, we should swap 7 with 8. That gives us: 123489765.

The number 123489765 is bigger than 123479865, but we can actually make it smaller while maintaining that it's bigger than 123479865. We can do this because we now have infinite freedom to change any of the following digits: 123489765 (anything to the right of 8). Those numbers can be as small as possible because the 8 to their left ensures that the new number is always bigger.

The best way to make the digits 9765 smaller is to sort them in increasing order, giving us 5679. Sorting works because the leftmost place values contribute the most to the overall value. Therefore, we want the leftmost digits to be the smallest digits.

That leaves us with 123485679, which is our answer.

Note: we don't actually have to sort the numbers to the right of 8. We can actually reverse their order because we know that the numbers from the right side to 8 are in increasing order (because earlier, we stopped the first time we got to a number that was smaller than its previous number).