順列の生成
皆さんはじめまして。みやねゆうじと申します。今回がQiitaデビューです。
さて全ての要素の組み合わせを検査して最適解を求める問題がありますが、これは一般に全数検索アルゴリズムを適用して順列組み合わせを生成して解くことができます。
数学用語では「5個から3個順番に並べる全ての組み合わせ」が「順列(permutation)」で、「5個から順序に関係なく3個選ぶ組み合わせ」が「組み合わせ(combination)」です。ここでは順列のみについて示します。
この生成機能は多くの高級言語の標準ライブラリに入っています。RubyではArrayクラスにpermutationメソッドが組み込まれています。
$ irb
> [0, 1, 2].permutation.to_a
=> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
Pythonには標準ライブラリにitertoolモジュールがあります。
$ python
>>> import itertools
>>> list(itertools.permutations([0, 1, 2]))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
しかしJavaScriptにはありません。外部ライブラリを探せばどこかにありそうなのですが意外と見つかないので自作しました(ぜひ使って下さい)。
(補足) 後で検索したところPythonのitertoolsのnode.js版を見つけましたので紹介しておきます。
最初にコードと使い方を示し、その後で内容について説明します。
CoffeeScriptコード
私は現在JavaScriptは全てCoffeeScriptで記述しており、最初はCoffeeScript版を作成しました。
https://gist.github.com/higuma/9889266
# internal: generate permutation recursively
generatePermutation = (perm, pre, post, n) ->
if n > 0
for i in [0...post.length]
rest = post.slice 0
elem = rest.splice i, 1
generatePermutation perm, pre.concat(elem), rest, n - 1
else
perm.push pre
return
###
extend Array.prototype
e.g. [0, 1, 2].permutation(2)
=> [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
###
Array::permutation = (n = @.length) ->
perm = []
generatePermutation perm, [], @, n
perm
JavaScriptコード
CoffeeScriptコードのコンパイル結果を元に、手動で少しだけ手を入れて最適化したのが次のJavaScriptコードです。
https://gist.github.com/higuma/9889540
// JavaScript Array permutation generator
// (optimized from CoffeeScript output: see ArrayPermutation.coffee)
(function() {
var generatePermutation = function(perm, pre, post, n) {
var elem, i, rest, len;
if (n > 0)
for (i = 0, len = post.length; i < len; ++i) {
rest = post.slice(0);
elem = rest.splice(i, 1);
generatePermutation(perm, pre.concat(elem), rest, n - 1);
}
else
perm.push(pre);
};
/*
extend Array.prototype
e.g. [0, 1, 2].permutation(2)
=> [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
*/
Array.prototype.permutation = function(n) {
if (n == null) n = this.length;
var perm = [];
generatePermutation(perm, [], this, n);
return perm;
};
})();
使い方
これを実行(ロード)するとArrayオブジェクトにpermutationメソッドが追加され、次のようにArrayオブジェクトからコールできるようになります(rubyと同じメソッド名と書式で呼び出せます)。
[0, 1, 2].permutation()
// -> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
純粋にコードだけ利用したい人はここまで読めば十分です。自由に使って下さい。
コードの解説
以下はコードの解説です。短いですが色々なテクニックを使っています。まず一番外側の無名functionでその内部のvar変数を閉じ込め(外に出さないようにして)一回だけ実行しています(JavaScriptの常套テクニックの一つ)。
(function() {
var generatePermutation = ...
// ローカル変数として使う
})();
// ここではgeneratePermutationは未定義
心臓部はgeneratePermutation関数です(実質10行しかありませんがかなり高密度です)。まず次の標準テクニックから説明します(中級以上の方なら説明不要でしょう)。
-
post.slice(0)は配列の複製を作る: これ以外にconcatを使う方法がいくつかありますpost.concat([])[].concat(post)-
post.concat()も可能ですが昔のブラウザでは使えない可能性あり
-
rest.splice(i, 1)はi番目を抜き取り配列を縮め(破壊処理)、抜き取られた要素(この場合は1個)の配列を返す -
pre.concat(elem)は後ろにelemを連結した新しい配列を作る(非破壊)
順列組み合わせを生成するには再帰処理が必要になります。ここが本当の心臓部なので詳しく説明します。処理する配列を[0, 1, 2, 3]としてまず1レベル目に渡される引数(pre, post)がどのように推移するかを示します。
[0, 1, 2, 3]
[0], [1, 2, 3] // 引数pre, postの状態(以下同じ)
[1], [0, 2, 3]
[2], [0, 1, 3]
[3], [0, 1, 2]
これが最初の1レベルで、順番に要素をひとつ抜き出して先頭に移動し、残りの要素も再帰的に処理していきます。再帰レベル(n)を1つずつ減らしながら再帰し、0になったら最終結果(perm)に追加します。先頭が0の場合の再帰処理の流れを示します(最大再帰レベルは3で全6通り)。
[0, 1, 2, 3]
[0], [1, 2, 3]
[0, 1], [2, 3]
[0, 1, 2], [3] -> [0, 1, 2, 3]
[0, 1, 3], [2] -> [0, 1, 3, 2]
[0, 2], [1, 3]
[0, 2, 1], [3] -> [0, 2, 1, 3]
[0, 2, 3], [2] -> [0, 2, 3, 1]
[0, 3], [1, 2]
[0, 3, 1], [2] -> [0, 3, 1, 2]
[0, 3, 2], [1] -> [0, 3, 2, 1]
[1], [0, 2, 3]
...以下同様...
ここで重要になるのがメソッドが破壊(自分自身を変更する)か非破壊(新しい配列を生成する)かの違いで、spliceは破壊メソッドなので事前にslice(0)で複製を作る必要があります。
最後はこれをArray.prototypeのpermutationプロパティに登録してArrayオブジェクトに組み込みます。これはよく知られたJavaScriptのテクニックですからここでの説明は省きます。
Array.prototype.permutation = function(n) {
if (n == null) n = this.length;
var perm = [];
generatePermutation(perm, [], this, n);
return perm;
};
最後に一言。先日天気データマップというWebアプリケーションをgithubに発表しました。Googleマップ上に天気分布を表示し、各点のトレンド分布も自由自在に見られます。ぜひお試し下さい。