Set, PowerSet, Combination, Permutation

[dlehdanakf]

집합

• JavaScript 에서 집합은 어차피 ArrayObject 일 테니 크게 신경은 쓰지 말자.
• 알고리즘적인 지식 보다는 코딩테스트를 풀면서 가져다 쓰게되는 집합과 관련된 여러가지 메소드를 정리해본다.

const numeric = [ 1, 2, 3, 4, ... ];
const alphabet = [ 'a', 'b', 'c', 'd', ... ];

부분집합

모든 가능한 부분집합

• 부분집합을 구하는 방법은 O(2ⁿ) 이다.
• 일단 집합 S에 대해 모든 부분집합을 구하는 방법부터!
• [ a, b ] 배열의 부분집합은 [ [ ], [a], [b], [a, b] ] 이다.
• [a, b, c] 배열의 부분집합은 [ [ ], [a], [b], [c] [a, b], [b, c], [a, c], [a, b, c] ] 이다.
• 자세히 보면 원소 c가 추가되면서 원래 [a,b] 부분집합들에 c를 더한 집합 + [a, b] 부분집합이다.
• P([ a,b,c ]) = P([ a,b ]) + (P([ a, b ]) + c) 인 것. 즉, 재귀호출이 가능하다.

const getAllSubsets = arr => arr
    .reduce((cur, acc) => [...cur, ...cur.map(set => [acc, ...set])], [[]]);

// 정렬된 버젼
const getAllSubsets = arr => arr
    .reduce((cur, acc) => [...cur, ...cur.map(set => [acc, ...set])], [[]])
    .map(cur => cur.sort((a, b) => a - b))
    .sort((a, b) => a.length - b.length);

• map 메소드는 실행하지 않아도 무방하다. 집합의 원소들이 꼭 정렬되어있을 필요는 없으니까.
• 여담으로, 배열 속 원소가 숫자가 아닌 알파벳일 경우 Array.prototype.sort((a, b) => a - b) 은 제대로 작동하지 않는다.
• .map(cur => cur.sort((a, b) => a.localeCompare(b))); 을 사용하자.

n개 원소의 부분집합

const combinations = (set, k) => {
    const result = [];
    if (k > set.length || k <= 0) return [];
    if (k == set.length) return [set];
    if (k == 1) {
        for(let i = 0; i < set.length; i++) {
            result.push([ set[i] ]);
        }

        return result;
    }

    for(let i = 0; i < set.length - k + 1; i++) {
        const head = set.slice(i, i + 1);
        const tail = combinations(set.slice(i + 1), k - 1);
        for(let j = 0; j < tail.length; j++) {
            result.push([...head, ...tail[j]])
        }
    }

    return result;
};

각 배열에서 하나씩 원소를 빼내 조합하기

/** cartesian([1,2,3,4], ['a','b'], ['ㄱ', 'ㄴ', 'ㄷ']) */
const cartesian = (...args) => {
    const results = [], max = args.length - 1;
    const helper = (arr, i) => {
        for(let j = 0, l = args[i].length; j < l; j++) {
            const a = [...arr]
            a.push(args[i][j]);

            if(i === max) results.push(a);
            else helper(a, i + 1);
        }
    };

    helper([], 0);
    return results;
};

순열

• 배열 속 원소들을 모든 경우의 방법으로 나열한 결과를 반환

const permutation = arr => {
    const result = [];
    arr.forEach((cur, i) => {
        const rest = permutation([...arr.slice(0, i), ...arr.slice(i + 1)]);
        if(rest.length === 0) result.push([ cur ]);
        else rest.forEach(m => result.push([ cur, ...m ]));
    });

    return result;
};