順列 - Retro-gaming and so on

まず最初に言っておこう。

「順列」は数学だが、「あるリストの要素を使ったリストを順列として生成せよ」は数学ではない。これは単なるプログラミングの再帰を用いたアルゴリズムだ。

何故かと言うと、「ある要素の組から適当な個数を選んだ順列の総数」を求めるのは数学で出来るが、実際どんな組をでっち上げるのか、と言うのは人手を要する。

「地道な作業」は数学じゃあないんだ。

そしてここで重大な事実が発覚する。

それは、

「人がメンド臭い、って思う計算は実はコンピュータも苦手だ」

と言う事実を。

コンピュータは一瞬で計算を終了する事が多いんで、あまり気づかれないが、実際問題、「人が手計算してもそこそこ出来る事」を高速で行ってるから「計算が得意」だと思われてる。

しかし、例えば高校数学で習った行列を考えてみよう。これは単純な計算なんだけど人は得意じゃない。実はこういう「単純でも構造上メンド臭い計算」は実はコンピュータも苦手で、行列演算なんつーのはコンピュータの最も苦手とする計算なんだ。

最近のGPU(グラフィック演算装置)は、元々、何に特化して作ってるのか、と言うとこの行列演算に対して、だ。CPUが行列演算が苦手なんで、そのテの計算が入ってきた時、GPUが処理するようになっている。これが無いと、3次元グラフィックスの演算がままならない。

その「ままならない」のをコンピュータ登場時からずーっと続けてきたわけだな。90年代のグラフィックワークステーションやら、プレイステーションの何が優れていたのか、と言うと、この「コンピュータが苦手な」行列演算の為の演算ユニットを持ってる部分だったんだ。

閑話休題。

いずれにせよ、「人が苦手な計算はコンピュータも苦手だ」と言うのは覚えておいて良いと思う。この「どんな数値の組が順列の解として現れるか」数え上げる、なんつーのは人も苦手だしコンピュータも苦手なんだ。

もう一回繰り返すけど、「順列の組を実際に返す」のは数学じゃあない。ある意味再帰の宿題的なブツで、以前言った「再帰は殆ど簡単なんだけど、一部分だけはやたら難しい」と言うその「難しい」部分に相当する。出来ればやりたくない部分だ(笑)。

考え方としては次のようになる。

例えば [1, 2, 3] から3つ取った順列を考えよう。最初にそのまま解を書く。

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

と6つある。

繰り返すが[1, 2, 3]から3つ取る順列の「総数が6になる」と分かるのは数学だが、実際「どんな組があるのか」並べまくるのは数学でも何でもない。単なる「メンドい手作業」だ。

ここでちょっと「先頭が1」の組を見てみよう。次の2つだな。

[1, 2, 3]
[1, 3, 2]

これは言い換えると「[2, 3]が形成する順列の先頭に1を加えたモノ」、となる。

何故なら[2, 3]から2個取る順列は次の2つだからだ。

[2, 3]
[3, 2]

まぁ、当たり前だよな。

もうちょっと文章化してみよう。先頭が1の順列のパターンとは何か。それは

「[1, 2, 3]から1を除いて生成した順列それぞれの先頭に1を加えたモノ」

だ。

先頭が2の順列のパターンは、

「[1, 2, 3]から2を除いて生成した順列それぞれの先頭に2を加えたモノ」

になる。先頭が3の場合も同じだ。

もっと一般化すると、

「[1, 2, 3]からxを除いて生成した順列それぞれの先頭にxを加えたモノ」

で順列が生成出来る、と言う事だ。これが順列を実際に返すアルゴリズムの心臓部になる。

Racketで言うと、関数permは与えられたリストxsに対して

(map (lambda (x)
　(map (lambda (ys)
　　　　(cons x ys)) (perm (remove x xs) (- r 1))))
　　　　xs)

そのものか、あるいはそれに近いカタチのコードが「心臓部」と言う事になる。

なお、いずれにせよ、解の形式としてはリストのリストが返らなければならない事が1つ。従ってベースケース(再帰の停止条件)は空リストのリスト、っちゅう事になる。

上の理屈をそのままプログラムとして書き下すと次のようになるだろう。

(define (perm xs r)
　(cond ((zero? r) '(()))
　((< (length xs) r) '(()))
　(else (append-map (lambda (x)
　　　　　　　　　　(map (lambda (ys)
　　　　　　　　　　　　　(cons x ys)) (perm (remove x xs) (- r 1))))
　　　　　　　　　　xs))))

外側が append-map になってるのは、mapのままだとcons cons cons ...になっちまうから、だ。適度にリストとしてまとめる為に append-map を使用している。

しかし、宿題としてはいいが、この関数を実用的に使おうとするとちと戴けない。

そもそも、これは末尾再帰じゃないし、高負荷の再帰関数だ。あまりにも与えるリストが長ければ、メモリを食いつぶしてしまうくらいマズい関数だろう。

Pythonにもこの順列計算用の関数が用意されている。さすがPython、Battery Includedなだけあって、「どう考えても実装するのがクソメンド臭い」関数をキチンと提供している。

でも、順列を生成して返す以上、基本再帰的処理は避けられない。しかも今まで見た通り、高負荷であるのは間違いないんだ。そんな関数は実用的なんだろうか。Pythonでは一体どうしてるんだろう。

Pythonではitertoolsと言うライブラリで、そのままpermutationsと言う関数が用意されている。

>>> from itertools import permutations as perm

使い方は例えば次のようにする。

>>> p = perm([5, 78, 9, 0, 12, 3, 54, 77, 54], 6)

何で変数に代入してるのか、と言う理由は次のようなモノだ。

>>> p
<itertools.permutations object at 0x7f21d4a38860>

そう、itertools.permutationsはイテラブルを返す関数、つまりイテレータなんだ。

そうすると、例えば [5, 78, 9, 0, 12, 3, 54, 77, 54] から6個選ぶ順列全部、とか、マトモに返せば負荷がかかってしゃーないトコを、一部分だけ「その時々」演算して返すだけなら負荷はかからない。

>>> p.__next__()
(5, 78, 9, 0, 12, 3)
>>> p.__next__()
(5, 78, 9, 0, 12, 54)
>>> p.__next__()
(5, 78, 9, 0, 12, 77)
>>> p.__next__()
(5, 78, 9, 0, 12, 54)
>>> p.__next__()
(5, 78, 9, 0, 3, 12)
>>> p.__next__()
(5, 78, 9, 0, 3, 54)
>>> p.__next__()
(5, 78, 9, 0, 3, 77)
>>>

そう、考え方は遅延評価なんだ。つまり、順列生成関数を実用的に使いたければ、伝家の宝刀、遅延評価の出番、となる。

RacketでもSRFI-41をrequireしてストリーム(遅延リスト)を返すように改造しよう。

(define (stream-perm xs r)
　(cond ((zero? r) (stream stream-null))
　　　　((< (stream-length xs) r) (stream stream-null))
　　　　(else (stream-concat
　　　　　　　(stream-map
　　　　　　　　(lambda (x)
　　　　　　　　　(stream-map
　　　　　　　　　　(lambda (ys)
　　　　　　　　　　　(stream-cons x ys))
　　　　　　　　　　(stream-perm
　　　　　　　　　　　(stream-filter
　　　　　　　　　　　　(lambda (z)
　　　　　　　　　　　　　((compose not =) x z))
　　　　　　　　　　　　xs) (- r 1))))
　　　　　　　　xs)))))

基本的に使われてる関数を全部地道にSRFI-41の提供関数に置き換えていけば済む筈だ。

注意点としては

原版では flatten としてappend-mapを使用したが、SRFI-41にはappend-stream-mapなんつー関数は存在しない。フツーに書けばapply stream-appendしたいトコだが、applyは第二引数以降はリストしか取れなく、ストリームは取れない。こういう場合は、stream-concatを使う。stream-concatはストリームを要素とするストリームの中身を全部結合し、まさしくapply stream-append したい、と思ったトコを解決する。
stream-removeと言う便利関数もないのでstream-filterを使って原作のremoveにあたる動作を定義する。

の二点程度があるだけ、だ。あとは殆ど原作と同じだ、って事が分かるだろう。

これなら、例えば、

> (define s (stream-perm (stream 5 78 9 0 12 3 54 77 54) 6))
> s
#<stream>
>

と「題意に従って順列の解となったストリーム」と言うデータ型が得られる。

> (stream-length s)
35280
>

ここだけはちと計算に時間がかかるが、許容範囲だろう。

使い方は、

> (stream->list (stream-ref s 0))
'(5 78 9 0 12 3)
> (stream->list (stream-ref s 1))
'(5 78 9 0 12 54)
> (stream->list (stream-ref s 2))
'(5 78 9 0 12 77)
> (stream->list (stream-ref s 3))
'(5 78 9 0 12 54)
> (stream->list (stream-ref s 4))
'(5 78 9 0 3 12)
> (stream->list (stream-ref s 5))
'(5 78 9 0 3 54)
> (stream->list (stream-ref s 6))
'(5 78 9 0 3 77)
>