#include<stdio.h>
#include?<string.h>
void?swap(char?*a,char?*b)
{
char?temp=*a;
*a?=?*b;
*b?=?temp;
}
int?nextperm(char?a[],?int?n)?//?字典序排列(從升序到降序排列(也可從降序到升序))基於ASCII碼準則
{
int?i,j,k=-1,l;
for(i=0;i<n-1;i++)?//?從前向後方向掃描,找到最後壹對為升序的相鄰元素(如果不存在,則所有排列已完成)
{
if(a[i]<a[i+1])?
k=i;?//?把最後壹對為升序的相鄰元素(靠左邊)的下標賦值給k
}
if?(k>=0)//?k>=0說明找到壹對為升序的相鄰元素
{?
l=-1;
for(i=0;i<n;i++)
{
if(a[k]<a[i])?l=i;
}?
swap(&a[k],&a[l]);//?交換下標為k和l的元素
for(i=k+1;i<n;i++)//?扭轉索引k+1後面的元素
{
j?=?n?-?i?+?k;if?(i?>=?j)?break;?
swap(&a[i],&a[j]);
}
}
if?(k==-1)?return?0;
for(i=0;i<n;i++)?printf("%c",a[i]);
printf("\n");
return?1;?
}
int?main()
{
int?i,?lens;
char?ch[10];
printf("Please?input?string?(longest?10):");
scanf("%s",ch);
lens=strlen(ch);
for(i=0;i<lens;i++)printf("%c",ch[i]);
printf("\n");
while?(nextperm(ch,lens));
return?0;?
}
註：該算法參考了14世紀印度數學家 納拉亞納潘迪特的思想,
我們偉大的數學家納拉亞納潘迪特的字典序思想原文(英文版的)如下:
-- 國內很多人使用這種技術但他(她)們並不知道該算法思想的創始者是誰?因為網上所看到的帖子個個都打著原創,其實不然,所以我對此表示很遺憾.因為真正的原創是追溯到14世紀印度數學家 納拉亞納潘迪特
下面是該算法的英文簡介(目前手頭上只有數學家的英文資料沒有中文的,所以將就著看):
Generation in lexicographic order:
There are many ways to systematically generate all permutations of a given sequence.[16]?One classical algorithm, which is both simple and flexible, is based on finding the next permutation in?lexicographic ordering, if it exists. It can handle repeated values, for which case it generates the distinct multiset permutations each once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the?factorial number system) and converting those to permutations. To use it, one starts by sorting the sequence in (weakly)?increasing?order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to?Narayana Pandita?in 14th century India, and has been frequently rediscovered ever since.[17]
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
Find the largest index?k?such that?a[k] <?a[k?+ 1]. If no such index exists, the permutation is the last permutation.
Find the largest index?l?such that?a[k] <?a[l].
Swap the value of?a[k] with that of?a[l].
Reverse the sequence from?a[k?+ 1] up to and including the final element?a[n].
For example, given the sequence [1, 2, 3, 4] which starts in a weakly increasing order, and given that the index is?zero-based, the steps are as follows:
Index?k?= 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than?a[k + 1]?which is 4.
Index?l?= 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition?a[k] < a[l].
The values of?a[2]?and?a[3]?are swapped to form the new sequence [1,2,4,3].
The sequence after?k-index a[2]?to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1,2,4,3].
Following this algorithm, the next lexicographic permutation will be [1,3,2,4], and the 24th permutation will be [4,3,2,1] at which point?a[k] < a[k + 1]?does not exist, indicating that this is the last permutation.