next_permutationをJSで実装する

目次

1. 概要
2. ソース
3. 使い方
4. 参考

概要

C++で提供されている順列を生成する next_permutation のJS実装です。

ソース

順列が存在する場合はtrueを返し、そうでなければfalseを返します。

function next_permutation(arr) {
  for (let i = arr.length - 2; i >= 0; i--) {
    if (arr[i] < arr[i + 1]) {
      for (let j = arr.length - 1; j > i; j--) {
        if (arr[j] > arr[i]) {
          [arr[i], arr[j]] = [arr[j], arr[i]];
          const len = (arr.length - (i + 1)) >> 1;
          for (let k = 0; k < len; k++) {
            [arr[i + 1 + k], arr[arr.length - 1 - k]] = [
              arr[arr.length - 1 - k],
              arr[i + 1 + k],
            ];
          }
          return true;
        }
      }
    }
  }
  return false;
}

使い方

let row = Array.from(Array(3).keys());
do {
  console.log(row);
} while (next_permutation(row));
// 0,1,2
// 0,2,1
// 1,0,2
// 1,2,0
// 2,0,1
// 2,1,0

参考

順列の全探索をするプログラム（競技プログラミング向け）

HunterLarco/next_permutation.js - Gist

【C++】next_permutation（順列列挙）

提出 #23921358 - 競プロ典型 90 問

順列・組み合わせ のサンプルコード JS [permutation] [combination]