C言語で文字列配列の全順列を生成!next_permutationアルゴリズムの実装方法

問題概要

複数の文字列が配列に格納されている状況を考えてみましょう。ここでの課題は、それらの文字列のすべての順列(並べ替え)を1行ずつ出力することです。

たとえば、入力が ["abc", "def", "ghi"] の場合、期待される出力は次のようになります。

abc def ghi
abc ghi def
def abc ghi
def ghi abc
ghi abc def
ghi def abc

解き方のアプローチ

この問題は、辞書順で「次の順列」を生成する next_permutation アルゴリズムを使うと、シンプルかつ効率的に解けます。手順は以下のとおりです。

• next_permutation() 関数を定義する。引数には要素数 n と文字列配列 s を渡します。
• 配列を末尾から走査し、s[i] > s[i-1] を満たす位置 i を探します。この位置が「入れ替えの起点(ピボット)」となります。
• ピボットより右側の要素の中から、s[i-1] より大きい値のうち最小のものを見つけ、s[i-1] と交換します。
• 交換した位置より右側の部分列を反転し、昇順に整列します。
• 新しい順列が作れた場合は 1 を、これ以上の順列が存在しない場合は 0 を返します。
• main 関数では do-while ループにより、next_permutation() が 0 を返すまで次の処理を繰り返します。
  • 現在の順列に含まれる文字列をすべて表示します。最後の要素のあとは改行し、それ以外の場合は空白で区切ります。

実装例

理解を深めるために、実際のコードを見てみましょう。

#include <stdio.h>
#include <string.h>
int next_permutation(int n, char **s){
    for (int i = n - 1; i > 0; i--)
        if (strcmp(s[i], s[i - 1]) > 0){
            int j = i + 1;
            for (; j < n; j++)
                if (strcmp(s[j], s[i - 1]) <= 0)
                    break;
            char *t = s[i - 1];
            s[i - 1] = s[j - 1];
            s[j - 1] = t;
            for (; i < n - 1; i++, n--){
                t = s[i];
                s[i] = s[n - 1];
                s[n - 1] = t;
            }
            return 1;
        }
    for (int i = 0; i < n - 1; i++, n--){
        char *t = s[i];
        s[i] = s[n - 1];
        s[n - 1] = t;
    }
    return 0;
}
int main(){
    char *strings[] = {"abc", "def", "ghi"};
    int n = 3;
    do{
        for (int i = 0; i < n; i++)
            printf("%s%c", strings[i], i == n - 1 ? '\n' : ' ');
    } while (next_permutation(n, strings));
}

入力

{"abc", "def", "ghi"}

出力

abc def ghi
abc ghi def
def abc ghi
def ghi abc
ghi abc def
ghi def abc

まとめ

next_permutation アルゴリズムを利用すれば、文字列配列のすべての順列を辞書順に漏れなく生成できます。1回の呼び出しにかかる計算量は O(n) であり、全体では順列の総数 n! に比例します。さらに、同じ文字列が含まれる場合でも重複した順列を出力しないという利点があります。C++ の std::next_permutation と同じ発想に基づく手法なので、他の言語でも幅広く応用できるでしょう。