알고리즘은 문제

Question

을 설정 해결 :

을 어떤 집합의 모든 가능한 조합을 해결하는 가장 좋은 방법은 노동 조합은 x와 같지만 누구도 서로 교차하지 않습니다. X는 숫자 1 ~ 100의 설정되면

, 그리고 네 개의 서브 세트가 :

예가있을

• 를 = 0-49
• B = 50-100
• C = possib 후 50-75
• D = 76 -

제작 조합 일 것이다 :

• A + B
• A + C + D

Answer 1

설명하는 내용을 Exact cover 문제라고합니다. 일반적인 솔루션은 Knuth의 Algorithm X이고, Dancing Links 알고리즘은 구체적인 구현입니다.

Answer 2

길 (가장 좋은 방법이 될 수 없음)이다

1. 는 집합 만들기 겹치는 모든 부분 집합 쌍.
2. 원래 하위 집합의 모든 조합에 대해 조합에 1 단계에 나열된 쌍 중 하나 이상이 포함되어 있으면 "거짓"이라고 말한 다음 하위 집합의 합집합이 x와 같은 경우 "참"이라고 말하십시오 (예 : 부분 집합의 요소는 x입니다.

Answer 3

실제 알고리즘은 부분 집합, 제품 연산 및 동등 연산의 선택에 크게 좌우됩니다. 추가 (+)의 경우 사용자의 필요에 맞게 summation을 찾을 수있는 것처럼 보입니다 (1에서 100까지의 합계는 a + b 예제와 유사합니다). 이렇게 할 수 있다면 알고리즘은 분명히 O (1)입니다.

강인한 제품 또는 동등 연산자를 사용하는 경우 (두 용어를 곱하면 문자열을 합산하고 SHA-1 해시를 찾는 것이라고 가정 해 봅시다.) O (n^x) 여기서 x는 용어/변수의 수입니다.

Answer 4

작업해야하는 하위 집합에 따라보다 단순한 알고리즘을 사용하는 것이 좋습니다. 하나는 전체 하위 집합을 비교할 필요가 없지만 상한선과 하한선 만 비교하면됩니다.

임의의 부분 집합을 말하는 것이지, 반드시 범위를 말하는 것이 아니라면 Nick Johnson의 제안이 최선의 선택 일 것입니다.

Answer 5

x의 요소에 정렬 순서 (이 유한 또는 가산 집합 항상 가능하다 필요한 경우까지 일을 할)을 감안할 때 :

는 "지금까지 선택 세트는"빈하자. x의 가장 작은 요소를 고려하십시오. x를 포함하고 지금까지 선택된 세트와 교차하지 않는 모든 세트를 찾습니다. 이러한 각 세트에 대해 차례로 반복하여 선택한 세트를 "지금까지 선택된 세트"에 추가하고 선택한 세트에없는 x의 가장 작은 요소를 봅니다.왼쪽 x의 요소가없는 지점에 도달하면 솔루션을 찾았습니다. 찾고있는 요소가 포함 된 선택되지 않은 세트가없고 이미 선택한 세트와 교차하지 않는 지점에 도달하면 솔루션을 찾지 못해 다시 추적합니다.

이것은되도록 조심 교차하지 않는 부분 집합의 개수에 비례 스택을 사용한다. 또한 많은 시간을 사용합니다 - 예에서와 같이 하위 집합이 모두 인접한 범위 인 경우 훨씬 효율적으로 작업 할 수 있습니다.

Answer 6

여기 나쁜 방법 (순환 중복 많은 일을한다). 그러나 실제 코드는 적어도 "효율적인"솔루션의 절반 정도입니다.

def unique_sets(sets, target): 
    if not sets and not target: 
     yield [] 
    for i, s in enumerate(sets): 
     intersect = s.intersection(target) and not s.difference(target) 
     sets_without_s = sets[:i] + sets[i+1:] 
     if intersect: 
      for us in unique_sets(sets_without_s, target.difference(s)): 
       yield us + [s] 
     else: 
      for us in unique_sets(sets_without_s, target): 
       yield us 

class named_set(set): 
    def __init__(self, items, name): 
     set.__init__(self, items) 
     self.name = name 

    def __repr__(self): 
     return self.name 

a = named_set(range(0, 50), name='a') 
b = named_set(range(50, 100), name='b') 
c = named_set(range(50, 75), name='c') 
d = named_set(range(75, 100), name='d') 

for s in unique_sets([a,b,c,d], set(range(0, 100))): 
    print s