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;
    }
  }
}

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

仕様

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

[...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, ...]について、次のように交換して縦線を進めることで、再帰的に順列を生成、列挙できる。

[... | 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;
    }
  }
}