調べてもまとまったものがないので。どちらも辞書順で並ぶ。C言語で実装する。
C++のnext_permutationのような実装
[1,2,4,3]の場合、2の後は逆順なので、2が繰り上がって3になる([1,3,*,*])。後は、*の部分の数字を昇順の数列で埋めれば良い。
ステップとしては、
- 後ろから見ていって、逆順の部分列でなくなる境界のkをメモる
- x>=arr[k]、つまり、lower boundの場所(i)を探す。Nが小さいので線形探索で実装した。
- 繰り上がりの処理。つまりi番目とk番目の要素をswap。0番目からk-1番目まではそのまま。k+1番目から以降は逆順で並んでいる(順列は数が重複してないので、2の方法で入れ替えても逆順の性質は保たれる) ので、これを昇順にreversedする。
reversedは計算量O(N)であんまり嬉しくないが、N自体が小さいので許容することにする。(どうしても許容できないときは双方向リストなどを使って、向きまで考慮するとO(1)でreversedが実装できるはず)
#ifndef PERM_SIZE #define PERM_SIZE 30 #endif void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } // assume that size is smaller.. void reversed(int *a, int size) { static int b[PERM_SIZE]; memcpy(b, a, sizeof(int)*size); int i; for(i = 0; i < size; i++) { a[i] = b[size-1-i]; } } // in-place(C++ like function) // see also https://cpprefjp.github.io/reference/algorithm/next_permutation.html int next_permutation(int *arr, int size) { int i, k; if(!size || size==1) return 0; for(k = size-2; k >= 0; k--) { if(arr[k+1] > arr[k]) break; } if(k < 0) { // reversed reversed(arr, size); return 0; } for(i = size-1; i >= 0; i--) { if(arr[i] < arr[k]) continue; break; } swap(&arr[i], &arr[k]); reversed(&arr[k+1], size-1-k); return 1; }
例) https://atcoder.jp/contests/abc054/submissions/12291613
例えば、ある1~Nの昇順とは限らない順列があって、「この順列を起点にして、K番目の順列を出力しなさい」的な問題でピッタリ使えそう。
再帰関数を使う
p, usedをglobalとする。pを盤面を保存した配列とみなすとよい。usedは順列の数字を使ったかどうかを記録する(１度しか使えないので、要記録)
if(pos == size)に入ったら、順列が生成された状態になっているので、所要の処理を施して、perm関数を抜ける。
蟻本の初級編のpermutationの実装例はこうなっている。
char used[VMAX]; int p[VMAX+1]; void perm(int *arr, int pos, int size, int *ans) { int i; if(pos == size) { int flag = 1; #ifdef DEBUG for(i = 0; i < size; i++) { printf("%d ", arr[p[i]]); } putchar('\n'); #endif // do something and early return; } for(i = 0; i < size; i++) { if(used[i]) continue; used[i] = 1; p[pos] = i; perm(arr, pos+1, size, ans); used[i] = 0; } return; }
関数ポインタを引数にしてもよいが、めんどくさいのでperm関数の中に直接処理を書いてみたのが例のリンク。
