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

# 動作環境

windows10 x64

```
> node --version
v9.5.0
```

# 目標

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

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

```javascript

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

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

期待する実行結果の一例[^1]

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

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

# 動機

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

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

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

# ジェネレータ関数とは

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

https://developer.mozilla.org/ja/docs/Web/JavaScript/Guide/Iterators_and_Generators

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

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

## 基本

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

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

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

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

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

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

```javascript
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*` 構文を用いると簡潔かつ高速なコードが書ける．

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

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

```javascript
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 ]
```


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

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

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

```javascript
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`に書き換えれば，順列を列挙するジェネレータ関数が完成する．

```javascript
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を実装．

```javascript
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に実装方法が掲載されているので，これを実装する．

https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

```javascript
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](https://google.github.io/styleguide/javascriptguide.xml?showone=Modifying_prototypes_of_builtin_objects#Modifying_prototypes_of_builtin_objects) から引用します．

> 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](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/proto) の警告にもあるように，Array等のビルドインオブジェクトは既にjavascriptエンジンによって最適化されており，拡張してしまうことによって，その最適化を妨げ，ソースコード中のあらゆるArrayのインスタンスの操作を低速化させてしまうようです．