不唯一字符按字典顺序排列

Matt 发表于 Dev

马特

我想让函数按字典顺序输出输入字符串中所有可能的排列。

我有以下代码：

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排序的。

它仅适用于唯一字符的排列，没有任何问题，但是我需要它也适用于非唯一字符的字符串，关于如何对其进行调整/修改/工作的任何想法？我必须使用递归，并且不应该使用任何种类的排序，也不应该将其存储在任何数组中，而只是打印。我想打印所有，甚至是重复的。

约翰·库拉克（John Kurlak）

警告：不是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);
    }
}

该算法在此处描述。有关示例/解释，请参见评论部分，或参见下面的转录：

假设我们正在寻找下一个最大的数字排列，范围是1-9。

例如，假设我们有：123479865

我们想要找到大于123479865的最小数字，可以通过重新排列123479865的数字来获得最小的数字。

这意味着我们必须使它至少比现在大一位数。如果我们有选择，我们希望将最右边的数字变大，因为这将导致最小的变化。如果我们将剩余数字增加，将会导致价值的更大变化。

例如：12347986 5 => 12347986 6比1 23479865 => 2 23479865小得多。

因此，我们想找到最右边的数字，我们可以将其增大。为了使数字更大，我们必须在序列中找到一个比其大的数字，然后将两者交换。

注意：我们不能将数字（例如5）与左边的数字（例如6）互换，因为那样的话，我们将减少左边数字的值，这将使我们的整体数字更小。例如，如果将5替换为6，我们将得到1234798 56，它小于1234798 65。因此，我们总是在右边交换一个数字。

因此，让我们从最右边的数字开始浏览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 8 9 7 65。

数字123489765大于123479865，但是实际上我们可以使其保持较小，同时保持它大于123479865。之所以可以这样做，是因为我们现在可以自由更改以下任何数字：12348 9765（8右边的任何数字））。这些数字可以尽可能小，因为它们左侧的8可以确保新数字始终更大。

减小数字9765的最佳方法是按升序对它们进行排序，从而得出5679。排序之所以有效，是因为最左边的位置值对整体值的贡献最大。因此，我们希望最左边的数字是最小的数字。

这给我们留下了12348 5679，这是我们的答案。

注意：实际上，我们不必将数字排序在8的右边。我们实际上可以颠倒它们的顺序，因为我们知道从右侧到8的数字是递增的顺序（因为更早的时候，我们第一次停下来了得出的数字小于先前的数字）。