JavaScriptで順列列挙（非再起ジェネレータ版）

タイトルの通り、あまり一般的でない順列列挙の実装を考えてみたので、そのメモ。
コメントなしだと下記の通り30行程度の実装になる。

```コメントなし.js
function* genPermutation (n, array) {
  if (n < 0 || n > array.length) {
    return;
  }

  const index = [...Array(array.length).keys()];
  let left = 0;
  const right = [...Array(n + 1).keys()];

  const swapIndex = () => {
    const temp = index[left];
    index[left] = index[right[left]];
    index[right[left]] = temp;
  };
  
  while (left >= 0) {
    if (left === n) {
      yield index.slice(0, n).map(i => array[i]);
    }

    if (left === n || right[left] === array.length) {
      left--;
      swapIndex();
      right[left]++;
    } else {
      swapIndex();
      left++;
      right[left] = left;
    }
  }
}
```

自分で書いといてなんだけど、これで順列が列挙されるって言われても違和感しかない。


# 仕様

第一引数に列挙する順列の長さ、第二引数に順列に使用する要素が格納された配列を指定する。引数に応じて順次、順列が生成される。
なお、引数に指定する配列の要素には重複がないことを前提とする。
また、指定された順列の長さが負であったり、配列の長さを超える場合は何も生成しない。
（注：辞書順での列挙は仕様に含めないものとする。）

```.js
[...genPermutation(0, [1,2,3])].map(p => p.join()); // [""]
[...genPermutation(1, [1,2,3])].map(p => p.join()); // ["1", "2", "3"]
[...genPermutation(2, [1,2,3])].map(p => p.join()); // ["1,2", "1,3", "2,1", "2,3", "3,2", "3,1"]
[...genPermutation(3, [1,2,3])].map(p => p.join()); // ["1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,2,1", "3,1,2"]

[...genPermutation(-1, [1,2,3])].map(p => p.join()); // []
[...genPermutation(4, [1,2,3])].map(p => p.join()); // []
```


# 実装の背景となる考え方

順列列挙なので再起的な考えが基本になる。あえて文章で述べれば、次のような考えが背景になっている。

先頭から長さ`left`までが固定された順列を考えると、その固定された`0 ～ left - 1`番目の要素を除いた、残りの要素すべてが`left`番目の要素になり得る。
そこで、`left`番目の要素を順次`left`以降の要素(`right`番目の要素)と交換し、先頭から長さ`left + 1`までが固定された順列と考えることで、再帰的に順列を生成、列挙できる。

例えば、縦線`|`までが、固定された順列であるような配列 `[... | a, b, c, ...]`について、次のように交換して縦線を進めることで、再帰的に順列を生成、列挙できる。

```.js
[... | a, b, c, ...] // 縦線`|`までが固定された順列と考えたとき、
[..., a | b, c, ...] // 縦線をひとつ進め、再帰的に縦線を進める
[..., b | a, c, ...] // 上記の再起が完了したら、a と b を交換し、再帰的に縦線を進める
[..., c | b, a, ...] // 上記の再起が完了したら、a と c を交換し、再帰的に縦線を進める
// 以下略...
```

上記の考えを単純に再帰関数として実装すると、次のようになる。

```再帰関数による実装.js
const rec = (n, array, left = 0, result = []) => {
  if (left === n) {
    result.push(array.slice(0, n));
    return result;
  }
  
  for (let right = left; right < array.length; right++) {
    swap(left, right, array);
    rec(n, array, left + 1, result);
    swap(left, right, array);
  }
  
  return result;
}

const swap = (i, j, array) => {
  const temp = array[i];
  array[i] = array[j];
  array[j] = temp;
};
```

このコードをジェネレータ関数に変換し、非再起化すれば、最初のコードが得られる。


# コメント付きで再掲

ここまでの話を理解できれば、コメント付きの実装が理解できる・・・はず？

```コメント付き.js
function* genPermutation (n, array) {
  // 無効な引数には何も返さない
  if (n < 0 || n > array.length) {
    return;
  }

  // 順列を生成する上での交換位置の管理
  // （交換位置（左）の値ごとに、
  //   交換位置（右）の値を管理する必要がある）
  const index = [...Array(array.length).keys()];
  let left = 0;
  const right = [...Array(n + 1).keys()];

  // 現在の交換位置で添字を交換するための関数
  const swapIndex = () => {
    const temp = index[left];
    index[left] = index[right[left]];
    index[right[left]] = temp;
  };
  
  // 交換位置（左）が正である限り、
  // 未生成の順列が存在する
  while (left >= 0) {
    // 交換位置（左）までの順列は生成済みなので、
    // 交換位置（左）と n と等しければ、
    // 長さ n の生成済みの順列を返す
    if (left === n) {
      yield index.slice(0, n).map(i => array[i]);
    }

    if (left === n || right[left] === array.length) {
      // 長さ n を超えて順列を生成しても意味がなく、
      // また、交換位置（右）が配列の長さ以上では交換ができないので、
      // 交換位置（左）をひとつ戻して、
      // 交換していた要素を再交換でもとの位置に戻したあとに、
      // 対応する交換位置（右）をひとつ進める
      left--;
      swapIndex();
      right[left]++;
    } else {
      // 交換して
      // 交換位置（左）をひとつ進め、
      // 対応する交換位置（右）として同じ位置を指定する
      swapIndex();
      left++;
      right[left] = left;
    }
  }
}
```