JavaScript에서 비어 있지 않은 하위 집합의 수를 찾는 방법

숫자 또는 문자로 구성되고 반복되는 값을 가질 수 있는 시퀀스 요소가 있는 경우 비어 있지 않은 부분 집합의 수를 찾는 방법은 무엇입니까?

예를 들어 {1, 2, 3, 4} 시퀀스가 ​​있고 비어 있지 않은 하위 집합은 다음과 같습니다.

{ {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4},{3,4 }, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}등 15개 항목이며, 빈 세트는 통계에 포함되지 않습니다.

또 다른 예는 {a, b, c, d, d} 시퀀스인데, 내부에 반복되는 값이 있지만 집합이 반복 가능하지 않기 때문입니다. , 따라서 비어 있지 않은 하위 집합에는

{{a}, {b}, {c}, {d}, {a,b}, {a,c}, {a, d }, {b,c}, {b,d},{c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c, d }, {a,b,c,d}}, 또한 15 항목, 반복되는 d이(가) 되었습니다. 제거됨 .

성능 요구 사항으로 인해 시퀀스의 길이가 50 또는 그 이상에 도달할 수 있으므로 기존의 부분 집합화 방법은 이 문제에 유용하지 않을 수 있습니다. 재귀를 사용하면 시간이 너무 오래 걸립니다.

다행스럽게도 하위 집합의 특정 내용을 물을 필요가 없고 숫자만 물을 필요가 있으므로 수식을 사용할 수 있습니다.

세트(시퀀스가 아님)에 N개의 요소가 있는 경우 2 N전력 하위 집합. 이 하위 집합에는 빈 집합과 그 자체가 포함되어 있으므로 비어 있지 않은 하위 집합을 원할 경우 2^N을 사용할 수 있습니다. - 1으로 계산합니다.

여기서는 이 문제를 2단계로 나눌 수 있습니다.

1. 시퀀스 중복 제거

2. 공식을 사용하여 비어 있지 않은 부분 집합의 수를 계산하세요

function estSubsets(arr) {
    var hash = {};
    for(var i=0;i<arr.length;i++){
        hash[arr[i]] = null;
    }
    arr = Object.keys(hash);
    return Math.pow(2,arr.length) - 1;
}

위 내용은 JavaScript에서 비어 있지 않은 하위 집합의 수를 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!