paizaラーニング レベルアップ問題集 巡回セールスマン問題メニュー JavaScript 順列全列挙

順列全列挙 (paizaランク B 相当)

解答例(C++の場合参考)

JavaScriptには順列全列挙のライブラリが用意されていないので、
自分で再帰関数を実装します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//関数print定義:配列pを半角スペースで出力
function print(n, p) {
  let cout = "";
  for (let i = 0; i < n; i++) {
    cout += p[i];
    if (i != n - 1) {
      cout += " ";
    }
  }
  console.log(cout);
}

//再帰関数permutation定義：空配列pに1からnまでの全順列を作る。
function permutations(n, p) {
  //pの長さがnになったら１行の順列が完成、出力する。
  if (p.length == n) {
    print(n, p);
    return;//スタックの一番上に残った関数へ戻る
  }
  //順列つくる
  for (let i = 1; i <= n; i++) {
    //配列pに要素iが存在するなら次のiへ
    if (p.indexOf(i) != -1) {
      continue;
    }
    //配列pに要素iがまだないなら
    p.push(i);//iを追加
    permutations(n, p);//さらに関数実行、スタック積む
    p.pop();//１つの関数実行完了して戻ってきて末尾削除
  }
}

//メイン
const n = Number(lines[0]);
const p = [];
permutations(n, p);

解答例

関数printをconsole.log(p.join(" "));にした。
includesを使った。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//順列つくる関数
function permutations(n, p) {
  //長さnなら出力
  if (p.length == n) {
    console.log(p.join(" "));
    return;//関数完了、スタックの一番上に残った関数へ戻る
  }
  //長さがn未満なら、順列つくる
  for (let i = 1; i <= n; i++) {
    //pにiがあればスキップ
    if (p.includes(i)) {
      continue;
    }
    //pにiがなければ
    p.push(i);
    permutations(n, p);//さらに関数実行、スタック積む
    p.pop();//１つの関数実行完了して、スタックの一番上の関数に戻ってきて末尾削除
  }
  //関数完了
}
//メイン
const n = Number(lines[0]);
const p = [];
permutations(n, p);

再帰関数について

再帰関数の理解のためには、pがどうなっているか、forのiはいくつか、スタックの積み上げ、のイメージを保ちながら、再帰関数の中を辿っていくと、よいかもしれません。

例:n=3のとき、以下のように動きます。スタック[x]はスタックのしたから何番目かを表す。
スタック[0]
p=[]でforのi=1はまだpに1がないのでpush(1)、p=[1]
p=[1]でスタック[0]に積んで、次の関数実行
スタック[1]
p=[1]でforのi=1はすでにpに1があるのでcontinue
p=[1]でforのi=2はまだpに2がないのでpush(2)、p=[1,2]
p=[1,2]でスタック[1]に積んで、次の関数実行
スタック[2]
p=[1,2]でforのi=1はすでにpに1があるのでcontinue
p=[1,2]でforのi=2はすでにpに2があるのでcontinue
p=[1,2]でforのi=3はまだpに3がないのでpush(3)、p=[1,2,3]
p=[1,2,3]でスタック[2]に積んで、次の関数実行
スタック[3]
p=[1,2,3]で長さが3なので出力。関数完了。一番上のスタック[2]に戻る。
スタック[2]
p=[1,2,3]でpop()してp=[1,2]、i=3なのでforループ終了。関数完了。一番上のスタック[1]に戻る。
スタック[1]
p=[1,2]でpop()してp=[1]、i=2なので、次のiへ
p=[1]でforのi=3はまだpにないのでpush(3)でp=[1,3]
p=[1,3]でスタック[1]に積んで、次の関数実行
スタック[2]
p=[1,3]でfor i=1はpにあるのでcontinue
p=[1,3]でfor i=2はpにないのでpush(2)でp=[1,3,2]
p=[1,3,2]でスタック[2]に積んで、次の関数実行
スタック[3]
p=[1,3,2]は長さ3なので出力、関数完了、一番上のスタック[2]に戻る
スタック[2]
p=[1,3,2]でpop()してp=[1,3]、for i=2なので次のループへ。
p=[1,3]、for i=3,pに3あり、continue、ループ終了。関数完了。一番上のスタック[1]に戻る。
スタック[1]
p=[1,3]、pop()でp=[1]、for i=3なのでループ終了。関数完了。一番上のスタック[0]に戻る。
スタック[0]
p=[1],pop()でp=[]。for i=1なので、次のi=２へ
p=[],for i=2,pに2ないので、push(2)でp=[2]
p=[2]でスタック[0]に積んで、次の関数実行。
。。。
これを同様にして、最後まで実行します。