【JavaScript】順列全探索のメモです。

この記事について

Atcoderで順列全探索の問題に出会い、コードを調べたので、まとめました。
仕組みについては書いておりません。いつか書けたらと思っています。

参考にした記事

@suzuki-naviさんの順列の全探索をするプログラム（競技プログラミング向け）です。

作成したコード

function Main(input){
    // ここに順列全探索をしたい配列を書く
  	P = [1, 3, 2, 4];
 
  	// 任意の配列Pをsortedに値渡しし、昇順にソート
  	sorted = P.slice();
    sorted.sort((a, b) => a - b);

    // 作成した順列を表示
    do {
        let str = "";
        for (let i = 0; i < sorted.length; i++) {
          str += sorted[i] + " ";
        }
      	console.log(str);
    } while (next_permutation(sorted));
}

// 階乗の計算
function factorial(n) {
	if(n == 0){
		return 1;
    }

	return n * factorial(n-1);
}

// 順列の生成
function next_permutation(arr) {
    const len = arr.length;
    let left = len - 2;
    while (left >= 0 && arr[left] >= arr[left+1]){
      left--;
    }  
    if (left < 0){
      return false;
    }
  
    let right = len - 1;
    while (arr[left] >= arr[right]){
      right--;
    }
    
  	const t = arr[left];
    arr[left] = arr[right]; 
    arr[right] = t; 
    left++;
    right = len - 1;
  
    while (left < right) {
        const t = arr[left]; 
      	arr[left] = arr[right]; 
      	arr[right] = t; 
        left++;
        right--;
    }
    return true;
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

実行結果

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1