순열, 조합(Permutaions and Combinations)

📌 순열(Permutaions)

이미지 출처 https://www.geeksforgeeks.org/wp-content/uploads/NewPermutation.gif

🔎 특징

• 순서가 중요함
• 조합을 구한 후, 선택하려는 수의 factorial을 곱하면 순열을 구하는 공식 (nPr = nCr x r!)

⌨ 구현

1. 순열

• 입력받은 배열을 forEach를 순회하며 처음에 선택한 fixer 선택
• fixer를 제외한 새로운 restArr 생성
• permutationArr에 restArr, targetNumber-1 순열 존재
• combineFixer에 fixer와 permutationArr을 합침
• result push

const permutation = (arr, targetNumber) => {
  const result = [];
  // 1개를 선택하는 경우 모든 배열 요소 리턴
  if(targetNumber === 1) return arr.map(v => [v]);
  
  arr.forEach((val, idx, arr) => {
    const fixer = val;
    // 해당하는 fixer를 제외한 나머지 배열 구하기
    const restArr = arr.filter((_, index) => index !== idx);
    // 나머지의 순열 구하기
    const permutationArr = permutation(restArr, targetNumber-1);
    // 돌아온 순열에 대해 fixer 값 합치기
    const combineFixer = permutationArr.map(v => [fixer, ...v].join('');
    // 결과에 push
    result.push(...combineFixer);
  });
  return result;
}

const item = permutation([0, 1, 3], 3);
console.log(item); // ["013", "031", "103", "130", "301", "310"]

2. 중복순열

• 입력받은 배열을 forEach를 순회하며 처음에 선택한 fixer 선택
• restArr = originArr
• permutationArr에 restArr, targetNumber-1 순열 존재
• combineFixer에 fixer와 permutationArr을 합침
• result push

const duplicationPermutation = (arr, targetNumber) => {
  const result = [];
  if(targetNumber === 1) return arr.map(v => [v]);
  arr.forEach((val, idx, arr) => {
    const fixer = val;
    const restArr = arr;
    const permutationArr = duplicationPermutation(restArr, targetNumber-1);
    const combineFixer = permutationArr.map(v => [fixer, ...v].join(''));
    result.push(...combineFixer);
  });
  return result;
}
const item = duplicationPermutation([0, 1, 3], 3);
console.log(item); //  ['000', '001', '003', '010', '011', '013', '030', '031', '033', '100', '101', '103', '110', '111', '113', '130', '131', '133', '300', '301', '303', '310', '311', '313', '330', '331', '333']

---

📌 조합(Combinations)

이미지 출처 https://www.techiedelight.com/find-permutations-given-string/

🔎 특징

• 순서는 상관없음 ([1, 2, 3] === [3, 2, 1])
• 조합을 구한 후, 선택하려는 수의 factorial을 곱하면 순열을 구하는 공식 (nPr = nCr x r!)

⌨ 구현

• 입력받은 배열을 forEach를 순회하며 처음에 선택한 fixer 선택
• fixer를 제외한 나머지 뒤 배열 생성
• combinationArr에서 restArr, targetNumber-1 나머지 조합을 구함
• combineFixer에 fixer와 combinationArr을 합침
• result push

const combination = (arr, targetNumber) => {
  const result = [];
  if(targetNumber === 1) return arr.map(v => [v]);
  
  arr.forEach((val, idx, arr) => {
  	const fixer = val;
    const restArr = arr.slice(idx+1);
    const combinationArr = combination(restArr, targetNumber-1);
    const combineFixer = combinationArr.map(v => [fixer, ...v].join(''));
    result.push(...combineFixer);
  });
  return result;
}

console.log(combination([0, 1, 2, 3], 2)); // ["01", "02", "03", "12", "13", "23"]