Numero di combinazioni nel configuratore

https://stackoverflow.com/questions/1154565

18-09-2019
|

Domanda

Mi è stato chiesto di programmare una routine per decidere il numero di combinazioni possibili in un configuratore di prodotto.

Il configuratore è davvero semplice.Anche se ha più funzionalità di queste, può essere modellato come diversi "gruppi radio" (come il controllo dell'interfaccia utente) in cui deve essere selezionata una delle n opzioni.

L'unico tipo di vincolo che può essere utilizzato sono le regole che dicono che se viene selezionata un'opzione non è possibile selezionarne un'altra.

Quindi quello che voglio fare è calcolare il numero di prodotti diversi che possono essere configurati, dato un insieme di gruppi di opzioni e vincoli.

Ho adottato un approccio ingenuo per risolvere questo problema utilizzando il file Principio di inclusione-esclusione.Tuttavia, per quanto posso vedere, qualsiasi algoritmo basato su questo metodo dovrebbe essere eseguito in O(2^n) che non funzionerà.Ci sono ovviamente diverse possibili ottimizzazioni che dovrebbero fornire tempi di autonomia decenti, ma ci sono ancora scenari peggiori facilmente costruibili.

È più o meno dove mi trovo adesso.Eventuali suggerimenti?

Aggiornamento

Mi rendo conto di non aver spiegato abbastanza bene come si applicano le regole.

Esistono diversi gruppi con opzioni.In ciascun gruppo deve essere selezionata una ed una sola opzione.Possono esserci una o più opzioni in un gruppo.

Esiste un solo tipo di vincoli.Se è selezionata l'opzione A in alcuni gruppi, l'opzione B in altri gruppi non potrà essere selezionata.Può esserci un numero qualsiasi di vincoli, non esiste alcun limite al numero di vincoli/regole applicabili a un gruppo di opzioni o a un'opzione stessa.

Quindi un esempio potrebbe essere:

Gruppo 1:
x1x2x3x4x5

Gruppo 2:
y1 y2 y3

Gruppo 3:
z1 z2 z3 z4

Vincoli:
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

* Se nel gruppo 1 è selezionata l'opzione x1, non è possibile selezionare l'opzione y2 nel gruppo 2.

Usando inclusione-esclusione calcolerei il numero di combinazioni come

Combinazioni = C_{senza regole} - C_R[1] - C_R[2] -C_R[3]+C_R[1,2] + C_R[1,3] + C_R[2,3] -C_R[1,2,3]

Dove

C_{senza regole} = 5 * 3 * 4

C_R[a,b,c] = Numero di combinazioni che violano le regole a, b e c.

Il metodo purtroppo richiede 2^| regole | calcoli.

Soluzione

Ok, non posso aggirare 2^N, ma posso ridurre il set di campioni.Per fare ciò, calcoleremo i "Vincoli composti".Un vincolo composto è un vincolo in cui, se vengono selezionate tutte le opzioni sul lato sinistro, nessuna delle opzioni sul lato destro può essere selezionata, ma non può essere applicato nessun altro vincolo basato sulle opzioni sul lato sinistro.

Dobbiamo calcolare un insieme di tutti i possibili vincoli composti da un insieme di vincoli.Sebbene non sia necessario, "risolveremo" i vincoli esistenti scambiando la mano sinistra con quella destra se il gruppo della mano destra è più piccolo del gruppo della sinistra.Ciò può ridurre alcuni vincoli composti, sebbene siano possibili euristiche migliori per lo scambio.

Dobbiamo anche calcolare un "insieme minimo" di opzioni che possono essere scelte arbitrariamente per ciascun gruppo.Questo insieme minimo viene calcolato rimuovendo dall'elenco delle opzioni disponibili tutte le opzioni che appaiono a sinistra di un vincolo composto.

Segue un algoritmo, ma non sto dimostrando che calcoli correttamente i CC.Dimostrerò che, se così fosse, allora possono essere usati per calcolare il numero di combinazioni possibili.

Fissare i vincoli in modo che il gruppo della mano sinistra sia inferiore o uguale al gruppo della mano destra.
Comporre i vincoli:
1. Ordina i vincoli con la mano sinistra
2. In sequenza, per ciascun vincolo:
  1. Piegare il vincolo con tutti i vincoli che lo seguono con la stessa mano sinistra, girando x1 <-> y1, x1 <-> y2 ... x1 <-> yN in Set(x1) <-> Set(y1 ... yN)
  2. Comporre il vincolo piegato con ciascun vincolo già piegato, se:
    - x1 non è nella mano destra del vincolo già piegato
    - x1 non è nello stesso gruppo di nessun elemento nella mano sinistra
  3. Aggiungi il vincolo piegato e tutte le sue composizioni all'insieme dei vincoli piegati
Calcola l'insieme minimo, prendendo tutte le opzioni e rimuovendo quelle che appaiono nella mano sinistra dei vincoli fissi.

Ora puoi calcolare il numero di combinazioni con la formula seguente.Chiamiamo CC un vincolo composto.Quindi il numero di combinazioni è:

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

Dove:

C(Set Minimo) è il numero di combinazioni possibili con il set minimo.
CCCx è il numero di combinazioni possibili prendendo il set minimo, sostituendo eventuali gruppi per i quali esiste un'opzione a sinistra di CCx con quell'opzione e quindi rimuovendo eventuali opzioni a destra di CCx.

Si noti che l'espressione è puramente additiva.Ciò significa che, affinché l'espressione produca il risultato atteso, devono essere vere le seguenti due condizioni:

Non esistono due termini che contengano la stessa combinazione.
Tutte le combinazioni devono essere prese in considerazione da questi termini.
Nessun termine può fornire alcuna combinazione non valida.

Per la prima dimostrazione, si noti che non esistono due CC distinti con la stessa mano sinistra.Se due CC avessero la stessa mano sinistra ma una mano destra diversa, ciò significherebbe che c'è un vincolo di addizione che deve applicarsi a uno dei CC, o un vincolo non valido applicato all'altro.

Poiché non ci sono due CC con la stessa mano sinistra, e il set minimo non contiene la mano sinistra di nessun CC per definizione, allora due CC qualsiasi possono essere distinti da almeno un'opzione che è selezionata per l'uno ma non per l'altro .Pertanto, due CC non possono produrre la stessa combinazione.

Per la seconda dimostrazione, si noti che l'insieme dei CC contiene, per definizione, tutte le combinazioni valide per le opzioni della mano sinistra.

Supponiamo che esista una combinazione che non appare né nell'insieme minimo né nell'insieme dei CC.Se questa combinazione non contiene alcuna opzione della mano sinistra, allora deve essere una combinazione del set minimo, per definizione.Pertanto, deve contenere opzioni dalla mano sinistra.

Poiché l'insieme dei CC contiene tutte le combinazioni valide per la mano sinistra, esiste un CC con le stesse opzioni per la mano sinistra.Questa combinazione deve quindi avere un'opzione che non sia inclusa in nessuna combinazione per quel CC.Ma le uniche opzioni non incluse in quel CC sono quelle che appaiono nella mano sinistra per gli altri CC, e quelle che devono esserne escluse per vincoli.Poiché nessuno dei due può essere il caso, questa combinazione non può esistere.

Per la terza dimostrazione consideriamo innanzitutto l'insieme minimo.Il set minimo non contiene alcuna opzione nella mano sinistra di nessun gruppo.Poiché tutti i vincoli sono compresi tra un'opzione a sinistra e una a destra, non si applica alcun vincolo all'insieme minimo.

Consideriamo ora i CC.Un CC ha una combinazione valida di opzioni della mano sinistra per definizione.Qualsiasi opzione incompatibile con quella mano sinistra deve apparire nella mano destra e qualsiasi opzione di quella mano destra deve essere rimossa dal set minimo.Poiché nessuna opzione sull'insieme minimo era incompatibile tra loro fin dall'inizio, non può esserci alcun vincolo insoddisfatto in nessuna combinazione su un CC.

E questo conclude la dimostrazione.

Vediamo come si applica con un esempio dai commenti:

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}

Soffermiamoci brevemente sui gruppi composti non presenti nell'elenco:

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

Ora vediamo quali opzioni sono possibili in ciascun set:

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

Adesso sommiamo le cose:

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

Aggiungerò qui un ulteriore pensiero.Anche se ci sono solo 6 CCC per 5 regole, molto meno dei 32 termini previsti altrimenti, questi CCC vengono calcolati con 2^N tempo peggiore, poiché, per ciascuna regola, è necessario confrontarla e combinarla con tutti i CCC creati finora.Potresti pensarli come numeri binari, dove un bit viene impostato se la regola viene combinata e non viene impostato altrimenti.

Tuttavia, le combinazioni incompatibili vengono scartate immediatamente, in modo che per ogni nuova regola combinata non si perda tempo su combinazioni già ritenute non valide.Inoltre, ordinando le regole in anticipo, le regole successive nello stesso gruppo possono essere scartate senza nemmeno testare l'incompatibilità, con le giuste strutture dati.

Come mostra questo particolare esempio, il tempo medio può essere molto migliore di 2^N.

Algoritmi alternativi e considerazioni

Si parla in giro di 2-SAT e 3-SAT.Mi sembra che questo sia un problema 2-SAT, nel senso che ogni vincolo a <-> b è in realtà una clausola "!a || !b".Quindi tutti i vincoli insieme possono essere scritti semplicemente come "(!x1 || !y2) && (!x1 || !z4) && (!y2 && !z3)", ecc.Ciò significa che puoi "risolverlo". nel senso che puoi scoprire se esiste un'assegnazione booleana per ciascuna opzione che lo renderà vero.Esiste un algoritmo lineare per questo di Aspall, Plass e Tarjan, con una presentazione di diapositive Qui.

Ma sapere se i vincoli possono essere risolti o meno non è quello che è stato chiesto.Ciò che è stato chiesto è il numero di modi in cui è possibile impostare tutte le opzioni mantenendo vero il problema 2-SAT.

Ora esistono algoritmi efficienti per contare il numero di modi per soddisfare un problema 2-SAT.Ad esempio, questo articolo presenta un algoritmo che viene eseguito in 1.2561^N.Ma anche questo non ci aiuterà, come dobbiamo sapere Che cosa le soluzioni devono essere in grado di calcolare il numero di combinazioni che soddisfano quella soluzione.

Secondo Wikipedia, questo articolo ha un algoritmo che enumera in modo efficiente tutte le soluzioni, che è ciò che vogliamo.Ma se il conteggio è già esponenziale, lo sarà anche l’enumerazione.Meglio di 2^N, forse, ma pur sempre esponenziale.

Se enumeriamo tutte le soluzioni del problema 2-SAT, il numero di combinazioni per ciascun gruppo è dato da 1 moltiplicato per il numero di opzioni libere, opzioni che non compaiono in nessun vincolo, di ciascun gruppo per il quale non è stata selezionata alcuna opzione dalla soluzione.

Ad esempio, prendendo il precedente insieme di gruppi e vincoli.Il problema 2-SAT, inclusa la mutua esclusione, è:

(! X1 ||! Y2) && (! X3 ||! Y2) && (! Y1 ||! Z1) && (! Y2 ||! Z2) && (! Y2 ||! Z3) && (! X1 || ! x3) && (! Y1 ||! Y2) && (! Z1 ||! Z2) && (! Z1 ||! Z3) && (! Z2 ||! Z3)

La prima riga sono le cinque regole.La seconda linea è la mutua esclusione di tutte le opzioni dello stesso gruppo che compaiono nelle regole di vincolo.

Le soluzioni a questi problemi 2-SAT sono:

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

Nelle prime due soluzioni non ci sono gruppi senza opzione selezionata, quindi il numero di combinazioni è 1.La terza soluzione non ha alcuna opzione selezionata per il gruppo G3, quindi moltiplichiamo 1 per 0.Nelle righe che iniziano con "false false", non ci sono opzioni selezionate per il gruppo G1 e un'opzione libera:x2.Quindi moltiplichiamo 1 per 1 per loro e per 0 se non ci sono opzioni selezionate per G2 o G3 (nel qual caso il numero di opzioni libere è 0).

Ora, c'è la questione di come posso imporre un'opzione scelta in ciascun gruppo e affermare comunque di essere 2-SAT.Il problema, come detto, ha due vincoli impliciti:per ogni gruppo deve esserci una, ed una sola, opzione selezionata.Questi due vincoli possono essere scritti come:

X₁ || X₂ || X₃ (per il gruppo x con opzioni x₁ ..X₃)
(!X₁ || !X₂) && (!X₁ || !X₃) && (!X₂ || !X₃)

Il secondo vincolo è 2-SAT, il primo è 3-SAT per qualsiasi caso non banale.Si dà il caso che non applichi il primo vincolo, ma il conteggio diventa 0.L'algoritmo di conteggio dovrebbe essere questo:

Per le combinazioni senza vincoli, moltiplicare tra loro il numero di opzioni senza vincoli in ciascun gruppo.
Per le combinazioni con vincoli completi, aggiungere il risultato dei seguenti conteggi:
- Per ciascuna soluzione, moltiplicare il numero di opzioni senza vincoli in ciascun gruppo senza un'opzione valutata come "vera" l'una dall'altra.

Quindi, per ogni gruppo in cui è presente almeno un'opzione senza vincoli, la selezione è implicita e anonima.Per ogni gruppo in cui tutte le opzioni fanno parte di qualche vincolo, se non è stata selezionata alcuna opzione, il conteggio per quel gruppo diventa 0 e, pertanto, anche il numero di combinazioni per quella soluzione diventa 0.

Sembra come eliminare il problema da un vincolo valido> 2-SAT.Dopotutto, se ciò fosse possibile, allora il problema 3-SAT potrebbe essere risolto semplicemente enumerando le soluzioni della parte 2-SAT e poi scartando tutte quelle che non soddisfano la parte 3-SAT.Ahimè, c'è una differenza fondamentale che posso identificare:

Tutti i predicati non risolti dalla parte 2-SAT del problema sono liberi da ogni ulteriore vincolo.

Dato questo vincolo piuttosto restrittivo sulle clausole, possiamo risolvere questo problema enumerando le soluzioni ai vincoli espliciti 2-SAT.

Se qualcuno vuole approfondire questo argomento, vada avanti.Sono soddisfatto del miglioramento rispetto al 2^N soluzione che ho suggerito.

Altri suggerimenti

Se avete N gruppi di opzioni, ciascuna con le opzioni Xi (0<=i<N) poi

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

Ti dà la risposta che si desidera. In altre parole, moltiplicare la dimensione di ciascun gruppo di opzioni.

Se avete parametri n con Ci valori possibili per ogni parametro e m vincoli, un limite superiore per il numero di configuartions è la seguente (ignorando i vincoli).

N0 = C1 * C2 * ... * Cn

Un unico vincolo della forma ci == x => cj != y non consente il seguente numero di configurazioni.

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

Quindi il numero di configurazione è ottenuto sottraendo i configuartions non riconosciute dal limite superiore ignorando i vincoli.

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

Qui xj e yj sono i entrambi gli indici dei parametri del vincolo j-esimo.

Esempio

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

Aggiorna

Credo che questo non è ancora completamente corretto perché non tiene conto per le dipendenze dei vincoli.

~~Non ci sono scorciatoie qui per il caso generale.~~ Non è così male come si pensa. Vedere "Ripensare" in basso.

E '2 ^ n davvero così male? Quante regole di esclusione stiamo parlando qui? È veramente a che fare solo una volta per ogni configuratore, a meno che l'insieme di regole / opzioni è in continua evoluzione al volo e che richiedono il ricalcolo dinamico. Se c'è davvero un numero enorme di regole, allora non avrebbe cercato una soluzione esatta - in considerazione solo le intersezioni KTH-order e dire "il numero di combinazioni è almeno / la maggior parte ...". Ci potrebbero essere altri metodi setaccio che vi permetterà di trarre rapidamente limiti sulla risposta.

Anche tenere a mente: se si considerano solo le esclusioni che realmente bisogno, quindi 2 ^ n è solo un limite superiore, e il numero effettivo di calcoli può essere significativamente inferiore per eventuali scenari attuali. Cioè, se C [1,2] è zero, allora lo è C [1,2, ...]. Considerate questo: per ogni vincolo, set di "grumo" di vincoli insieme se condividono le opzioni in comune. E 'chiaro che il tempo di esecuzione reale sta per essere definito dalla dimensione del più grande "macchia" (che, sì, può essere grande come n).

Ripensare : C [x, y] sarà zero maggior casi. Un vincolo può sovrapporsi solo con altri vincoli che coinvolgono un diverso di gruppo. In altre parole, (x1 <-> Y1) possono sovrapporsi solo con (x1 <-> Z1) o (Y1 <-> Z2) o qualcosa del genere, non è (x1 <-> Y2). Allo stesso modo, un insieme di vincoli può sovrapporsi solo con un nuovo gruppo: combinazione di (x1 <-> Y1) con (Y1 <-> Z2) non ha alcuna interazione con (x3 <-> Z2) (il gruppo x è già fissato a x1). Basta prendere in considerazione l'inclusione / esclusione in cui ogni regola si aggiunge alla combinazione aggiunge un gruppo precedentemente intatto per il mix. Così si è in realtà O (2 ^G), dove G è il numero di gruppi (e forse anche un diverso limite in base alla dimensione dei gruppi). Molto più gestibile!

Modifica

Questo algoritmo non è corretta. Ho presentato una risposta alternativa in un altro post che è ancora 2 ^ N nel caso peggiore, ma potrebbe dare risultati migliori in caso contrario.

Questo funziona nell'esempio scelto perché y2 è parte della esclusione fissato di x1, e le prime due vincoli sono basati su x1. Eppure, ora vedo che cosa deve essere fatto. E 'ancora vicino al 2 ^ N, ma ci sono ottimizzazioni che possono portare a risultati significativi.

Per risolvere questo algoritmo, le regole devono essere composti del set di modulo (ox) <-> set (oy). Per comporre loro, per ogni vincolare bue a sinistra si compone, è anche fare altre composizioni di esso con ogni regola già composto, se oX non è parte del lato destro della regola composto, né si tratta di gruppo è lo stesso come il lato sinistro del gruppo .

Per vincoli completamente indipendenti, questo è 2 ^ N. In caso contrario, si stanno riducendo N facendo:

unificante vincola con un sinistro comuni
non calcolare le combinazioni di regole che si escludono a vicenda, questo si divide in:
- non combinando le regole per le opzioni nello stesso gruppo
- non combinando le regole in cui appare nella parte sinistra del di uno sul lato destro degli altri

Non credo che la risoluzione di questo algoritmo è valsa la pena. E 'piuttosto la memoria-pesante, e sarebbe lo stesso ordine in cui la mia risposta alternativo, che è molto più leggero.

Fine Modifica

Facciamo girare intorno a questo. Che ne dite di questo per un algoritmo:

regole Fix in modo da assicurare che, per regola o1 <-> o2, group(o1) < group(o2)
Calcola "composti" regole piegando tutte le regole oX <-> o? in un'unica regola oX <-> Set(o?)
calcolare un set "pulita" di gruppi, eliminando dalla loro la possibilità di sinistra di ogni regola
Calcola gruppi alternati dal set pulito, uno per ogni regola composto, sostituendo il gruppo dell'opzione sinistra con l'opzione sinistra stessa, e sottraendo gli altri gruppi alle impostazioni della mano destra della regola.
Per ogni insieme di gruppi, calcolare il numero di combinazioni moltiplicando il numero di opzioni in ogni gruppo nel set.
Aggiungi tutti i risultati dal punto 5.

Vediamo questo al lavoro:

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

Ora, forse questo algoritmo non è corretto. In questo momento, non posso pensare con sufficiente chiarezza a dimostrarlo corretto o meno - sono stato troppo vicino al problema per troppo tempo. Ma diamo un'occhiata contro l'esempio:

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

Se il mio algoritmo è corretto, sembra essere polinomiale. Anche in questo caso, in questo momento non riesco a pensare con sufficiente chiarezza, e avrei bisogno di prendere in considerazione il big-O della manipolazione nei set.

Ecco un'implementazione Scala di esso:

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)
}

Questo potrebbe non essere una risposta direttamente utili, quindi sentitevi liberi di ignorarlo ... tuttavia; Al momento sto lavorando senza un sistema simile me stesso; e francamente non per esempi banali non sono sicuro che sia utile cercare di calcolare il numero di combinazioni valide. A titolo di esempio, i modelli su cui sto lavorando in questo momento hanno (per esempio) 18000 articoli candidati si sviluppa su 80 + selezioni, alcune a selezione singola / un po 'di selezione multipla. Al di là dei modelli più piccoli, non v'è alcuna vantaggio a conoscere il numero, come si farebbe mai semplicemente scriverlo come una tabella di verità piena; siete pretty-più costretto per eseguire le regole (vale a dire rimuovere tutto ciò che non è più valido, auto-selezionare qualsiasi cosa a seconda dei casi, e controllare che non regole vengono infrante) on-demand. Il che non è necessariamente un problema; il mio codice attuale elabora questo modello (come un web-service) in ~ 450ms, e la maggior parte che è in realtà il tempo speso xml di elaborazione per l'input / output. Se l'ingresso / uscita non era XML, penso che sarebbe ~ 150ms, che è fresco.

Mi piacerebbe convincere il mio datore di lavoro di open-source del motore; che è una battaglia per un altro giorno, però.

non essere solo x ^ n, dove n è il numero di opzioni e x è il numero di scelte per ogni opzione?

Credo che Zac sta pensando nella giusta direzione. Guardando la tua espressione per il numero di combinazioni, si vede che i termini del secondo ordine Cr [i, j] sono molto più piccoli rispetto ai termini C [k]. Immaginate un cubo in cui ogni asse è un gruppo di opzioni. Ogni punto nel cubo rappresenta una particolare combinazione di opzioni. Una correzione primo ordine C [k] esclude una linea di opzioni tra due superfici del cubo. Una seconda correzione ordine C [i, j] avviene solo quando due di tali linee si incontrano in un punto (combinazione di opzioni) nello spazio nel cubo. Quindi, indipendentemente dal numero di gruppi che hai, le correzioni di ordine superiore sono sempre sempre più piccola. Se rispettate

Combinazioni = C (senza regole) - Cr [1] - Credito [2] - Credito [3]

si finisce con un limite inferiore per il numero di combinazioni. Ora che sapete le dimensioni del vostro ordine prima correzione, e pensare l'osservazione con il cubo di cui sopra, si può anche stimare l'ordine di grandezza della seconda correzione ordine. Esso dipenderà dal numero di gruppi. Il vostro algoritmo può quindi decidere se si vuole continuare con gli ordini superiori o interrompere.

Commento di Daniel postale :

Il vostro algoritmo sembra buono, ma non ho potuto convincermi che davvero ha funzionato, così ho installato Scala e ha fatto alcuni test. Unfortunaly non ottengo risultati corretti.

Per esempio si consideri questo caso:

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

Ho configurato il mio algoritmo setaccio base con questa configurazione ed ha ottenuto i seguenti risultati ( 227 combinazioni):

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***

Tuttavia utilizzando questo codice in scala:

  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)))

ho avuto la risposta 258 .

Ho controllato i calcoli nel metodo del setaccio e sembrano essere di destra. Forse è possibile fissare il vostro algoritmo? Non posso davvero mettere il dito su ciò che è sbagliato.

Il problema è piuttosto fattibile.

Contare il numero di soluzioni è # P-completo, anche se si limita ogni gruppo di radioboxes a due opzioni
Verifica se c'è qualche scelta di opzioni coerenti con i vincoli è NP-completo
Verificando se c'è qualche scelta di opzioni coerenti con i vincoli può essere fatto abbastanza veloce, se si limita ogni gruppo di radioboxes a due opzioni (2SAT)

Quindi, in generale non contare su un algoritmo polinomiale; esistenza di tali algoritmi implicherebbe P = NP.

Cosa si può fare:

Utilizzare un algoritmo di approssimazione. Secondo l'articolo di Wikipedia ho linkato, sono spesso suspectible a loro.
Usa un risolutore http://en.wikipedia.org/wiki/SAT_solver o di uno strumento per il conteggio relativo (purtroppo non so ne sono); le persone hanno creato molte euristiche e che i programmi saranno in generale molto più veloce di quanto il tuo soluzione fatta in casa. Ci sono anche gare di SAT, quindi questo campo si sta espandendo molto velocemente.
Controlla se avete bisogno di tale generalità. Forse il tuo problema ha un ulteriore ipotesi, e questo cambierà la sua complessità.

Prove:

Contare il numero di soluzioni può essere facilmente dimostrato di essere #P, quindi è sufficiente a ridurre 2SAT a questo. Prendete un po 'esempio 2SAT, come

(P1 o non p2) e (p2 p3 o meno)

Consente all'utente di scegliere i valori di p1, p2, p3. Si può facilmente formare vincoli che costringerà che questo è risolvibile. Così il numero di possibili configurazioni = numero di possibili assegnazioni di p1, p2, p3 rendendo la formula booleano true.

Si può facilmente verificare se qualche scelta di opzioni è consentito o meno, quindi questo è NP, quindi è sufficiente a ridurre 3SAT a questo. Prendete un po 'esempio 3SAT, come

(P1 o P2 o no p3) e (P1 P2 o meno o P4)

Dare opzioni:

gruppo p1 p1true p1false

gruppo p2 p2false p2true

gruppo p3 p3false p3true

gruppo p4 p4false p4true

gruppo clause_1 C1A C1B C1C

gruppo clause_2 C2A c2b c2c

clause_1 verrà controllando la prima clausola: (P1 o P2 o no p3). Precisamente, C1A sarà verificabile se è stato scelto p1true, C1B sarà controllabile se p2true è stato scelto, C1C sarà controllabile se p3false è stato scelto. Così i vincoli sono:

p1false <-> C1A

p2false <-> C1B

p3true <-> C1C

Lo stesso con clause_2, constaints sono

p2false <-> C2A

p1true <-> c2b

p4false <-> c2c

Se l'utente sarà in grado di scegliere tutte le risposte (in modo che il numero di configurazioni è> 0), che sarà lui a dimostrare che v'è una certa valutazione delle variabili p1, ..., P4 che rendono l'istanza 3SAT vero. E viceversa, se l'utente non sarà in grado di scegliere le risposte coerenti con le ipotesi (il numero di configurazioni disponibili = 0), l'istanza 3SAT non sarà satisfable. Quindi, sapendo se la risposta è> 0 significa conoscere se l'istanza 3SAT è risolvibile.

Naturalmente questa riduzione è polinomiale. Fine della prova.

Se non siete soddisfatti con il fatto che la risposta potrebbe essere 0: è ancora NP-difficile se si trascurano questi configuratori. (Si potrebbe aggiungere un po 'opzione "fasullo" a tutti i gruppi e di consentire in modo esponenziale molte scelte se "falso" non è stato scelto. Questo è più complesso da spiegare, quindi lo farò su richiesta).

Questo è menzionato brevemente nella risposta eccellente di sdcvvc sopra, ma potrebbe un'approssimazione Monte Carlo essere abbastanza buono? Generare N configurazioni casuali (dove N è scelto in modo che la potenza del vostro esperimento è abbastanza alto: io non ne so abbastanza per aiutarvi a qui), quindi verificare come molti di loro sono compatibili con i vostri vincoli. Estrapolare che proporzione al resto del vostro spazio di configurazione.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow