만족스러운 인증 조건의 서브 세트를 생성하는 알고리즘

StackOverflow https://stackoverflow.com/questions/936015

  •  06-09-2019
  •  | 
  •  

문제

정렬 된 요소 목록이 제공되고 일부 조건을 충족하는 모든 서브 세트를 생성하고 싶다고 가정 해 져서 주어진 세트가 조건을 충족시키지 않으면 더 큰 서브 세트도이를 충족시키지 못하고 하나의 요소 세트가 만족합니다. 그것.

예를 들어, 100보다 작은 모든 양의 정수 목록이 주어지면 합계가 130보다 작은 서브 세트를 결정합니다 : (100,29) (0,1,40), (0) 등 ...

(바람직하게는 파이썬에서) 어떻게 할 수 있습니까?

감사! :)

도움이 되었습니까?

해결책

a를 사용하여 모든 서브 세트를 생성 할 수 있습니다 지점과 바운드 기술 : 자두 조건으로 사용하여 "이미 결정된 하위 집합의 슈퍼 세트 생성)로 모든 서브 세트를 생성 할 수 있습니다.

제약 조건에 관해 일반적이되고 싶다면 이것이 최선의 전략이라고 생각합니다.

서브 세트를 생성하는 코드를 올바른 방식으로 작성하십시오. 그렇지 않으면 여러 시간에 동일한 서브 세트를 생성합니다. Memoization을 피하기 위해 MAP 조회로 인해 시간이 소요될 수있는 메모리 오버 헤드를 소개하면 서브 세트를 생성 할 수 있습니다. 그런 식으로 :

GetAllSubsets(List objects) {
    List generated = {};
    GetAllSubsets(generated, [], objects);
    return generated;
}

GetAllSubsets(List subsetGenerated, List objectFixed, List objectsToFix) {
    GetAllSubsets(subsetGenerated, objectFixed, objectsToFix.sublist(1, objectsToFix.length());
    if (satisfy(toCheck = objectsFixed.add(objectsToFix.get(0)))) {
        subsetGenerated.add(toCheck);
        GetAllSubsets(subsetGenerated, toCheck, objectsToFix.sublist(1, objectsToFix.length());
    }
}

실제로, GetAllSubsets의 첫 번째 호출에 의해 추가 된 서브 세트에는 ObjectStofix의 첫 번째 요소가 없으며, 두 번째 호출에 의해 추가 된 서브 세트 (가지 치기 조건이 위반되지 않은 경우)에 해당 요소가 있으므로 두 가지의 교차점 생성 된 서브 세트 세트는 비어 있습니다.

다른 팁

빈 세트부터 시작하여 더 많은 요소를 추가하려고 시도하여 세트를 재귀 적으로 구성 할 수 있으며, 서브 세트 중 하나 (및 모든 슈퍼 세트)가 조건을 충족시키지 못하면 재귀 적 실행 라인을 포기할 수 있습니다. 다음은 일부 의사 코드가 있습니다. 조건이 만족스러운 서브 세트를 나열하려는 세트를 가정합니다. 편의를 위해 S의 요소가 x (0), x (1), x (2), ...로 인덱싱 될 수 있다고 가정합니다. 

EnumerateQualifyingSets(Set T)
{
    foreach (x in S with an index larger than the index of any element in T)
    {
            U = T union {x}

            if (U satisfies condition)
            {
                print U
                EnumerateQualifyingSets(U)
            }
    }
}

첫 번째 호출은 T를 빈 세트로 사용합니다. 그런 다음 조건과 일치하는 S의 모든 서브 세트가 인쇄됩니다. 이 전략은 조건을 충족하지 않는 S의 하위 집합을 포함 할 수 없다는 사실에 결정적으로 의존합니다.

확실히 할 수있는 방법이 있지만, 어떻게 든 조건을 제한 할 수 없다면 O (2^n) 단계를 수행 할 것입니다. 예를 들어 모든 서브 세트가 선택되는 1–100의 조건을 고려하면 (예 : <σ 나 ~을 위한 나 1-N), 그러면 모든 서브 세트를 열거하게됩니다.

당신은보고있을 것입니다

for i in the powerset of {1-n}
    if cond(i)
       note that set

0에서 s까지 모든 바이너리 숫자를 단순히 생성하여 세트의 파워 세트를 얻을 수 있습니다.N-1, 그리고 비트 i가 1 일 때 하위 집합의 요소 i를 선택합니다.

클래스 일정 생성 알고리즘에 대해 비슷한 일을했습니다. 우리의 일정 수업에는 2 개의 요소가 있습니다 - 일정에 추가 된 코스 목록과 추가 할 수있는 코스 목록이 있습니다.

의사 코드 :

queue.add(new schedule(null, available_courses))
while( queue is not empty )
    sched = queue.next()
    foreach class in sched.available_courses
        temp_sched = sched.copy()
        temp_sched.add(class)
        if(temp_sched.is_valid())
            results.add(temp_sched)
            queue.add(temp_sched)

아이디어는 빈 일정과 사용 가능한 클래스 목록으로 시작하고 유효한 일정을 위해 트리를 검색하는 것입니다 (유효한 의미는 사용자가 제공 한 요구 사항에 맞는 시간 충돌이 없습니다). 일정이 유효하지 않으면 버려집니다. 클래스를 추가하여 유효한 일정을 유효하게 만들 수 없습니다 (예 : 트리를 가지 치기).

문제를 해결하기 위해 이것을 수정하는 것은 매우 쉽습니다.

다음은 재귀 기능을 사용하여 서브 세트를 생성하는 Akappa의 답변의 구체적인 예입니다.

def restofsubsets(goodsubset, remainingels, condition):
    answers = []
    for j in range(len(remainingels)):
        nextsubset = goodsubset + remainingels[j:j+1]
        if condition(nextsubset):
            answers.append(nextsubset)
            answers += restofsubsets(nextsubset, remainingels[j+1:], condition)
    return answers

 #runs slowly
 easieranswer = restofsubsets([], range(101), lambda l:sum(l)<40)

 #runs much faster due to eliminating big numbers first
 fasteranswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<40)

 #runs extremely slow even with big-numbers-first strategy
 finalanswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<130)

최악의 경우에도 모든 서브 세트를 생성하고 각 세트의 합을 계산하여 자격이 있는지 여부를 결정해야한다고 생각합니다. 비대칭 적으로, 그것은 서브 세트 생성 절차의 비용입니다.

다음은 동일한 아이디어를 위해 JavaScript에서 구현 한 방법입니다. 

//this is to generate an array to test
var numbers = (function(start, end){
    var result = [],
        i =  start; 
    for(; i <= end; i++){
        result.push(i);
    }
    return result; 
})(1, 12);

//this is the qualifying function to determine if the generated array is qualified
var fn = (function(maxSum){
    return function(set){
        var sum = 0;
        for(var i = 0 ; i< set.length; i++){
            sum += set[i];
            if( sum > maxSum ){
                return false;
            }
        }
        return true;
    }
})(30);

//main function
(function(input, qualifyingFn){
    var result, mask, total = Math.pow(2, input.length);
    for(mask = 0; mask < total; mask++){

        result = [];
        sum = 0;

        i = input.length - 1; 
        do{
            if( (mask & (1 << i)) !== 0){
                result.push(input[i]);
                sum += input[i];
                if( sum > 30 ){
                    break;
                }
            }
        }while(i--);
        if( qualifyingFn(result) ){
            console.log(JSON.stringify(result));
        }
    }

})(numbers, fn);
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top