In C
有一个非常简单的算法描述(加上实现)极客之极客 http://www.geeksforgeeks.org/lexicographic-permutations-of-string/:
给定一个字符串,按排序顺序打印它的所有排列。为了
例如,如果输入字符串是“ABC”,则输出应该是“ABC,
ACB、BAC、BCA、CAB、CBA”。
我们在这篇文章中讨论了一个打印所有排列的程序,
但这里我们必须按升序打印排列。
以下是按字典顺序打印排列的步骤
按非降序对给定字符串进行排序并打印它。第一个排列始终是按非降序排序的字符串。
开始生成下一个更高的排列。这样做直到不可能进行下一个更高的排列。如果我们达到一个排列,其中所有
字符按非递增顺序排序,然后排列
是最后一个排列。
生成下一个更高排列的步骤:
1. 取出先前打印的排列并找到其中最右边的字符,该字符小于其下一个字符。让我们打电话
该字符作为“第一个字符”。
现在找到“第一个字符”的上限。 Ceiling 是“第一个字符”右侧最小的字符,较大者
比“第一个字符”。让我们将 ceil 字符称为“第二个”
特点'。
交换上面 2 个步骤中找到的两个字符。
在“第一个字符”的原始索引之后对子字符串进行排序(按非降序)。
我在下面重新实现了它:
#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;
}
Output
abc
acb
bac
bca
cab
cba
现场演示 http://ideone.com/3WHHtG
In C++
std::next_permutation http://www.cplusplus.com/reference/algorithm/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)));
Output:
a b c
a c b
b a c
b c a
c a b
c b a
现场演示 http://ideone.com/2yzLva