[코딩 테스트] 순열 & 조합

파이썬

순열

def perm(lst, n):
    result = []
    if n > len(lst):
        return result
    if n == 1:
        for i in lst:
            result.append([i])
    elif n > 1:
        for i in range(len(lst)):
            temp = [i for i in lst]
            temp.remove(lst[i])
            for p in perm(temp, n - 1):
                result.append([lst[i]] + p)

    return result

조합

def comb(arr, n):
    chosen = []
    if n > len(arr):
        return chosen
    if n == 1:
        for i in arr:
            chosen.append(i)
    elif n > 1:
    	# r 개 만큼 빼주는 이유 (순서가 고려사항이 아니기 때문에, r개는 고려하지 않아도 앞서서 정해진다)
        for i in range(len(arr) - n + 1):
            for c in comb(arr[i+1:], n - 1):
                chosen.append([arr[i], c])
    return chosen

자바스크립트

순열

var permute = function(nums) {
    const result = [];
    
    function permute(arr, options) {
        if(!options.length) result.push(arr);
        
        for(let i = 0; i < options.length; i++) {
            permute([...arr, options[i]], [...options.slice(0, i), ...options.slice(i+1)]);
        }
    }
    permute([], nums)
    return result;
};

function permutation(arr, num) {
  let result = [];
  if(num == 1) return arr.map(e => [e]);
  
  arr.forEach((e,i,array) => {
    let rest = [...array.slice(0,i), ...array.slice(i+1)];
    let perms = permutation(rest,num-1);
    let permArr = perms.map(x => [e, ...x])
    result.push(...permArr);
  }) 
  return result;
}

조합

function combination(arr, num) {
  let result = [];
  if(num == 1) return arr.map(e => [e]);
  
  arr.forEach((e,i,array) => {
    let rest = array.slice(i+1);
    let combinations = combination(rest,num-1);
    let combiArr = combinations.map(x => [e, ...x])
    result.push(...combiArr);
  }) 
  return result;
}

너무 헷갈리면 그냥 외우자!