Permutation과 Combinations

Permutations (순열)

서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수

nPr = n·(n-1)·(n-2)···(n-r+1)

---

function allPermutations (items) {
// allPermutations () : return a list of all possible permutations
// credits: https://stackoverflow.com/questions/9960908/permutations-in-javascript
 
  let results = [];
  function permute (arr, memo) {
    var cur, memo = memo || [];
    for (let i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }
    return results;
  }
  permute(items);
  return results;
}
 
var fruits = ["Apple", "Banana", "Coconut"];
var permutated = allPermutations(fruits);
console.table(permutated);

Combinations (조합)

서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한다.

nCr = n(n−1)(n−2)⋯⋯(n−r+1)​ / r!

---

function allCombinations (items) {
// allcombinations () : return a list of all possible combinations
 
  let results = [];
  for (let slots = items.length; slots > 0; slots--) {
    for (let loop = 0; loop < items.length - slots + 1; loop++) {
      let key = results.length;
      results[key] = [];
      for (let i = loop; i < loop + slots; i++) {
        results[key].push(items[i]);
      }
    }
  }
  return results;
}

var fruits = ["Apple", "Banana", "Coconut"];
var combo = allCombinations(fruits);
console.table(combo);

 

* 알고리즘 문제를 풀때 순열 및 조합 문제들이 나왔을때 참고하면 좋습니다.