順列の問題を解く

駿台の講師陣が受験生に贈ることばを集めた広告が話題になっている。

解いたらスッキリする答えが出てくる問題とはこれ。

"GAKKOU"の6文字を並べ替えてできる360個の文字列を辞書式に並べるとき、100番目の文字列を求めよ。

JavaScriptで実装する場合の素直な書き方。再帰呼び出しを使う。

function permute(arr) {
  if (arr.length === 0) return [];
  if (arr.length === 1) return [arr];

  let result = [];
  for (let i = 0; i < arr.length; i++) {
    const currentElm = arr[i];
    const remainingElms = arr.slice(0, i).concat(arr.slice(i + 1));
    const remainingElmsPermuted = permute(remainingElms);
    for (let j = 0; j < remainingElmsPermuted.length; j++) {
      const permutedElms = [currentElm].concat(remainingElmsPermuted[j]);
      result.push(permutedElms);
    }
  }
  return result;
}

const arr = "GAKKOU".split("").sort();
const permutetion = permute(arr).map((elm) => elm.join(""));
const permutetionSet = new Set(permutetion);
console.log(Array.from(permutetionSet)[99]);

もう少しすっきりさせたやつ。

function permute(arr) {
  if (arr.length <= 1) return [arr];

  let result = [];
  arr.map((head, i) =>
    permute([...arr.slice(0, i), ...arr.slice(i + 1)]).forEach((rest) =>
      result.push([head, ...rest])
    )
  );
  return result;
}

は〜ん、なるほどね。受験生の努力が報われますように。

参考にした記事:Step-by-Step Guide to Array Permutation Using Recursion in JavaScript