중복 순열

반복문

let result = [];
let arr = [1, 2, 3]
for(let i = 0; i < arr.length; i++){
  for(let j = 0; j < arr.length; j++){
    for(let k = 0; k < arr.length; k++){
      result.push([arr[i], arr[j], arr[k]]);
    }
  }
}
console.log(result)

재귀

let result = [];

function multiPermutation(arr, n, bucket) {
  if(n === 0) { 
    result.push(bucket);
    return;
  }
  for(let i = 0; i < arr.length; i++){
    multiPermutation(arr, n - 1, bucket.concat(arr[i]))
  }
  return result;
}

multiPermutation([1,2,3], 3, []);

순열

중복을 허용하지 않는다.

반복문

index가 하나라도 같으면 반복문을 한 턴 넘기는 원리

let result = [];
let arr = [1, 2, 3]
for(let i = 0; i < arr.length; i++){
  for(let j = 0; j < arr.length; j++){
    for(let k = 0; k < arr.length; k++){
      if(i === j || j ===k || k === i) continue;
      result.push([arr[i], arr[j], arr[k]]);
    }
  }
}
console.log(result)

재귀

현재 선택된 배열의 요소를 splice 하면서 재귀가 진행되면, 중복을 제거한 조합을 만든다.

let result = [];
function permutation(arr, n, bucket){
  if(n === 0){
    result.push(bucket);
    return;
  }
  
  for(let i = 0; i < arr.length; i++){
    let rest = arr.slice();
    let pick = rest.splice(i, 1);
    permutation(rest, n - 1, bucket.concat(pick));
  }
  return result
}

permutation([1,2,3], 3, []);

조합

중복과 순서의 중복을 허용하지 않는다.
ex) 조합은 [1,2,3]과 [1,3,2]를 같은 것으로 간주한다.

반복문

let result = [];
let arr = [1,2,3];

for(let i = 0; i < arr.length; i++){
  for(let j = i + 1; j < arr.length; j++){
    result.push([arr[i], arr[j]])
  }
}
console.log(result);

재귀

조합은 순서가 다른 것도 같은 것이라고 간주하여서, pick한것을 제외할 뿐만 아니라, 다시 넣지 말아야 한다.

let result = [];
function combination(arr, n, bucket){
  if(n === 0){
    result.push(bucket);
    return;
  }
  
  for(let i = 0; i < arr.length; i++){
    let pick = arr[i];
    let rest = arr.slice(i + 1);
    combination(rest, n - 1, bucket.concat(pick));
  }
  return result;
}

combination([1,2,3], 2, []);