順列列挙をC言語で実装するやり方

先日行われたABCで、順列列挙（c++でいうところのnext_permutation)が出題された。
https://atcoder.jp/contests/abc302/tasks/abc302_c
この手の問題は時折出題されるので、後学のためC言語での実装にチャレンジしてみる。以下はその備忘録である。
前提として、ここでの目標は、「あるint型配列に対して、それを並べ替えてできる全ての配列を辞書順に出力する」こととする。

参考記事

この記事を書くにあたって、以下のサイトを参考にしている。

順列列挙の関数のイメージ

「そもそも普段どのようにして順列を列挙しているか」というところから考えていこう。例えば、a={1,2,3,4}を並べ替えると、
１２３４
１２４３
１３２４
１３４２
１４２３
１４３２
２１３４
　：
４３２１
のように列挙できる。ここで注目してほしいのは、最初は「１２３４」と昇順で並んでいるのに対し、最後は「４３２１」と降順になっていることだ。何が言いたいかというと、順列列挙で我々がやっているのは、昇順の配列を少しずつ降順にしていくという作業なのである。（降順の正確な定義とは少し外れるが、わかりやすさのためこのように記述している）　ちょっと強引な気がするので他の部分も見てみよう。
「１２３４」→「１２４３」：３４が４３になっている。
「１３４２」→「１４２３」：ちょっと見づらいが、同様にして３→４の並びだったのが４→３になっている。
だから、実際のプログラムでも、s[i] < s[j]になっているところをswapしてs[i] > s[j]にしていくんだろうな〜という想像ができる。もちろんそれだけではなく、swapするべきiとjをうまいこと見つけてきたり、他にもなんやら色々しなきゃいけないわけなのだが、そこから先は下で説明しよう。

順列列挙の仕組み

実装したものは下に置いてあるが、長ったらしいので大事なところだけ抜き出して説明する。

void swap(int *a,int *b);//aとbのメモリを入れ替える
void reverse(int *s,int start,int end);//配列sのstart番目からend番目までを反転する
Bool permute(int *s,int n){
    int i = n-1;
    while (s[i-1] >= s[i])
    {
        i--;
        if (i == 0) {
            return false;
        }
        else{
            continue;
        }
    }
    int j = n-1;
    while (j > i && s[j] <= s[i-1]) {
        j--;
    }
    swap(&s[i-1],&s[j]);
    reverse(s,i,n-1);
    return true;

}

このコードでは、以下のようなステップを踏んで「配列sが与えられた時の、辞書順で次の配列」を計算している。

1.s[i-1] < s[i]なる初めのindexを探す

int i = n-1;
    while (s[i-1] >= s[i])
    {
        i--;
        if (i == 0) {
            return false;
        }
        else{
            continue;
        }
    }

具体的にはこの部分を指す。上のコードを見てみると、配列sの一番右から、s[i-1] < s[i]になっている初めのiを探している。
例えば１２３４なら、
3 < 4 が成立しているので i = 3となり、３１４２なら
4 > 2 → 不成立
1 < 4 → 成立　なので、i = 2となる。また、４３２１の場合、
2 > 1 → 不成立
3 > 2 → 不成立
4 > 3 → 不成立　と最後まで行ってしまうので、この場合はfalse(これが最後の配列です)を返す。
これはつまり、「右から調べて一番最初に昇順になっている部分を調べる」というものである。
これは普段やっている列挙と合致するので理解しやすいと思うが、１２３４に対していきなり１と２をswapされても困る。右から調べてやらないと順番が一気に飛んでしまうのだ。
ここまでのコードから、
「ここで見つけた昇順部分を降順に変えて仕舞えば、とりあえずもとの配列よりは辞書順で下のものができるだろう」というところまでは上のイメージから理解できるだろう。（降順になっているほど辞書順で下になるため）

2.s[i-1] < s[j]なる最初のjを配列の右側から探す

int j = n-1;
    while (j > i && s[j] <= s[i-1]) {
        j--;
    }
    swap(&s[i-1],&s[j]);

上の部分から、とりあえず辞書順で下のものを発見することには成功した。次は、この新たな配列を辞書順でsの次に来させるための作業である。ここでは、iの右側からs[i-1] < s[j]になる最初のjをまたまた配列の右側から探している。個人的にここを理解するのに大事だと思うのは、この時s[j]はs[i-1] < s[j]になるようなものの中での最小値ということだ。
少し話を戻す。辞書順の次に来るものを探す必要があるわけだが、例えば１２５４３の次を探すときに、２と５や２と４をswapしてしまうと、13...系列を飛ばしてしまう。（１３４５２とか１３５４２とか...)そのため、２とswapさせるのは2よりちょっとだけ大きい３が相応しい。
よって次のstepは、「s[i-1]より大きくて、かつその中での最小値を右側から探す」ことになる。今回の場合は３が当てはまるし、
１３５４２：３＞５よりs[i-1] = ３、s[i-1] < s[j]なる最小の数値は４
１５２４３：２＞４よりs[i-1] = ２、s[i-1] < s[j]なる最小の数値は３　となる。
もちろんfor文とかを使って最小値を満たすindexを探るのもアリだが、ここで使えるのは、「s[i]~s[n-1]は降順に並んでいる」ということだ。
一つ目のstepを思い出して欲しい。このstepでは、s[i-1] < s[i]なる最初のiを探していた。ということは、それより右側については、
s[i] >= s[i+1] >= s[i+2] >= s[i+3] ... >= s[n-1]のような形になっていなければおかしい。つまり降順に並んでいるのだ。ということは、右から調べて行って初めてs[i-1] < s[j]になっているようなs[j]は同時にそのような数字の中での最小値を取っているということになるのである。
（少し上で見せた三つの例について見てみると、確かにそうなっていることがわかるだろう）
これでswapすべき要素s[i-1]とs[j]が決まった。大きく見ればs[i-1] < s[j]と並んでいるのをs[i-1] > s[j]と降順にしているので、確かに今の所辞書順の下に来ていることがわかるだろう。

s[i]~s[n-1]をreverseする

reverse(s,i,n-1);

最後のstepがこれ。具体例から見てみよう。まず、１２５４３の次を調べるにあたって、２と３を入れ替えることが決まった。その結果、１２５４３→１３５４２と今のところなっているはずだ。当然ここまででは不十分であり、間に１３４５２や１３２４５などが挟まる。
正しい答えは１２５４３→１３２４５である。ここで注目するポイントは、１２５４３→１３２４５について、swapした３(=s[i-1])の次は昇順になっていることだ。他にも、
１４５３２→１５２３４：５以降は昇順
１５３４２→１５４２３：４以降は昇順、
１５３２４→１５３４２：少し分かりづらいが、４以降の要素は２一つしかないので昇順と捉えられる
のように、swapした時、s[i-1]より先（=s[i]~s[n-1])は全て昇順になっているのだ。そこで、
次のstepでは「s[i]~s[n-1]を昇順にする」ようにすればいいとわかる。もちろん汎用的なアルゴリズムを組んで昇順にしてやっても構わないのだが、実は「swap後もs[i]~s[n-1]は降順になっている」ことに気づけばreverseで十分だということがわかる。
そもそもswap前は、
s[i] >= s[i+1] >= s[i+2] ... >=s[j-1] >= s[j] >= s[j+1]>= ... >= s[n-1]になっていたのだ。
ここで、上のstepのプログラム上、s[i-1] >= s[j+1] かつ s[i-1] < s[j] <= s[j+1]という関係なので、s[i-1] = tmpと書くと、swap後も同様に
s[i] >= s[i+1] >= s[i+2] ... >=s[j-1] > tmp >= s[j+1]>= ... >= s[n-1]であるから降順のままなのだ。そのため、これをreverseしてやれば昇順に戻るのである。

実装したやつ

#include<stdio.h>
#include<stdlib.h>
int** return_permute_arr;//結果を保持するための配列
typedef enum{false,true} Bool;
void swap(int *x, int *y) 
{ 
    int temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
}
int factorial(int n){
    int ans = 1;
    for(int i = n;i > 0;i--){
        ans *= i;
    }
    return ans;
}
int compare(const void *a, const void *b){
    if(*(int*)a > *(int*)b){
        return 1;
    }
    else if(*(int*)a < *(int*)b){
        return -1;
    }
    else{
        return 0;
    }
}
void reverse(int* s,int start,int end){
    int i = start;
    int j = end;
    while(i < j){
        swap(&s[i],&s[j]);
        i++;
        j--;
    }
}
//ここから上の部分はそんなに気にしなくてOK
//本題はここ
Bool permute(int *s,int n){
    int i = n-1;
    while (s[i-1] >= s[i])
    {
        i--;
        if (i == 0) {
            return false;
        }
        else{
            continue;
        }
    }
    int j = n-1;
    while (j > i && s[j] <= s[i-1]) {
        j--;
    }
    swap(&s[i-1],&s[j]);
    reverse(s,i,n-1);
    return true;

}
void next_permutation_int(int *a, int n){
    return_permute_arr = (int**)malloc(sizeof(int*)*factorial(n));
    for(int i = 0;i < factorial(n);i++){
        return_permute_arr[i] = (int*)malloc(sizeof(int) * (n+1));
    }
    int* a_sorted = (int*)malloc(sizeof(int) * (n));
    for(int i = 0;i < n;i++){
        a_sorted[i] = a[i];
    }
    qsort(a_sorted,n,sizeof(int),compare);
    int counter = 0;
    for(int i = 0;i < n;i++){
        return_permute_arr[counter][i] = a_sorted[i];
    }
    counter++;
    while(permute(a_sorted,n)){
        for(int i = 0;i < n;i++){
            return_permute_arr[counter][i] = a_sorted[i];
        }
        counter++;
    }
    free(a_sorted);
}  
//テスト
int main() 
{ 
    int arr[] = {1,2,3};
    int n = 3;
    next_permutation_int(arr, n);
    for(int i = 0;i < factorial(n);i++){
        for(int j = 0;j < n;j++){
            printf("%d ",return_permute_arr[i][j]);
        }
        printf("\n");
    }
    for(int i = 0;i < factorial(n);i++){
        free(return_permute_arr[i]);
    }
    free(return_permute_arr);
    return 0; 
} 

（実行結果）

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1