n 個の順列を順番に列挙するのは next_permutation() でできる。
n 個から k 個を選ぶ順列を列挙する場合、next_permutation から先頭の k 個だけを取り出せばよい。ただし、k+1 個目以後を無駄に列挙することになります。
うまく nPk を列挙できないかと思い、実装してみました。今回の実装は c++ でやってみます。
next_permutation() と同じように使いたい
n 個の順列を列挙する場合、next_permutation はこのように使います。
vector<int> ar(n);
for (int i = 0; i < n; i++) ar[i] = i;
do {
for (int i = 0; i < n; i++) {
cout << ar[i];
if (i < n - 1) cout << " ";
else cout << endl;
}
} while (next_permutation(ar.begin(), ar.end()));
next_nPk も同じ使い方ができるようにします。5P3 の場合はこんな風になります。
int maxn = 5;
int sz = 3;
vector<int> ar(maxn);
for (int i = 0; i < sz; i++) ar[i] = i;
do {
for (int i = 0; i < sz; i++) {
cout << ar[i];
if (i < n - 1) cout << " ";
else cout << endl;
}
} while (next_nPk(ar, maxn, sz);
出力はこうなります。
0 1 2
0 1 3
0 1 4
0 2 1
:
4 2 3
4 3 1
4 3 2
実装方針
1) 戻り値
引数に与えられた配列を、小さい順で一つ次の配列に更新します。更新できた場合は true を返し、更新できない場合（与えられた配列が最も大きい場合）は false を返します。
2) 値を増加させることができる桁（場所）を見つける
値を小さい順で 1 つ大きい値に増加させた時に、上の桁への桁上りが発生しない場所を、配列の最後尾から探して行きます。つまり、5P3 で考えた時（0 スタートで列挙していきます）、
- {0, 1, 3} → {0, 1, 4} の時は、最後尾（右端）は桁上りしない
- {0, 1, 4} → {0, 2, 1} の時は、右端から 2 つ目が桁上りしない
となる桁を見つけます。
この場所が見つかったら、この場所の値を1 つ大きい値に増加させます。なお、1 つ大きい値とは、その桁より左側で使われていない値のうち、次に大きい値です。
3) 1つ大きい値にした桁から後方の値を昇順に決めていく
昇順に決めていくには次のようにします。
- 1 つ大きい値に更新した桁から 1 つ右の桁に移動します
- その桁より左側で使われていない値のうち最も小さい値を割り当てます
- 桁を右に 1 つ移動します
- 2 と3 を最も右の桁に到達するまで繰り返す
ここで、その桁よりも左側で使われていない値を探すために、どの値を使っているかを管理する必要があります。
実装コード
実装方針の内容をそのままコードに落とし込んでいきます。
1) 使っている値を管理するためのブール配列を定義します。
vector<bool> used(maxn, false);
2) 与えられた配列について、使われている値を調べます。
for (int i = 0; i < sz; i++)
used[ar[i]] = true;
3) 増やしても桁上りが発生しない桁を探していきます。この時、調べる桁は値を更新する桁なので、その桁の値を未使用にしていきます。
int pos = sz - 1; // start from lowest right position
while (pos >= 0) {
int x = ar[pos]; // x = current number
used[x] = false; // unuse current number
x++; // increment
while (x < maxn && used[x]) // find unused number
x++;
if (x == maxn) { // if carry over occur
pos--; // move to next upper digit position
} else {
ar[pos] = x;
used[x] = true;
break; // end of increment of digit
}
}
上記の実装では、桁上りが発生せずに値を増やすことができる桁には、値をセットしてその値を使用済みにしています。
4) 桁上りが発生しない桁が見つからない場合は、与えられた配列を増加させることができなかったということなので false を返して終了します。
if (pos < 0) {
return false;
}
5) 見つけた場所の右側に未使用の値の中から昇順に値を割り当てていきます。
pos++; // move to next right of updated position
while (pos < sz) {
int x = 0; // find smallest unused number
while (used[x]) x++;
ar[pos] = x; // set smallest unused number
used[x] = true;
pos++; // move to next lower digit position
}
以上を関数 next_nPk() の中に実装します
bool next_nPk(vector<int> &ar, int maxn, int sz) {
// 1) 使っている値を管理するためのブール配列を定義
// 2) 与えられた配列について、使われている値を調べる
// 3) 増やしても桁上りが発生しない場所を探す
// 4) 配列が更新できなければ false を返して終了する
// 5) 見つけた場所の右側に未使用の値の中から昇順に値を割り当てていく
return true;
}