PHP で next permutation を作る
目次：
Permutation （順列）とは
グレッグ・イーガンという作家の作品に、 ‘Permutation City’（順列都市）という難しい SF 小説がありますが、順列自体は、難しい考え方ではありません。
小・中学校の算数や数学で、「場合の数」と呼ばれていたものの1つで、たとえば、以下のような問題を解いたことがあるのではないでしょうか？
Aさん、Bさん、Cさんの3人が、一列に並びます。
何種類の並び順がありますか？
- A:B:C
- A:C:B
- B:A:C
- B:C:A
- C:A:B
- C:B:A
よって 6種類
公式を覚えている方の場合、 3! で6種類とすぐに求まったかもしれません。
順列とは、区別できるものを並べ替えて、その並び順を数え上げる時などに使われる概念です。
Next Permutation とは
C++ という言語に、 std::next_permutation() というメソッドがあります。
順列の組み合わせを、辞書順（アルファベット順）に並べたとき、ある順列の次の順列を高速に求めることができるメソッドです。
今回は、これと似たような関数を PHP で実装してみます。
PHP での実装
<?php
function next_permutation(array $arr, int $n): Generator {
while (true) {
yield $arr;
$target = -1;
for ($i = $n - 2; $i >= 0; $i--) {
if ($arr[$i] < $arr[$i + 1]) {
$target = $i;
break;
}
}
if ($target == -1) {
return;
}
for ($i = 0; $target + 1 + $i < $n - 1 - $i; $i++) {
$temp = $arr[$target + 1 + $i];
$arr[$target + 1 + $i] = $arr[$n - 1 - $i];
$arr[$n - 1 - $i] = $temp;
}
for ($j = $target + 1; $j < $n; $j++) {
if ($arr[$j] > $arr[$target]) {
$temp = $arr[$j];
$arr[$j] = $arr[$target];
$arr[$target] = $temp;
break;
}
}
}
}
// 使い方
$arr = [1, 2, 3, 4, 5, 6, 7, 8];
$n = 8;
$ans = 0;
foreach (next_permutation($arr, $n) as $perm) {
$ans += 1;
}
var_dump($ans === (int) gmp_fact(8));
実装上のポイント
ジェネレータを使う
まず、すべて区別される順列の組み合わせ数は、 N! となり、数字が大きくなれば、爆発的に大きな数になってしまいます。
よって、関数はジェネレータとして作成し、次の順列が判明するごとに yield で返すことで、メモリを節約できます。
次の順列を見つけ出すロジック
手順は、大きく3つに分かれます。
- 後ろから順に見ていき、降順になっていないものを
$targetとして取り出す $target以下の降順部分を逆順にひっくり返す$targetと、それより大きい最初の数を入れ替える
このロジックは、私が思いついたのではなく、ネット上の解説から作成しました。
どうしてこの手順で可能なのかは、私にもうまく証明できません。
しかし、実際にメモなどに書きつけて考えてみると、確かにうまくいくことが分かります。
1, 3, 5, 4, 2
| <= target は、3
1, 3, 2, 4, 5 // 3 より後をひっくり返す
1, 4, 2, 3, 5 // 3 より大きい4と入れ替える
まとめ
もちろん、 C++ の std::next_permutation に処理速度で勝てるわけは無いのですが、とはいえ、 PHP で必要な場面では、それほど問題なく使えます。
もしさらに高速化したい場合は、関数内部で、下3桁か4桁程度を事前計算してしまい、問答無用で yield で返してしまうという技もあります。（ただし、これが通用するのは、要素すべてが区別できる場合です）
最後までお読みいただき、ありがとうございました。
何かお気づきの点がありましたら、 お問い合わせ ください。