[javascript]ジェネレータによる配列の順列の列挙

動作環境

windows10 x64

> node --version
v9.5.0

目標

Array.prototypeに順列を列挙するジェネレータ関数を定義したい．
RubyのArray#permutationと同じ使い方．

2018/01/11追記：良い書き方ではありません．追記を参照してください．

Array.prototype.permutation = function*(){
    // ここになにか書く
}

for (let e of [1,2,4]){
    console.log(e);
}

期待する実行結果の一例¹

[ 1, 2, 4 ]
[ 1, 4, 2 ]
[ 2, 1, 4 ]
[ 2, 4, 1 ]
[ 4, 1, 2 ]
[ 4, 2, 1 ]

動機

順列列挙プログラムを書きたい．

配列を返す実装はすべての順列をメモリに保管するため，階乗オーダーのメモリ空間を消費する．イテレータ・ジェネレータ関数を用いた実装ならば，1つ生成する度に返すので，使い方によっては多項式オーダのメモリ空間で済む．

普段ジェネレータを書かないので，再帰中のyieldにはまってしまった．

ジェネレータ関数とは

developer.mozilla.org の説明が分かりやすいので引用．

ジェネレーター関数は、 function* 構文を使用して記述されます。 最初に呼び出されると、ジェネレータ関数はコードを実行せず、ジェネレーターと呼ばれるある種のイテレーターを返します。 ジェネレーターの next メソッドを呼び出すことによって値が消費されると、ジェネレーター関数は yield キーワードを検出するまで実行します。

ジェネレータ関数の利用例

基本

for of で取り出せるような「イテレータのようなもの」が書ける．
yield の挙動は，関数内から見ると中断しているかのように見える．

function* foo(){
    yield 2;
    yield 3;
    yield 5;
    return;
}

for (let e of foo()){
    console.log(e);
}

次のような，関数barから直接yieldする曲芸は出来ない．

function* foo(){
    function bar(x){
        yield x+x;
        yield x*x;
    }
    bar(1);
    bar(2);
}

しかし，barをジェネレータ関数にすれば，barがyieldした値をfooが受け取って，fooがその受け取った値をyieldすることで，先程の曲芸が実現できる．
バケツリレーのようなイメージ．

function* foo(){
    function* bar(x){
        yield x+x;
        yield x*x;
    }
    for (let y of bar(1)) yield y;
    for (let y of bar(2)) yield y;
}

2018/01/11 追記：yield* 構文を用いると簡潔かつ高速なコードが書ける．

function* foo(){
    function* bar(x){
        yield x+x;
        yield x*x;
    }
    yield* bar(1);
    yield* bar(2);
}

再帰の中でジェネレータを使う

function* foo(n){
    if (n <= 0) return;
    for (let x of foo(n-1)) yield x;
    yield n;
    for (let x of foo(n-1)) yield x;
    return;
}

console.log(Array.from(foo(3))); // [ 1, 2, 1, 3, 1, 2, 1 ]

ジェネレータによる配列の順列の列挙

順列を表示するコード(ジェネレータを使わない)

再帰関数を使って，すべての順列を出力するコードはこちら．
(アルゴリズムについては解説しません．)

const arr = [1,2,4];

const n = arr.length;
function recursivef(p){
    if (p.length == n){
        console.log(p.map(i => arr[i]));
        return;
    }
    for (let i = 0; i < n; ++i){
        if (p.includes(i)) continue;
        p.push(i);
        recursivef(p);
        p.pop();
    }
}
recursivef([]);

成果物

再帰呼出しをfor of,yieldに変えて，returnをyieldに書き換えれば，順列を列挙するジェネレータ関数が完成する．

Array.prototype.permutation = function*() {
    if (this.length <= 0) return;
    const n = this.length;
    const this_ = this;
    function* recursivef(p) {
        if (p.length == n){
            yield p.map(i => this_[i]);
            return ;
        }
        for (let i = 0; i < n; ++i){
            if (p.includes(i)) continue;
            p.push(i);
            for (let r of recursivef(p)) yield r;
            p.pop();
        }
    }
    for (let r of recursivef([])) yield r;
}

おまけ

仲間たち

せっかくなので，repeated_permutation，combination，repeated_combinationを実装．

Array.prototype.repeated_permutation = function*(k) {
    if (this.length <= 0) return;
    const n = this.length;
    const this_ = this;
    function* recursivef(p) {
        if (p.length == k){
            yield p.map(i => this_[i]);
            return ;
        }
        for (let i = 0; i < n; ++i){
            p.push(i);
            for (let r of recursivef(p)) yield r;
            p.pop();
        }
    }
    for (let r of recursivef([])) yield r;
}

Array.prototype.combination = function*(k) {
    if (this.length <= 0 || (this.length < k)) return;
    const n = this.length;
    const this_ = this;
    function* dfs(c, idx) {
        if (n - idx < k - c.length) return;
        if (idx == n){
            if (c.length == k)
                yield c.map(i => this_[i]);
            return ;
        }
        if (k > c.length) {
            c.push(idx);
            for (let r of dfs(c, idx+1)) yield r;
            c.pop();
        }
        for (let r of dfs(c, idx+1)) yield r;
    }
    for (let r of dfs([], 0)) yield r;
}

Array.prototype.repeated_combination = function*(k) {
    if (this.length <= 0 || (this.length < k)) return;
    const n = this.length;
    const this_ = this;
    function* dfs(c, idx) {
        if (c.length == k) {
            yield c.map(i => this_[i]);
            return ;
        }
        if (idx == n) return;
        if (k > c.length) {
            c.push(idx);
            for (let r of dfs(c, idx)) yield r;
            c.pop();
        }
        for (let r of dfs(c, idx+1)) yield r;
    }
    for (let r of dfs([], 0)) yield r;
}

再帰を使わずに順列を列挙する

再帰を使わずに順列を列挙する方法がある．C++STLのstd::next_permutation()など．
wikipediaに実装方法が掲載されているので，これを実装する．

Array.prototype.permutation = function*() {
    if (this.length <= 0) return;
    const n = this.length;
    const perm = new Array(n).fill(0).map((e,i) => i);
    
    yield this;
    
    let k = n-2, l;
    while(k !== null) {
        // step 2
        l = -1;
        for (let i = k+1; i < n; ++i)
            if (perm[k] < perm[i])
                l = i;
        // step 3
        { let t = perm[k]; perm[k] = perm[l]; perm[l] = t; }
        // step 4
        for (let i = k+1, j = n-1; i < j; ++i, --j)
            { let t = perm[i]; perm[i] = perm[j]; perm[j] = t; }
        // yield
        yield perm.map(i => this[i]);
        // step 1
        k = null;
        for (let i = 0; i < n-1; ++i)
            if (perm[i] < perm[i+1])
                k = i;
    }
}

追記

Array.prototypeについて

ビルドインオブジェクトの拡張は良くない，という指摘を頂きましたので，調べました．

例えば，Google JavaScript Style Guide から引用します．

Modifying builtins like Object.prototype and Array.prototype are strictly forbidden. Modifying other builtins like Function.prototype is less dangerous but still leads to hard to debug issues in production and should be avoided.

strictly forbidden です．

mozilla web docs の Object.prototype.proto の警告にもあるように，Array等のビルドインオブジェクトは既にjavascriptエンジンによって最適化されており，拡張してしまうことによって，その最適化を妨げ，ソースコード中のあらゆるArrayのインスタンスの操作を低速化させてしまうようです．

1. すべての順列を列挙したいだけなので，異なる順序で出力されても良い． ↩