初めての再帰バージョンを理解するのは難しく、ベレの方法を探すのに時間がかかりました。見つけるためのより良い方法 (私が考えることができる) は、Narayana Panditaによって提案されたアルゴリズムを使用することです。基本的な考え方は次のとおりです。
- 最初に、指定された文字列を減少しない順序で並べ替えてから、辞書順で次の文字よりも小さい末尾からの最初の要素のインデックスを見つけます。この要素インデックスを「firstIndex」と呼びます。
- 「firstIndex」の要素よりも大きい最小の文字を見つけます。この要素インデックスを「ceilIndex」と呼びます。
- 「firstIndex」と「ceilIndex」の要素を交換します。
- インデックス 'firstIndex+1' から文字列の末尾までの文字列の部分を逆にします。
- (ポイント 4 の代わりに) 文字列の一部をインデックス 'firstIndex+1' から文字列の末尾まで並べ替えることもできます。
ポイント 4 と 5 は同じことを行いますが、ポイント 4 の場合の時間計算量は O(n*n!) であり、ポイント 5 の場合は O(n^2*n!) です。
上記のアルゴリズムは、文字列に重複する文字がある場合にも適用できます。:
文字列のすべての順列を表示するコード:
#include <iostream>
using namespace std;
void swap(char *a, char *b)
{
char tmp = *a;
*a = *b;
*b = tmp;
}
int partition(char arr[], int start, int end)
{
int x = arr[end];
int i = start - 1;
for(int j = start; j <= end-1; j++)
{
if(arr[j] <= x)
{
i = i + 1;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[end]);
return i+1;
}
void quickSort(char arr[], int start, int end)
{
if(start<end)
{
int q = partition(arr, start, end);
quickSort(arr, start, q-1);
quickSort(arr, q+1, end);
}
}
int findCeilIndex(char *str, int firstIndex, int n)
{
int ceilIndex;
ceilIndex = firstIndex+1;
for (int i = ceilIndex+1; i < n; i++)
{
if(str[i] >= str[firstIndex] && str[i] <= str[ceilIndex])
ceilIndex = i;
}
return ceilIndex;
}
void reverse(char *str, int start, int end)
{
while(start<=end)
{
char tmp = str[start];
str[start] = str[end];
str[end] = tmp;
start++;
end--;
}
}
void permutate(char *str, int n)
{
quickSort(str, 0, n-1);
cout << str << endl;
bool done = false;
while(!done)
{
int firstIndex;
for(firstIndex = n-2; firstIndex >=0; firstIndex--)
{
if(str[firstIndex] < str[firstIndex+1])
break;
}
if(firstIndex<0)
done = true;
if(!done)
{
int ceilIndex;
ceilIndex = findCeilIndex(str, firstIndex, n);
swap(&str[firstIndex], &str[ceilIndex]);
reverse(str, firstIndex+1, n-1);
cout << str << endl;
}
}
}
int main()
{
char str[] = "mmd";
permutate(str, 3);
return 0;
}