我想用字典顺序把函数从输入字符串中输出所有可能的排列。
我有以下代码：
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;
}
输入字符串排列是排列打印排序。
它对只有唯一字符的排列没有任何问题，但我也需要它对字符非唯一字符串起作用，有什么想法可以调整它/修改它/工作吗？我必须使用递归，不应该使用任何排序，也不应该将其存储在任何数组中，只需打印我想打印所有的，甚至是复制品。
最佳答案
警告：不是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的数字来获得。
这意味着我们必须至少比现在大一位数如果我们有自己的选择，我们会想让最右边的数字变大，因为这将导致最小的变化。如果我们把左边的数字调大一点，就会导致数值的更大变化。
例如：123479865=>123479866比123479865=>223479865的变化要小得多。
因此，我们想找到最远的数字在右边，我们可以使更大。为了使一个数字变大，我们必须在序列中找到另一个大于它的数字，然后交换这两个数字。
注意：我们不能把一个数字（如5）换成一个左边的数字（如6），因为这样我们就会减少左边一个数字的值，这会使我们的总数字变小。例如，如果我们将5替换为6，我们将得到123479856，它小于123479865。因此，我们总是用右边的数字交换。
让我们看一下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这给了我们：123489765。
123489765比123479865大，但我们实际上可以使它变小，同时保持它比123479865大。我们可以这样做，因为我们现在可以无限自由地更改以下任何数字：123489765（8右边的任何数字）这些数字可以尽可能小，因为他们左边的8确保新的数字总是更大。
使数字9765变小的最好方法是按递增顺序对它们进行排序，得到5679排序工作是因为最左边的位置值对整体值的贡献最大。因此，我们希望最左边的数字是最小的数字。
剩下123485679，这是我们的答案。
注意：我们实际上不必把数字排在8的右边。实际上，我们可以颠倒它们的顺序，因为我们知道从右边到8的数字是按递增的顺序排列的（因为在前面，我们第一次得到一个比之前的数字小的数字时就停止了）。