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

目次

1. 概要
2. 順列---permutation
3. 組み合わせ---combination

概要

順列(permutation) と 組み合わせ(combination) のサンプルコードをJavaScriptで実装してみました。

順列 - permutation

サンプルコード

const permutation = (nums, k) => {
  let ans = [];
  if (nums.length < k) {
    return [];
  }
  if (k === 1) {
    for (let i = 0; i < nums.length; i++) {
      ans[i] = [nums[i]];
    }
  } else {
    for (let i = 0; i < nums.length; i++) {
      let parts = nums.slice(0);
      parts.splice(i, 1)[0];
      let row = permutation(parts, k - 1);
      for (let j = 0; j < row.length; j++) {
        ans.push([nums[i]].concat(row[j]));
      }
    }
  }
  return ans;
};

Usage

let arr = permutation(['a', 'b', 'c'], 2);
console.log(JSON.stringify(arr));
// [["a","b"],["a","c"],["b","a"],["b","c"],["c","a"],["c","b"]]

組み合わせ - combination

サンプルコード

const combination = (nums, k) => {
  let ans = [];
  if (nums.length < k) {
    return [];
  }
  if (k === 1) {
    for (let i = 0; i < nums.length; i++) {
      ans[i] = [nums[i]];
    }
  } else {
    for (let i = 0; i < nums.length - k + 1; i++) {
      let row = combination(nums.slice(i + 1), k - 1);
      for (let j = 0; j < row.length; j++) {
        ans.push([nums[i]].concat(row[j]));
      }
    }
  }
  return ans;
};

Usage

let arr = combination(['a', 'b', 'c'], 2);
console.log(JSON.stringify(arr));
// [["a","b"],["a","c"],["b","c"]]