JavaScriptを用いた順列、組み合わせ

Table of contents

調べた経緯

配列の中から数字選ぶ際、被らないように選びたかった。 その際、「Permutation（順列）」「Combination（組み合わせ）」を知ったのでメモ。

コード

コードは下記に示す。

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;
};

const numList = [1, 2, 3];

let arr = permutation(numList, 3);

console.log(arr);

// [
//   [ 1, 2, 3 ],
//   [ 1, 3, 2 ],
//   [ 2, 1, 3 ],
//   [ 2, 3, 1 ],
//   [ 3, 1, 2 ],
//   [ 3, 2, 1 ]
// ]

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;
};

const numList = [1, 2, 3];

let arr = combination(numList, 3);

console.log(arr);

// [
//   [ 1, 2 ],
//   [ 1, 3 ],
//   [ 2, 3 ]
// ]

参考

https://tech-blog.s-yoshiki.com/entry/144