[자바스크립트] 집합(초집합, 합집합, 교집합, 차집합, 멱집합)

자바스크립트에서는 파이썬의 itertools같이 편리한 내부 라이브러리가 없다.

따라서 모든 집합 연산을 직접 구현해야한다.

다행히 Set 객체는 존재하기 때문에 이 객체를 통해 연산하면 된다.

---

초집합

Set.prototype.isSuperset = function(subset) {
    for (var elem of subset) {
        if (!this.has(elem)) {
            return false;
        }
    }

    return true;
}

var setA = new Set([1, 2, 3, 4]);
var setB = new Set([2, 3]);
setA.isSuperset(setB);  // true

Set 객체의 prototype에 isSuperset이라는 메소드를 등록한다.

인자로 전달받은 subset의 원소가 Set 객체에 포함되어 있지 않다면 false를 반환한다.

 

 

합집합

Set.prototype.union = function(setB) {
    var union = new Set(this);
    for (var elem of setB) {
        union.add(elem);
    }

    return union;
}

var setA = new Set([1, 2]);
var setB = new Set([2, 3]);
setA.union(setB);  // Set [1, 2, 3]

Set 객체의 prototype에 union이라는 메소드를 등록한다.

원본 Set 객체를 복사하여 union 집합을 만들고, setB의 원소를 union 집합에 add한다.

 

 

교집합

Set.prototype.intersection = function(setB) {
    var intersection = new Set();
    for (var elem of setB) {
        if (this.has(elem)) {
            intersection.add(elem);
        }
    }

    return intersection;
}

var setA = new Set([1, 2, 3, 4]);
var setB = new Set([2, 3]);
setA.intersection(setB);  // Set [1, 2]

Set 객체의 prototype에 intersection이라는 메소드를 등록한다.

intersection이라는 새로운 Set 객체를 만들어 둔다.

기존의 Set 객체에 인자로 전달받은 setB의 원소가 포함되어 있는지 확인하고, 포함되어 있다면 intersection 집합에 그 원소를 add한다.

 

 

차집합

Set.prototype.difference = function(setB) {
    var difference = new Set(this);
    for (var elem of setB) {
        difference.delete(elem);
    }

    return difference;
}

var setA = new Set([1, 2, 3, 4]);
var setB = new Set([1, 4]);
setA.difference(setB);  // Set [2, 3]

Set 객체의 prototype에 difference라는 메소드를 등록한다.

현재 Set 객체를 difference라는 변수로 복사해놓는다.

인자로 전달받은 setB의 원소를 difference 집합에서 delete한다.

 

 

멱집합

function getSubSets(arr) {
    var flag = new Array(arr.length).fill(false);
    var subSets = [];

    var subSet = function DFS(depth) {
        if (depth === arr.length) {
            var element = arr.filter((_, index) => flag[index]);
            subSets.push(element);

            return;
        }

        flag[depth] = true;
        subSet(depth + 1);

        flag[depth] = false;
        subSet(depth + 1);
    }

    subSet(0);
    return subSets;
}

완전 탐색을 이용해서 함수를 구현한다.

집합 [1, 2]를 예시로 tree를 통해 멱집합을 구해보면 아래 그림과 같다.

그림

왼쪽 노드를 선택했을 때, 오른쪽 노드는 선택되지 않는다.

같은 Depth에 있는 노드값들은 모두 동일하기 때문에 한 쪽 노드만 선택되면서 중복된 노드값이 선택되지 않게 된다.

 

코드를 살펴보면

var flag = new Array(arr.length).fill(false);

flag는 선택된 노드를 표시해둘 배열이다. 이 flag 배열의 상태에 따라(true인 인덱스만 사용) 원본 집합에서 부분집합들을 구하게 된다.

 

var subSets = [];

구한 부분집합들을 담아둘 배열이다.

 

var subSet = function DFS(depth) {
        if (depth === arr.length) {
            var element = arr.filter((_, index) => flag[index]);
            subSets.push(element);

            return;
        }

        flag[depth] = true;
        subSet(depth + 1);

        flag[depth] = false;
        subSet(depth + 1);
    }

subset은 메인 로직 함수를 가지고 있는 객체이다.

인자로 전달받은 depth가 원본 집합의 개수와 같게될 때를 탈출 조건으로 갖는다.

이 때는 filter() 메소드를 사용해서 원본 집합 arr의 인덱스 중에 flag[index]가 true인 값만 골라 element에 담고, subSets 배열에 push한다.

 

// 왼쪽 노드 선택
flag[depth] = true;
subSet(depth + 1);

// 왼쪽 노드 선택 안함(오른쪽 노드 선택)
flag[depth] = false;
subSet(depth + 1);

탈출 조건에 도달하지 않았다면 왼쪽 노드를 선택했을 때와, 오른쪽 노드를 선택했을 때를 구분하여 재귀해준다. 재귀함수를 호출할 때는 depth를 1 더해주어야 한다.

 

subSet(0);
return subSets;

구현한 subSet객체에 0을 인자로 전달해서 함수를 호출하고, 구해진 멱집합을 반환한다.

 

파이썬의 itertools 라이브러리에 있는 combinations처럼 사용하고 싶다면 아래와 같이 코드를 수정하면 된다.

function getSubSets(arr, n) {
    if (n === -1) {
        var flag = new Array(arr.length).fill(false);
        var subSets = [];
    
        var subSet = function DFS(depth) {
            if (depth === arr.length) {
                var element = arr.filter((_, index) => flag[index]);
                subSets.push(element);
    
                return;
            }
    
            flag[depth] = true;
            subSet(depth + 1);
    
            flag[depth] = false;
            subSet(depth + 1);
        }
    
        subSet(0);
        return subSets;
    }
    else {
        var flag = new Array(arr.length).fill(false);
        var subSets = [];
    
        var subSet = function DFS(depth) {
            if (depth === arr.length) {
                var element = arr.filter((_, index) => flag[index]);
                subSets.push(element);
    
                return;
            }
    
            flag[depth] = true;
            subSet(depth + 1);
    
            flag[depth] = false;
            subSet(depth + 1);
        }
    
        subSet(0);
        return subSets.filter(arr => arr.length === n);
    }
}

인자 n이 -1이면 단순히 멱집합을 구하고, 그렇지 않다면 부분집합 중 원소의 개수가 n인 부분집합만 반환하는 함수이다.

---

참고한 글

 

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Set

Set - JavaScript | MDN

 

https://code-designer.tistory.com/56

자바스크립트 모든 부분 집합(멱집합) 구하기