Javascript 순열과 조합 (Feat.재귀함수) | protect-me

순열은 순서를 따지고, 조합은 순서를 따지지 않음

📝 순열

---

서로 다른 n개의 물건 중에서 r개를 택하여
한 줄로 배열하는 것을 n개의 물건에서 r개 택하는 순열이라 하고,
이 순열의 수를 기호로 nPr과 같이 나타낸다.

const getPermutations= function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]);

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
    const permutations = getPermutations(rest, selectNumber - 1);
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    results.push(...attached);
  });

  return results;
};

const example = [1,2,3,4];
const result = getPermutations(example, 3);
console.log(result);

📝 조합

---

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때,
이것은 n개에서 r개를 택하는 조합이라 하고,
이 조합의 수를 기호로 nCr와 같이 나타낸다.

function getCombinations(arr, num) {
  const result = [];
  if (num === 1) return arr.map((value) => [value]);
  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, num - 1);
    const attached = combinations.map((combination) => [fixed, ...combination]);
    result.push(...attached);
  });
  return result;
}
const arr = [1, 2, 3, 4];
const num = 3;
console.log(getCombinations(arr, num));
// [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

1	2	3	결과
1고정
	2고정		[2,3], [2,4]
		3고정	[3,4]

최종 : [[1,2,3], [1,2,4], [1,3,4]]

조합 디버깅 코드

const getCombinations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) {
    console.log(
      "return",
      arr.map((value) => [value])
    );
    return arr.map((value) => [value]);
  }
  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    console.log("fixed", fixed, "------------");
    console.log("rest", rest);
    const combinations = getCombinations(rest, selectNumber - 1);
    console.log("combinations", combinations);
    const attached = combinations.map((combination) => [fixed, ...combination]);
    console.log("attached", attached);
    results.push(...attached);
    console.log("results", results);
    console.log("======================");
  });
  console.log("============================================");

  return results;
};

📚 참고

---

• 네이버 지식백과 : 순열
• 네이버 지식백과 : 조합
• JavaScript로 순열과 조합 알고리즘 구현하기 | 춤추는 개발자
• Photo by Anne Nygård on Unsplash