next_permutationをJSで実装する

next_permutationをJSで実装する

2021-07-225 min read

目次

  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]

Tags
javascript(109)
linux(54)
node.js(53)
amazon%20aws(47)
typescript(44)
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0(36)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86(30)
html5(29)
php(24)
centos(24)
python(22)
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0(21)
mac(21)
mysql(20)
canvas(19)
opencv(17)
%E9%9B%91%E8%AB%87(16)
docker(16)
wordpress(15)
atcoder(14)
apache(12)
%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92(12)
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9(12)
amazon%20s3(12)
red%20hat(12)
prisma(12)
ubuntu(11)
github(10)
git(10)
vue.js(10)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86100%E6%9C%AC%E3%83%8E%E3%83%83%E3%82%AF(10)
mariadb(10)
react(9)
aws%20cdk(9)
css3(8)
%E5%8F%AF%E8%A6%96%E5%8C%96(8)
%E5%B0%8F%E3%83%8D%E3%82%BF(8)
nestjs(8)
amazon%20lightsail(7)
next.js(7)
%E3%83%96%E3%83%AD%E3%82%B0(6)
cms(6)
oracle(6)
perl(6)
gitlab(6)
iam(5)
amazon%20ec2(5)
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93(5)
aws%20amplify(5)
curl(4)
Author
githubzennqiita
ただの備忘録です。

※外部送信に関する公表事項