구성 자의 조합 수

https://stackoverflow.com/questions/1154565

18-09-2019
|

문제

제품 구성 자의 가능한 조합 수를 결정하기 위해 루틴을 프로그래밍하도록 요청 받았습니다.

구성자는 정말 간단합니다. 이보다 더 많은 기능이 있지만 N 옵션 중 하나를 선택 해야하는 여러 "무선 그룹"(UI 제어와 같은)으로 모델링 할 수 있습니다.

사용할 수있는 유일한 제약 조건은 하나의 옵션을 선택하면 다른 옵션을 선택할 수 없다는 규칙입니다.

따라서 옵션 그룹과 제약 조건이 주어지면 구성 할 수있는 다양한 제품의 수를 계산하는 것입니다.

나는 이것을 사용하여 이것을 해결하기 위해 순진한 접근 방식을 만들었습니다. 포함 배제 원리. 그러나 내가 볼 수있는 한,이 방법을 기반으로 한 알고리즘은 작동하지 않는 O (2^N)로 실행해야합니다. 물론 괜찮은 런타임을 제공해야 할 몇 가지 가능한 최적화가 있지만 여전히 최악의 시나리오가 쉽게 구성 될 수 있습니다.

그게 내가 지금있는 곳이 거의 없습니다. 제안이 있습니까?

업데이트

나는 규칙이 어떻게 충분히 적용되는지 설명하지 않았다는 것을 알고 있습니다.

옵션이있는 여러 그룹이 있습니다. 각 그룹에서 하나의 옵션 만 선택해야합니다. 그룹에는 하나 이상의 옵션이있을 수 있습니다.

제약 조건은 하나뿐입니다. 일부 그룹의 옵션 A가 선택되면 다른 그룹의 옵션 B를 선택할 수 없습니다. 수많은 제약 조건이있을 수 있으며 옵션 그룹 또는 옵션 자체에 적용되는 제약/규칙의 수가 제한되지 않습니다.

그래서 예는 다음과 같습니다.

그룹 1 : 그룹 1.
x1 x2 x3 x4 x5

그룹 2 : 그룹 2.
Y1 Y2 Y3

그룹 3 :
Z1 Z2 Z3 Z4

제약 조건 :
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

* Group1에서 옵션 X1을 선택하면 그룹 2의 옵션 Y2를 선택할 수 없습니다.

포함 배치를 사용하여 조합 수를 다음과 같이 계산합니다.

조합 = c_{규칙이 없습니다} - 씨_{아르 자형}[1] - 씨_{아르 자형}2] -c_{아르 자형}3] + c_{아르 자형}1,2] + c_{아르 자형}1,3] + c_{아르 자형}2,3] -c_{아르 자형}[1,2,3]

어디에

씨_{규칙이 없습니다} = 5 * 3 * 4

씨_{아르 자형}A, B, C] = 규칙 A, B 및 C를 위반하는 조합 수.

불행히도이 방법은 2^| 규칙 |를 필요로합니다 계산.

해결책

좋아, 나는 2 ^ n 정도를 얻을 수 없지만 샘플 세트를 줄일 수있다. 이를 위해 "작곡 된 제약 조건"을 계산할 것입니다. 구성된 제약 조건은 왼쪽의 모든 옵션을 선택하면 오른쪽의 옵션을 선택할 수 없지만 왼쪽 옵션을 기반으로 다른 제약 조건이 적용될 수없는 제약 조건입니다.

우리는 일련의 제약으로부터 가능한 모든 구성 제약 조건 세트를 계산해야합니다. 필요하지는 않지만 오른손 그룹이 왼쪽 그룹보다 작 으면 왼쪽과 오른손을 교환하여 기존 제약 조건을 "고정"합니다. 이렇게하면 스왑에 더 나은 휴리스틱이 가능하지만 일부 구성 제약 조건이 줄어들 수 있습니다.

또한 각 그룹에 대해 임의로 선택할 수있는 "최소 세트"옵션을 계산해야합니다. 이 최소 세트는 사용 가능한 옵션 목록에서 구성된 제약 조건의 왼쪽에 나타나는 옵션을 제거하여 계산됩니다.

알고리즘이 뒤 따릅니다. 그러나 나는 그것이 CC를 올바르게 계산한다는 것을 증명하지는 않습니다. 그렇다면 가능한 조합의 수를 계산하는 데 사용될 수 있음을 증명할 것입니다.

왼손의 그룹이 오른손 그룹보다 작거나 동일하도록 제약 조건을 고정하십시오.
제약 조건을 구성하십시오.
1. 왼손으로 제약 조건을 정렬하십시오
2. 순차적으로, 각각의 제약에 대해 :
  1. 같은 왼손으로 뒤 따르는 모든 제약 조건으로 제약을 접고 돌립니다. x1 <-> y1, x1 <-> y2 ... x1 <-> yN ~ 안으로 Set(x1) <-> Set(y1 ... yN)
  2. 접힌 제약 조건을 이미 접힌 각 제약 조건으로 구성하십시오.
    - X1은 이미 접힌 제약 조건의 오른쪽에 있지 않습니다.
    - X1은 왼손에 같은 요소의 동일한 그룹에 있지 않습니다.
  3. 접힌 제약 조건 및 모든 구성 제약 조건을 접힌 제약 조건에 추가하십시오.
모든 옵션을 사용하고 고정 제약 조건의 왼쪽에 나타나는 옵션을 제거하여 최소 세트를 계산하십시오.

이제 아래 공식으로 조합 수를 계산할 수 있습니다. CC를 구성된 제약 조건이라고 부릅니다. 그런 다음 조합 수는 다음과 같습니다.

C(Mininum Set) + CCC1 + ... + CCCn

어디에:

C (최소 세트)는 최소 세트로 가능한 조합 수입니다.
CCCX는 최소 세트를 가져 와서 CCX의 왼쪽에 옵션이있는 그룹을 해당 옵션으로 교체 한 다음 CCX의 오른쪽에 옵션을 제거함으로써 가능한 조합 수입니다.

표현은 순전히 부가 적입니다. 이것은 그 표현이 예상 결과를 산출하려면 다음 두 조건이 사실이어야 함을 의미합니다.

그것의 두 용어는 동일한 조합을 포함 할 수 없습니다.
모든 조합은이 약관에 의해 설명되어야합니다.
어떤 용어에 따라 유효하지 않은 조합이 산출되지 않을 수 있습니다.

첫 번째 증거의 경우 왼손이 같은 두 개의 별개의 CC가 없습니다. 두 CC가 왼손이 같지만 오른손이 다른 경우 CCS 중 하나에 적용되어야하는 추가 제약 조건이 있거나 다른 사람에게는 잘못된 제약 조건이 있음을 의미합니다.

왼손이 같은 두 개의 CC가없고 최소 세트에는 정의에 따라 CC의 왼손을 포함하지 않으므로 두 CC는 하나 이상의 옵션으로 구별 될 수 있지만 다른 하나는 하나에 대해 선택하지는 않습니다. . 따라서 두 CC가 동일한 조합을 생성 할 수 없습니다.

두 번째 증거의 경우, CCS 세트에는 정의상 왼손의 옵션에 대한 모든 유효한 조합이 포함되어 있습니다.

최소 세트 나 CC 세트에 나타나지 않는 하나의 조합이 있다고 가정하십시오. 이 조합에 왼쪽 옵션이 포함되어 있지 않으면 정의상 최소 세트의 조합이어야합니다. 따라서 왼손의 옵션이 포함되어야합니다.

CCS 세트에는 왼손에 대한 모든 유효한 조합이 포함되어 있으므로 왼쪽 옵션이 동일한 하나의 CC가 있습니다. 따라서이 조합에는 해당 CC에 대한 조합에 포함되지 않은 옵션이 있어야합니다. 그러나 CC에 포함되지 않은 유일한 옵션은 다른 CC의 왼손에 나타나는 옵션이며, 제약 조건으로 제외 해야하는 옵션입니다. 어느 것도 그렇지 않을 수도 있으므로이 조합은 존재할 수 없습니다.

세 번째 증거를 위해 먼저 최소 세트를 고려해 봅시다. 최소 세트에는 그룹의 왼쪽에 옵션이 포함되어 있지 않습니다. 모든 제약 조건은 왼쪽과 오른쪽 옵션 사이에 있으므로 최소 세트에 제약 조건이 적용되지 않습니다.

이제 CCS를 고려해 봅시다. CC는 정의에 따라 왼손 옵션의 유효한 조합을 가지고 있습니다. 해당 왼손과 호환되지 않는 옵션은 오른손에 나타나야하며 해당 오른손의 옵션을 최소 세트에서 제거해야합니다. 처음부터 호환되지 않는 최소 세트의 옵션이 없기 때문에 CC의 조합에서 만족스럽지 않은 제약 조건이 없을 수 있습니다.

그리고 그것은 증거를 끝냅니다.

이것이 주석의 예제와 함께 어떻게 적용되는지 봅시다.

G1: x1, x2, x3 
G2: y1, y2 
G3: z1, z2, z3 

R1: x1 <-> y2 
R2: x3 <-> y2 
R3: y1 <-> z1 
R4: y2 <-> z2 
R5: y2 <-> z3

CC1: {x1} <-> {y2}
CC2: {x3} <-> {y2}
CC3: {y1} <-> {z1}
CC4: {x1, y1} <-> {y2, z1}
CC5: {x3, y1} <-> {y2, z1}
CC6: {y2} <-> {z2, z3}

목록에없는 작곡 그룹에 대해 간단히 숙고합시다.

R1&R2: {x1, x3} <-> {y2} -- not in the list because x1 and x3 belongs to the same
                            group
R1&R5: {x1, y2} <-> {y2} -- not in the list because the left hand of R2, y2
                            appears in the right hand of R1

이제 각 세트에서 어떤 옵션이 가능한지 봅시다.

Minimum Set: (x2), (), (z1, z2, z3)    
CC1: (x1), (), (z1, z2, z3) -- replace G1 with x1, remove y2 from G2
CC2: (x3), (), (z1, z2, z3) -- replace G1 with x3, remove y2 from G2
CC3: (x2), (y1), (z2, z3)   -- replace G2 with y1, remove z1 from G3
CC4: (x1), (y1), (z2, z3)   -- replace G1 with x1, G2 with y1, remove y2 and z1
CC5: (x3), (y1), (z2, z3)   -- replace G1 with x3, G2 with y1, remove y2 and z1
CC6: (x2), (y2), (z1)       -- replace G2 with y2, remove z2 and z3 from G3

이제 추가해 봅시다 :

C(Minimum Set) = 1 * 0 *3 = 0
CCC1 = 1 * 0 * 3 = 0
CCC2 = 1 * 0 * 3 = 0
CCC3 = 1 * 1 * 2 = 2
CCC4 = 1 * 1 * 2 = 2
CCC5 = 1 * 1 * 2 = 2
CCC6 = 1 * 1 * 1 = 1

C(Minimum Set) + CCC1 + CCC2  + CCC3 + CCC4 + CCC5 + CCC6
0              + 0    + 0     + 2    + 2    + 2    + 1    = 7

여기에 한 가지 생각을 추가하겠습니다. 5 개의 규칙에 대해 6 개의 CCC 만 있지만, 달리 예상되는 32 가지 용어보다 훨씬 적지 만,이 CCC는 2^n 최악의 시간으로 계산됩니다. 각 규칙에 대해 지금까지 생성 된 모든 CCC와 비교하고 결합해야하기 때문입니다. 규칙이 결합되면 비트가 설정되고 그렇지 않은 경우 설정하지 않은 경우 이진 번호로 생각할 수 있습니다.

그러나 양립 할 수없는 조합은 즉시 폐기되므로 각 새로운 규칙이 결합 될 경우 이미 유효하지 않은 것으로 간주되는 조합에서는 시간이 손실되지 않습니다. 또한, 규칙을 사전에 정렬함으로써 동일한 그룹의 연속 규칙은 올바른 데이터 구조로 비 호환성을 테스트하지 않고 버릴 수 있습니다.

이 특정 예에서 알 수 있듯이 평균 시간은 2^n보다 훨씬 우수 할 수 있습니다.

대체 알고리즘 및 고려 사항

2-SAT와 3-SAT가 돌아 다니는 이야기가 있습니다. 나에게 이것은 모든 제약 a <> b가 실제로 "! a ||! b"라는 의미에서 2-sat 문제인 것 같습니다. 따라서 모든 제약은 함께 "(! x1 ||! y2) && (! x1 ||! z4) && (! y2 &&! z3)"등으로 작성 될 수 있습니다. 각 옵션에 부울 할당이 있는지 확인할 수 있다는 점 에서이 사실을 알 수 있습니다.. 슬라이드 프레젠테이션과 함께 Aspall, Plass 및 Tarjan의 선형 알고리즘이 있습니다. 여기.

그러나 제약을 해결할 수 있는지 아는 것 요청한 것이 아닙니다. 묻는 것은 숫자 2-SAT 문제를 진실하게 유지하면서 모든 옵션을 설정할 수있는 방법.

이제 2-SAT 문제를 만족시키는 방법을 계산하기위한 효율적인 알고리즘이 있습니다. 예를 들어, 이 종이 1.2561에서 실행되는 알고리즘을 제시합니다^N. 하지만 이것조차도 우리가 알아야 할 때 우리를 도와주지 않을 것입니다 무엇 솔루션은 해당 솔루션을 만족시키는 조합 수를 계산할 수 있어야합니다.

Wikipedia에 따르면 이 종이 모든 솔루션을 효율적으로 열거하는 알고리즘이 있습니다. 이것이 우리가 원하는 것입니다. 그러나 계산이 이미 지수 인 경우 열거됩니다. 2보다 낫다^N, 아마도, 그러나 여전히 지수.

2-SAT 문제에 대한 모든 솔루션을 열거하는 경우 각 그룹의 조합 수에는 1로 제공됩니다. 무료 옵션의 수, 어떤 제약 조건에 나타나지 않는 옵션, 각 그룹의 옵션이 선택되지 않은 옵션이 제공됩니다. 솔루션에 의해.

예를 들어, 이전 그룹과 제약 조건을 취합니다. 상호 배제를 포함한 2-SAT 문제는 다음과 같습니다.

(! x1 ||! y2) && (! x3 ||! y2) && (! y1 ||! z1) && (! y2 ||! z2) && (! y2 ||! z3) && (! x1 || ! x3) && (! y1 ||! y2) && (! z1 ||! z2) && (! z1 ||! z3) && (! z2 ||! z3)

첫 번째 줄은 5 가지 규칙입니다. 두 번째 줄은 제약 규칙에 나타나는 동일한 그룹의 모든 옵션을 상호 배제하는 것입니다.

이 2-SAT 문제에 대한 솔루션은 다음과 같습니다.

x1    x3    y1    y2    z1    z2    z3    Combinations
true  false true  false false true  false 1
true  false true  false false false true  1
true  false true  false false false false 0
true  false false false true  false false 0
true  false false false false true  false 0
true  false false false false false true  0
true  false false false false false false 0
false true  true  false false true  false 1
false true  true  false false false true  1
false true  true  false false false false 0
false true  false false true  false false 0
false true  false false false true  false 0
false true  false false false false true  0
false true  false false false false false 0
false false true  false false true  false 1
false false true  false false false true  1
false false true  false false false false 0
false false false true  true  false false 1
false false false true  false false false 0
false false false false true  false false 0
false false false false false true  false 0
false false false false false false true  0
false false false false false false false 0

처음 두 솔루션에서는 선택한 옵션이없는 그룹이 없으므로 조합 수는 1입니다. 세 번째 솔루션은 그룹 G3에 대해 선택된 옵션이 없으므로 "False로 시작하는 선에서 1 곡을 곱합니다. false ", 그룹 G1에 대해 선택한 옵션이없고 하나의 무료 옵션이 있습니다 : x2. 따라서 G2 또는 G3에 대해 선택한 옵션이없는 경우 1에 1을 곱하고 0만큼 곱합니다 (이 경우 무료 옵션 수는 0).

이제 각 그룹에서 선택되는 하나의 옵션을 어떻게 시행하고 여전히 2-SAT라고 주장하는지에 대한 의문이 있습니다. 언급 한 바와 같이, 문제는 두 가지 암시 적 제약 조건을 가지고 있습니다. 각 그룹에 대해 하나의 옵션이 선택된 옵션이 있어야합니다. 이 두 가지 제약은 다음과 같이 쓸 수 있습니다.

엑스₁ || 엑스₂ || 엑스₃ (옵션 x가있는 그룹 X의 경우₁ .. x₃)
(!엑스₁ || !엑스₂) && (! x₁ || !엑스₃) && (! x₂ || !엑스₃)

이후의 제약은 2-sat이고, 전자는 사소한 사례의 경우 3-SAT입니다. 이런 일이 발생하면 첫 번째 제약 조건을 시행하지는 않지만 카운트는 0이됩니다. 계산 알고리즘은 다음과 같이해야합니다.

제약 조건이없는 조합의 경우 각 그룹의 제약 조건이없는 옵션의 수를 서로 곱하십시오.
제약 조건 조합의 경우 다음 카운트의 결과를 추가하십시오.
- 각 솔루션에 대해 서로 "true"로 평가 된 옵션없이 각 그룹의 제약 조건이없는 옵션의 수를 곱하십시오.

따라서 적어도 하나의 제약 조건이없는 옵션이있는 모든 그룹에 대해 선택은 암시적이고 익명입니다. 모든 옵션이 일부 제약 조건의 일부인 모든 그룹에 대해, 옵션이 선택되지 않으면 해당 그룹의 카운트는 0이되므로 해당 솔루션의 조합 횟수도 0이됩니다.

이것은 유효한> 2-sat 제약 조건에서 문제를 속이는 것처럼 느껴집니다. 결국, 이것이 가능하다면, 3-SAT 문제는 솔루션을 2-SAT 부분에 열거 한 다음 그것의 3-sat 부분을 만족시키지 않는 모든 것을 폐기함으로써 해결 될 수 있습니다. 아아, 내가 식별 할 수있는 근본적인 차이가 하나 있습니다.

문제의 2-SAT 부분에 의해 해결되지 않은 모든 곤경은 더 이상의 제약이 없다.

조항에 대한 이러한 제한적인 제약 조건을 감안할 때, 우리는 2-SAT 명시 적 제약 조건에 솔루션을 열거 하여이 문제를 해결할 수 있습니다.

누군가 더 이것을 추구하고 싶다면 계속하십시오. 나는 2의 개선에 만족한다^N 솔루션 나는 제안했다.

다른 팁

당신이 가지고 있다면 N 각각 옵션 그룹 Xi 옵션 (0<=i<N) 그 다음에

X0*X1*...*X(N-1)

원하는 대답을 제공합니다. 즉, 각 옵션 그룹의 크기를 곱하십시오.

당신이 가지고 있다면 n 매개 변수 Ci 각 매개 변수에 대한 가능한 값 m 제약 조건, 구성 수의 상한은 다음과 같습니다 (제약을 무시).

N0 = C1 * C2 * ... * Cn

양식의 단일 제약 ci == x => cj != y 다음 수의 구성을 비활성화합니다.

        N
Dk = -------
     Ci * Cj

따라서 구성 수는 제약 조건을 무시하는 상한에서 허용되지 않은 구성을 빼서 얻습니다.

N = prod(Ci, i = 1...n) * (1 - sum(1 / (Cxj * Cyj), j = 1...m))

여기 xj 그리고 yj 두 매개 변수 지수입니다 j-제약 조건.

예시

Parameters    n = 4

Parameter 1   C1 = 4   0 1 2 3 
Parameter 2   C2 = 3   4 5 6 
Parameter 3   C3 = 2   X Y
Parameter 4   C4 = 3   7 8 9

Constraints   m = 2

Constraint 1  c2 == 4 => c3 != X
Constraint 2  c3 == X => c4 != 9

N0 = 4 * 3 * 2 * 3 = 72

D1 = 72 / (3 * 2) = 12
D2 = 72 / (2 * 3) = 12

N = 72 - (12 + 12) = 48

업데이트

제약 조건의 종속성을 설명하지 않기 때문에 이것이 아직 완전하게 정확하지 않다고 생각합니다.

~~일반적인 경우에는 바로 가기가 없습니다.~~ 생각만큼 나쁘지 않습니다. 아래의 "다시 생각"을 참조하십시오.

2^n이 정말 나쁘니? 여기서 우리는 몇 개의 제외 규칙에 대해 이야기하고 있습니까? 일련의 규칙/옵션 세트가 끊임없이 즉석에서 바뀌고 동적 재 계산이 필요하지 않는 한, 각 구성기에 대해 한 번만이 작업을 수행하면됩니다. 실제로 수많은 규칙이 있다면 정확한 해결책을 찾지 못할 것입니다. KTH 주문 교차로 만 고려하고 "조합 수는 적어도/대부분입니다 ..."라고 말합니다. 답에 대한 경계를 빠르게 도출 할 수있는 다른 체 메소드가있을 수 있습니다.

또한 명심하십시오 : 실제로 필요한 제외 만 고려하면 2^N은 단지 상한 일 뿐이며 실제 계산 수는 실제 시나리오에서 훨씬 적을 수 있습니다. 즉, C [1,2]가 0이면 C [1,2, ...]도 마찬가지입니다. 이것을 고려하십시오 : 각 제약 조건에 대해 공통 옵션을 공유하면 "덩어리"세트가 함께 모입니다. 실제 실행 시간은 가장 큰 "덩어리"의 크기 (예, N만큼 클 수 있음)의 크기로 정의 될 것임이 분명합니다.

다시 생각합니다: c [x, y]는 0이 될 것입니다. 대부분 케이스. 제약은 다음과 같은 다른 제약과 겹칠 수 있습니다. 다른 그룹. 다시 말해, (x1 <-> y1)은 (x1 <-> z1) 또는 (y1 <-> z2) 또는 (x1 <-> y2) 와만 겹칠 수 있습니다. 마찬가지로, 일련의 제약은 새로운 그룹과 겹칠 수 있습니다. 콤비네이션 (y1 <-> z2)와 (x1 <-> y1)의 (x3 <-> z2)는 (x3 <-> z2)와 상호 작용하지 않습니다 (X 그룹은 이미 x1로 고정되어 있음). 조합에 추가하는 각 규칙이 믹스에 이전에 설치된 그룹을 추가하는 경우 포함/제외 만 고려하면됩니다. 그래서 당신은 실제로 O입니다 (2^G), 여기서 G는 그룹의 수입니다 (아마도 그룹의 크기에 따라 다른 경계). 훨씬 더 관리하기 쉽습니다!

편집하다

이 알고리즘이 잘못되었습니다. 나는 다른 게시물에서 여전히 2^n이 더 나쁜 경우에 대체 답변을 제시했지만 그렇지 않으면 더 나은 결과를 줄 수 있습니다.

y2는 x1의 배제 세트의 일부이고 두 개의 첫 번째 제약 조건은 x1을 기반으로하기 때문에 예제 선택에서 작동합니다. 아직도, 나는 이제 무엇을 해야하는지 봅니다. 여전히 2^N에 가깝지만 상당한 이익을 얻을 수있는 최적화가 있습니다.

이 알고리즘을 수정하려면 구성된 규칙은 양식 세트 (OX) <-> 세트 (OY)이어야합니다. 그것들을 구성하려면, 당신이 구성하는 왼손 황소로 각각의 제약에 대해, 당신은 이미 구성한 각 규칙에 따라 다른 구성을 만듭니다. 황소가 구성된 규칙의 오른쪽의 일부가 아니거나 그룹의 왼쪽과 동일하다면.

완전히 독립적 인 제약의 경우, 이것은 2^n입니다. 그렇지 않으면, 당신은 다음을 통해 n을 줄입니다.

일반적인 왼쪽으로 제약을 통일합니다
상호 배타적 인 규칙 조합을 계산하지 않으면 다음과 같이 나뉩니다.
- 같은 그룹의 옵션 규칙을 결합하지 않습니다
- 하나의 왼쪽이 다른 쪽의 오른쪽에 나타나는 규칙을 결합하지 않음

이 알고리즘을 고치는 것이 그만한 가치가 있다고 생각하지 않습니다. 오히려 기억이 나고, 대체 대답과 동일한 순서를 가질 것입니다.

최종 편집

이걸 돌리자. 알고리즘은 어떻습니까 :

규칙을 위해 필요한 경우 규칙을 수정하십시오 o1 <-> o2, group(o1) < group(o2)
모든 규칙을 접어 "작성된"규칙을 계산합니다 oX <-> o? 단일 규칙으로 oX <-> Set(o?)
모든 규칙의 왼쪽 옵션을 제거하여 "깨끗한"그룹 세트를 계산합니다.
왼쪽 옵션 그룹을 왼쪽 옵션 자체로 바꾸고 다른 그룹에서 규칙의 오른손 옵션을 빼서 정리 세트에서 대체 세트를 계산합니다.
각 그룹 세트에 대해 세트의 각 그룹의 옵션 수를 곱하여 조합 수를 계산하십시오.
5 단계의 모든 결과를 추가하십시오.

직장에서 이것을 보자 :

Group 1:
x1 x2 x3 x4 x5

Group 2:
y1 y2 y3

Group 3:
z1 z2 z3 z4

Constraints (already fixed):
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

Composed rules:
x1 <-> (y2, z4)
y2 <-> (z2)

Clean set of groups:
x2x3x4x5, y1y3, z1z2z3z4

Alternate sets:
x1, y1y3, z1z2z3 (first composed rule)
x2x3x4x5, y2, z1z3z4 (second composed rule)

Totals:
4 * 2 * 4 = 32
1 * 2 * 3 = 6
4 * 1 * 3 = 12

Total: 50

이제이 알고리즘이 잘못되었을 수 있습니다. 지금, 나는 그것이 정확하거나 다른 방식으로 증명하기에 충분히 명확하게 생각할 수 없다. 나는 너무 오랫동안 문제에 너무 가까웠다. 그러나 예제에 반대하는 것을 확인해 봅시다.

c(no rules) = 60
c1 => 4
c2 => 3
c3 => 5
c12 => 1
c13 => 1
c23 => 0
c123 => 0

c(no rules) - c1 - c2 - c3 + c12 + c13 + c23 - c123 = 50

내 알고리즘이 정확하다면 다항식 인 것 같습니다. 다시 한 번, 지금은 명확하게 생각할 수 없으며 세트에서 조작의 큰 O를 고려해야합니다.

다음은 Scala 구현입니다.

case class GroupOption(id: Int, option: Int)
case class Group(id: Int, options: Set[Int])
case class Rule(op1: GroupOption, op2: GroupOption)
case class ComposedRule(op: GroupOption, set: Set[GroupOption])

object ComputeCombinations {
  def fixRules(rules: Set[Rule]) = {
    rules map (rule => if (rule.op1.id > rule.op2.id) Rule(rule.op2, rule.op1) else rule)
  }

  def ruledOptions(id: Int, rules: Set[Rule]): Set[Int] = (
    rules 
    filter (rule => rule.op1.id == id)
    map (rule => rule.op1.option)
  )

  def cleanseSet(groups: Set[Group], rules: Set[Rule]) = {
    groups map (group => 
      Group(group.id, group.options -- ruledOptions(group.id, rules)))
  }

  def composeRules(rules: Set[Rule]): Set[ComposedRule] = Set(
    (
      rules.toList
      sort (_.op1.id < _.op1.id)
      foldLeft (List[ComposedRule]())
      ) { (list, rule) => list match {
        case ComposedRule(option, set) :: tail if option == rule.op1 =>
          ComposedRule(option, set + rule.op2) :: tail
        case _ => ComposedRule(rule.op1, Set(rule.op2)) :: list
      }} : _*
  )

  def subset(groups: Set[Group], composedRule: ComposedRule) = (
    groups
    filter (_.id != composedRule.op.id)
    map (group => Group(group.id, group.options -- 
                                  (composedRule.set 
                                   filter (_.id == group.id)
                                   map (_.option)
                                  )))
  )

  def subsets(groups: Set[Group], composedRules: Set[ComposedRule]) = (
    composedRules map (composedRule => subset(groups, composedRule))
  )

  def combinations(groups: Set[Group]) = (
    groups.toList map (_.options.size) reduceLeft (_*_)
  )

  def allCombinations(groups: Set[Group], rules: Set[Rule]) = {
    val fixedRules = fixRules(rules)
    val composedRules = composeRules(fixedRules)
    val cleanSet = cleanseSet(groups, fixedRules)
    val otherSets = subsets(cleanSet, composedRules)
    val allSets = otherSets + cleanSet
    val totalCombinations = allSets.toList map (set => combinations(set)) reduceLeft (_+_)
    totalCombinations
  }
}

object TestCombinations {
  val groups = Set(Group(1, Set(1, 2, 3, 4, 5)),
                   Group(2, Set(1, 2, 3)),
                   Group(3, Set(1, 2, 3, 4)))
  val rules = Set(Rule(GroupOption(1, 1), GroupOption(2, 2)),
                  Rule(GroupOption(1, 1), GroupOption(3, 4)),
                  Rule(GroupOption(2, 2), GroupOption(3, 2)))
  def test = ComputeCombinations.allCombinations(groups, rules)
}

이것은 직접 유용한 답변이 아닐 수도 있으므로 무시하십시오 ... 그러나; 나는 현재 비슷한 시스템을 직접 일하지 않습니다. 그리고 솔직히 사소한 사례 외에 유효한 조합의 수를 계산하는 것이 유용한지 확실하지 않습니다. 예를 들어, 현재 진행중인 모델에는 18000 개의 후보자 항목이 80 개 이상의 선택, 일부 단일 선택 / 일부 다중 선택이 있습니다. 가장 작은 모델 외에도 아니요 혜택 그 숫자를 아는 경우, 당신은 단순히 그것을 완전한 진실 테이블로 쓰지 않을 것입니다. 당신은 꽤 많이 있습니다 강요된 규칙을 실행하려면 (예 : 더 이상 유효하지 않은 것을 제거하고, 적절한 것으로 자동 선택하고, 규칙이 깨지지 않았는지 확인하십시오) 주문형. 반드시 문제는 아닙니다. 내 현재 코드는이 모델 (웹 서비스로)을 ~ 450ms로 처리하며, 대부분 입력/출력을 위해 XML을 처리하는 데 소요되는 시간입니다. 입력/출력이 XML이 아니라면 ~ 150ms라고 생각합니다.

나는 고용주가 엔진을 오픈 소스하도록 설득하고 싶습니다. 그러나 그것은 또 다른 날을위한 전투입니다.

x^n이 아닌 경우, n은 옵션 수이고 x는 옵션 당 선택의 수입니까?

Zac가 올바른 방향으로 생각하고 있다고 생각합니다. 조합 수에 대한 표현식을 살펴보면 2 차 용어 CR [I, J]가 C [k] 용어보다 훨씬 작음을 알 수 있습니다. 각 축이 옵션 그룹 인 큐브를 상상해보십시오. 큐브의 각 지점은 특정 옵션 조합을 나타냅니다. 첫 번째 순서 C [k] 보정은 큐브의 두 표면 사이에 옵션 라인을 제외합니다. 2 차 수정 C [I, J]는 큐브의 공간에서 두 개의 선이 한 지점 (옵션 조합)에서 만나면 발생합니다. 따라서 보유한 그룹의 수에 관계없이 고차 수정은 항상 점점 더 작아집니다. 당신이 고수한다면

조합 = C (규칙 없음) -Cr [1] -Cr [2] -Cr [3

조합 수에 대한 하한으로 끝납니다. 1 차 수정의 크기를 알았으므로 위의 큐브에 대한 관찰에 대한 생각을 생각하면 2 차 수정의 크기를 추정 할 수도 있습니다. 그룹 수에 따라 다릅니다. 그런 다음 알고리즘은 더 높은 주문을 계속할 것인지 여부를 결정할 수 있습니다.

댓글 다니엘의 게시물:

알고리즘은 좋아 보이지만 실제로 효과가 있었기 때문에 스칼라를 설치하고 테스트를했습니다. 불행히도 나는 올바른 결과를 얻지 못한다.

예를 들어이 사례를 고려하십시오.

Group 1:
a1 a2 a3 a4 a5

Group 2:
b1 b2 b3

Group 3:
c1 c2 c3 c4

Group 4:
d1 d2 d3 d4 d5

Rules:
a1 <-> b2
a1 <-> c2
b2 <-> c2
b2 <-> d1
a2 <-> d2

이 구성으로 기본 체계 알고리즘을 구성하고 다음 결과를 얻었습니다.227 조합) :

Without rules => 300
Rules: [1] => 20
Rules: [2] => 15
Rules: [3] => 25
Rules: [4] => 20
Rules: [5] => 12
Order: 1 => 208 (diff: -92)
Rules: [1, 2] => 5
Rules: [1, 3] => 5
Rules: [2, 3] => 5
Rules: [1, 4] => 4
Rules: [2, 4] => 1
Rules: [3, 4] => 5
Rules: [1, 5] => 0
Rules: [2, 5] => 0
Rules: [3, 5] => 1
Rules: [4, 5] => 0
Order: 2 => 234 (diff: 26)
Rules: [1, 2, 3] => 5
Rules: [1, 2, 4] => 1
Rules: [1, 3, 4] => 1
Rules: [2, 3, 4] => 1
Rules: [1, 2, 5] => 0
Rules: [1, 3, 5] => 0
Rules: [2, 3, 5] => 0
Rules: [1, 4, 5] => 0
Rules: [2, 4, 5] => 0
Rules: [3, 4, 5] => 0
Order: 3 => 226 (diff: -8)
Rules: [1, 2, 3, 4] => 1
Rules: [1, 2, 3, 5] => 0
Rules: [1, 2, 4, 5] => 0
Rules: [1, 3, 4, 5] => 0
Rules: [2, 3, 4, 5] => 0
Order: 4 => 227 (diff: 1)
Rules: [1, 2, 3, 4, 5] => 0
Order: 5 => 227 (diff: 0)

***Combinations: 227***

그러나 스칼라 에서이 코드를 사용합니다.

  val groups = Set(Group(1, Set(1, 2, 3, 4, 5)),
                   Group(2, Set(1, 2, 3)),
                   Group(3, Set(1, 2, 3, 4)),
                   Group(4, Set(1, 2, 3, 4, 5)))

  val rules = Set(Rule(GroupOption(1, 1), GroupOption(2, 2)),
                  Rule(GroupOption(1, 1), GroupOption(3, 2)),
                  Rule(GroupOption(2, 2), GroupOption(3, 2)),
                  Rule(GroupOption(2, 2), GroupOption(4, 1)),
                  Rule(GroupOption(1, 2), GroupOption(4, 2)))

나는 답을 얻었다 258.

체계에서 계산을 확인했는데 옳은 것 같습니다. 아마도 알고리즘을 수정할 수 있습니까? 나는 실제로 무엇이 잘못되었는지에 손가락을 넣을 수 없습니다.

당신의 문제는 다소 무관심합니다.

솔루션 수를 계산하는 것은 모든 방사성 그룹을 두 가지 옵션으로 제한하더라도 #P-Complete입니다.
제약 조건과 일치하는 옵션 선택이 있는지 확인하면 NP가 완성됩니다.
모든 방사성 그룹을 두 가지 옵션 (2SAT)으로 제한하는 경우 제약 조건과 일치하는 옵션을 선택할 수 있는지 확인하십시오.

따라서 일반적으로 다항식 알고리즘에 의존하지 않습니다. 이러한 알고리즘의 존재는 p = np를 의미합니다.

할 수있는 일 :

근사 알고리즘을 사용하십시오. 내가 링크 한 Wikipedia 기사에 따르면 종종 그들에게는 의심됩니다.
SAT 솔버를 사용하십시오 http://en.wikipedia.org/wiki/sat_solver 또는 계산을위한 관련 도구 (불행히도 나는 모른다); 사람들은 많은 휴리스틱을 만들었으며 그 프로그램은 일반적으로 수제 솔루션보다 훨씬 빠릅니다. SAT 경쟁도 있습니다. 따라서이 분야는 현재 매우 빠르게 확장되고 있습니다.
그러한 일반성이 필요한지 확인하십시오. 아마도 당신의 문제에는 추가적인 가정이있을 수 있으며, 이는 복잡성을 바꿀 것입니다.

증명 :

솔루션 수를 계산하는 것은 #P 인 것으로 쉽게 표시되므로 2SAT를 줄이기에 충분합니다. 2SAT 인스턴스를 사용하십시오

(P1 여부) 및 (P2) 또는 P3)

사용자가 P1, P2, P3 값을 선택할 수 있습니다. 이를 해결할 수있는 제약 조건을 쉽게 형성 할 수 있습니다. 따라서 가능한 구성의 수 = P1, P2, P3의 가능한 할당 수는 부울 공식을 사실로 만듭니다.

일부 옵션 선택이 허용되는지 쉽게 확인할 수 있으므로 NP이므로 3SAT를 줄이기에 충분합니다. 같은 3SAT 인스턴스를 사용하십시오

(P1 또는 P2 또는 P3) 및 (P2 또는 P1 또는 P4)

옵션 제공 :

그룹 P1 p1true p1false

그룹 P2 p2false p2true

그룹 P3 p3false p3true

그룹 P4 p4false p4true

그룹 조항 _1 C1A C1B C1C

그룹 조항 _2 C2A C2B C2C

clause_1은 첫 번째 조항을 제어합니다 : (P1 또는 P2 또는 P3). 정확히, p1true가 선택되면 C1A를 점검 할 수 있고, p2true가 선택되면 C1B는 검사 할 수 있으며, p3false가 선택된 경우 C1C를 점검 할 수 있습니다. 따라서 제약은 다음과 같습니다.

p1false <-> c1a

P2FALSE <-> C1B

p3true <-> c1c

clause_2와 동일하며, 상수는입니다

P2FALSE <-> C2A

p1true <-> c2b

P4false <-> C2C

사용자가 모든 답변을 선택할 수있는 경우 (구성 수는> 0이면) 변수 P1, ..., P4의 일부 평가가 있음을 증명할 것입니다. 반대로, 사용자가 가정과 일치하는 답변을 선택할 수 없으면 (사용 가능한 구성 = 0) 3SAT 인스턴스는 만족스럽지 않습니다. 따라서 대답이> 0인지 아는 것은 3SAT 인스턴스가 해결 될 수 있는지 아는 것을 의미합니다.

물론이 감소는 다항식 시간입니다. 증거의 끝.

대답이 0 일 수 있다는 사실에 만족하지 않는다면 : 그러한 구성자를 무시하는 경우 여전히 NP-HARD입니다. ( "가짜"옵션을 모든 그룹에 추가하고 "가짜"가 선택되지 않은 경우 기하 급수적으로 많은 선택을 허용 할 것입니다. 이것은 더 복잡하기 때문에 요청에 따라 할 것입니다.)

이것은 위의 SDCVVC의 훌륭한 답변에 간략하게 언급되지만 Monte Carlo 근사가 충분할 수 있습니까? N 무작위 구성을 생성하십시오 (여기서 N이 선택되어 실험의 힘이 충분히 높도록 선택됩니다. 나머지 구성 공간에 비례를 외삽하십시오.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow