Número de combinações em configurador

https://stackoverflow.com/questions/1154565

18-09-2019
|

Pergunta

Me pediram para programar uma rotina para decidir o número de combinações possíveis em um configurador de produto.

O configurador é realmente simples. Mesmo que ele tem mais recursos do que isso, ele pode ser modelado como vários "grupos de rádio" (como o controle UI) onde um de n opções tem de ser selecionado.

O único tipo de restrições que podem ser usados ??são regras que diz que se uma opção for selecionada outra opção não pode ser selecionada.

Então, o que eu quero fazer é calcular o número de produtos diferentes que podem ser configurados, dado um conjunto de grupos de opções e restrições.

Eu fiz uma abordagem ingênua para resolver isso usando a Inclusão-exclusão princípio . No entanto, tanto quanto eu posso ver, qualquer algoritmo com base neste método deve ser executado em O (2 ^ n) que não vai funcionar. Há, naturalmente, várias otimizações possíveis que devem dar tempos de execução decentes, mas ainda são facilmente construídos os piores cenários.

Isso é muito bonito, onde estou agora. Alguma sugestão?

Atualizar

Eu percebo que eu não explicou como as regras se aplica bem o suficiente.

Existem vários grupos com opções. Uma e apenas uma opção deve ser selecionada em cada grupo. Pode haver uma ou mais das opções em um grupo.

Existe apenas um tipo de restrições. Se a opção A, em alguns grupo é seleccionado, em seguida, a opção B em algum outro grupo não pode ser seleccionado. Não pode haver qualquer número de restrições, não há limite de quantas restrições / regras aplicam-se a um grupo de opção ou um própria opção.

Assim, um exemplo seria:

Grupo 1:
x1 x2 x3 x4 x5

Grupo 2:
y1 y2 y3

Grupo 3:
Z1 Z2 Z3 Z4

Restrições:
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

* Se a opção x1 é selecionado no grupo1, então y2 opção no grupo 2 não pode ser selecionado.

Usando inclusão-exclusão eu calcular o número de combinações como

Combinações = C _{não há regras} - C _r [1] - C _r [2] - C _r [ 3] + C _r [1,2] + C _r [1,3] + C _r [2,3] - C < sub> r [1,2,3]

Onde

C _{não há regras} = 5 * 3 * 4

C _r [a, b, c] = Número de combinações que viola governar a, b e c.

O método, infelizmente, exige 2 ^ | regras | cálculos.

Solução

Ok, eu não posso dar a volta 2 ^ N, mas pode reduzir o conjunto de amostras. Para fazer isso, vamos calcular "Restrições compôs". A restrição Composta é uma restrição que, se as todas as opções no lado esquerdo é selecionado, em seguida, nenhuma das opções no lado direito podem ser selecionados, mas nenhuma outra restrição com base nas opções do lado esquerdo podem ser aplicadas.

Precisamos calcular um conjunto de todas as possíveis restrições composta a partir de um conjunto de restrições. Embora não seja necessário, vamos "consertar" as restrições existentes trocando as mãos esquerda e direita se o grupo da mão direita é menor do que o grupo de esquerda. Isto pode reduzir algumas restrições compostas, embora heurísticas melhores são possíveis para trocar.

Nós também precisamos calcular um "conjunto mínimo" de opções que podem ser arbitrariamente escolhidos para cada grupo. Este conjunto mínimo é calculado através da remoção da lista de opções disponíveis todas as opções que aparecem no lado esquerdo de uma restrição composta.

Um algoritmo segue, mas eu não estou provando que calcula CCs corretamente. Vou provar que, se isso acontecer, então eles podem ser usados ??para calcular o número de combinações possíveis.

Corrija as restrições para que o grupo da mão esquerda é menor ou igual ao grupo da mão direita.
compor as restrições:
1. Classificar restrições por mão esquerda
2. Sequencialmente, para cada restrição:
  1. Dobre o constrangimento com todas as restrições que o seguem com a mesma mão esquerda, virando x1 <-> y1, x1 <-> y2 ... x1 <-> yN em Set(x1) <-> Set(y1 ... yN)
  2. Componha a restrição dobrado com cada restrição já dobrado, se:
    - x1 não é na mão direita da restrição
    - x1 não está no mesmo grupo de qualquer elemento na mão esquerda
  3. Adicionar a restrição dobrado e todas as composições que seja para o conjunto de restrições dobradas
Calcule o conjunto mínimo, tomando todas as opções e removendo os que aparecem no lado esquerdo das restrições fixas.

Agora você pode calcular o número de combinações com a fórmula abaixo. Vamos chamada CC uma restrição composta. Em seguida, o número de combinações é:

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

Onde:

C (Conjunto mínima) é o número de combinações possíveis com o conjunto mínimo.
CCCx é o número de combinações possíveis, tomando o conjunto mínimo, substituindo quaisquer grupos para os quais há uma opção no lado esquerdo da CCx com essa opção e, em seguida, remover quaisquer opções na mão direita de CCx.

Note que a expressão é puramente aditivo. Isto significa que, por essa expressão para produzir o resultado esperado, as duas seguintes condições devem ser verdadeiras:

Não existem dois termos de que podem conter a mesma combinação.
Todas as combinações devem ser contabilizados por estes termos.
Não há combinações inválidos podem ser gerados por qualquer prazo.

Para a primeira prova, nota que não há dois CCs distintas com a mesma mão esquerda. Se dois CCs tinha a mesma mão esquerda, mas diferentes mãos certas, isso significaria que havia uma restrição de adição que deve aplicar-se um dos CCs, ou uma restrição inválida sendo aplicada para o outro.

Uma vez que não existem duas CCs com a mesma mão esquerda, e o conjunto mínimo não contém o lado esquerdo de qualquer CC, por definição, então qualquer dois CC podem ser distinguidos por pelo menos uma opção que é selecionado para um, mas não para o outro. Portanto, não há dois CCs podem produzir a mesma combinação.

Para a segunda prova, nota que o conjunto de CCs contém, por definição, todas as combinações válidas para as opções na mão esquerda.

Suponha que há uma combinação que não aparece tanto no conjunto mínimo nem o conjunto de CCs. Se esta combinação não contém qualquer opção do lado esquerdo, então deve ser uma combinação do conjunto mínimo, por definição. Portanto,deve conter opções do lado esquerdo.

Uma vez que o conjunto de CCs contém todas as combinações válidas para a mão esquerda, então não é um CC com as mesmas opções para a mão esquerda. Essa combinação deve ter, portanto, uma opção que não está incluído em qualquer combinação para que CC. Mas as únicas opções não incluídas nesse CC são os únicos que aparecem no lado esquerdo para outros CCs, e os que devem ser excluídos pela constrangimentos. Uma vez que nem pode ser o caso, então esta combinação não pode existir.

Para a terceira prova, vamos primeiro considerar o conjunto mínimo. O conjunto mínimo não contém nenhuma opção no lado esquerdo de qualquer grupo. Desde todas as restrições estão entre uma esquerda e uma opção mão direita, sem restrição aplica-se ao conjunto mínimo.

Agora, vamos considerar os CCs. A CC tem uma combinação válida de opções mão esquerda por definição. Qualquer opção que é incompatível com a mão esquerda deve aparecer na mão direita, e qualquer opção de que a mão direita deve ser removido do conjunto mínimo. Desde há opções no conjunto mínimo, onde incompatíveis entre si, para começar, não pode haver restrição insatisfeito em qualquer combinação em um CC.

E que termina a prova.

Vamos ver como isso se aplica com um exemplo a partir dos comentários:

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}

Vamos brevemente ponderar em grupos compostos não está na lista:

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

Agora, vamos ver o que são possíveis opções em cada conjunto:

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

Agora, vamos adicionar coisas:

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

Vou acrescentar um outro pensamento aqui. Mesmo que haja apenas 6 CCCs para 5 regras, muito menos do que os 32 termos esperado em contrário, estes CCCs são calculados com 2 ^ N pior momento, uma vez que, para cada regra, você deve comparar e combiná-lo a todos os CCCs criados até agora. Você pode pensar neles como números binários, onde um bit é definido se a regra está sendo combinado, e não definir se não.

No entanto, combinações incompatíveis são de descarte de imediato, de modo que para cada nova regra a ser combinada, sem tempo é perdido em combinações já considerada inválida. Além disso, classificando as regras de antemão, regras sucessivas no mesmo grupo podem ser descartados sem sequer testar por incompatibilidade, com as estruturas de dados direita.

Como mostra este exemplo especial, o tempo médio pode ser muito melhor do que 2 ^ N.

algoritmos alternativos e Considerações

Há alguma conversa de 2-SAT e 3-SAT acontecendo ao redor. Parece, para mim, que este é um problema 2-SAT, no sentido de que todos os constranger a <-> b é realmente uma cláusula "a || b!". Assim, todos os constrangimentos em conjunto só pode ser escrito como "(! X1 ||! Y2) && (! X1 ||! Z4) && (! Y2 &&! Z3)", etc. Isso significa que você pode "resolver" it no sentido de que você pode descobrir se existe uma atribuição booleano para cada opção que irá transformar este true . Há um algoritmo linear para isso Aspall, Plass e Tarjan, com uma apresentação de slides aqui .

Mas saber se as restrições podem ser resolvidos ou não não é o que foi perguntado . O que foi pedido é a número de maneiras todas as opções podem ser definidas, mantendo o problema 2-SAT verdade.

Agora, existem algoritmos eficientes para contar o número de maneiras para satisfazer um problema de 2 sab Por exemplo, presentes este papel um algoritmo que é executado em 1,2561 ⁿ. Mas mesmo este não vai nos ajudar, como precisamos saber o as soluções são para ser capaz de calcular o número de combinações que satisfazem essa solução.

De acordo com a Wikipedia, este papel tem um algoritmo que enumerar de forma eficiente todas as soluções, que é o que queremos. Mas se a contagem já é exponencial, Assim será também enumerando. Melhor do que 2 ⁿ, talvez, mas ainda exponencial.

Se fizermos enumerar todas as soluções para o problema 2-SAT, o número de combinações para cada grupo é dada por 1 multiplicado pelo número de opções gratuitas, opções que não aparecem em qualquer restrição, de cada grupo para as quais não opção foi selecionada pela solução.

Por exemplo, tendo o conjunto anterior de grupos e restrições. O problema 2-SAT, incluindo a exclusão mútua, é:

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

A primeira linha são as cinco regras. A segunda linha é a exclusão mútua de todas as opções no mesmo grupo que aparecem nas regras de restrição.

As soluções para este problemas 2-SAT são:

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

Nas duas primeiras soluções, não há grupos sem uma opção seleccionada, de modo que o número de combinações é 1. A terceira solução não tem a opção seleccionada para o grupo G3, portanto, multiplicar por 1 0. Nas linhas que início com "false false", não há nenhuma opção selecionada para o grupo G1, e uma livre opção: x2. Por isso, multiplicam 1 por 1 para eles, e por 0 se não houver opção selecionada para G2 ou G3 (caso em que o número de opções livres é 0).

Agora, há a questão de como faço para fazer cumprir uma opção a ser escolhida em cada grupo e ainda afirmam ser 2-sáb. O problema, como afirmou, tem duas limitações implícitas: para cada grupo, deve haver um, e apenas um, opção selecionada. Estas duas restrições pode ser escrita como:

x ₁ || x ₂ || x ₃ (para o grupo x com opções x ₁ .. x ₃)
(! X ₁ ||! X ₂) && (! X ₁ ||! X ₃) && (! x ₂ ||! x ₃)

O mais tarde restringir sendo 2-SAT, sendo o primeiro 3-SAT para qualquer caso não-trivial. Quando isso acontece, eu não impor a primeira restrição, mas a contagem torna-se então 0. O algoritmo de contagem deve ir como este:

Para as combinações de restrição-menos, multiplicar o número de opções de restrição-menos em cada grupo por outro.
Para as combinações de restrição-cheia, adicione o resultado das seguintes razões:
- Para cada solução, multiplique o número de opções de restrição-menos em cada grupo sem uma opção avaliada como "true" por outro.

Assim, para cada grupo em que há pelo menos uma opção de restrição-less, a selecção é implícita e anônimo. Para cada grupo em que todas as opções são parte de alguma restrição, se nenhuma opção foi selecionada, em seguida, a contagem para esse grupo se torna 0, e, portanto, o número de combinações para que a solução se torna 0 também.

Isto parece enganar o problema para fora de um válido> 2-SAT restrição. Afinal, se isso era possível, então o problema 3-SAT pode ser resolvido apenas por enumerar as soluções para a parte 2-SAT do mesmo, e, em seguida, descartando todo aquele que não satisfaz a parte 3-SAT dele. Infelizmente, há uma diferença fundamental I pode identificar:

Todos predicados não resolvidos pela parte 2-SAT do problema estão livres de quaisquer outras restrições.

Dada esta restrição bastante restritivo sobre as cláusulas, podemos resolver este problema, enumerando soluções para as limitações explícitas 2-SAT.

Se alguém quiser perseguir isso ainda mais, vá em frente. Estou satisfeito com a melhoria no 2 ⁿ solução que eu sugeri.

Outras dicas

Se você tem grupos de opções N, cada um com opções Xi (0<=i<N), então

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

Dá-lhe a resposta que você quer. Em outras palavras, multiplique o tamanho de cada grupo de opções.

Se você tem parâmetros n com valores Ci possíveis para cada parâmetro e m restrições, um limite superior para o número de configuartions é a seguinte (ignorando os constrangimentos).

N0 = C1 * C2 * ... * Cn

A única restrição da ci == x => cj != y forma não permite o seguinte número de configurações.

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

Por isso, o número de configuração é obtida subtraindo os configuartions impedido do limite superior ignorando os constrangimentos.

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

Aqui xj e yj são os dois índices de parâmetros do j-th restrição.

Exemplo

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

Atualizar

Eu acho que isso ainda não é completamente correto, pois ele não leva em conta as dependências das restrições.

~~Não há atalhos aqui para o caso geral.~~ Não é tão ruim quanto você pensa. Consulte "Rethinking" abaixo.

É de 2 ^ n realmente tão ruim? Quantas regras de exclusão que estamos falando aqui? Você realmente só tem que fazer isso uma vez para cada configurador, a menos que o conjunto de regras / opções está constantemente a mudar na mosca e exigindo recálculo dinâmico. Se há realmente um grande número de regras, então eu não iria procurar uma solução exata - considerar apenas as interseções k de ordem e dizer "número de combinações é de pelo menos / mais ...". Pode haver outros métodos de peneira que lhe permitirá limites rapidamente retirarem a resposta.

Além disso, mantenha em mente: se você considerar apenas as exclusões que você realmente precisa, em seguida, 2 ^ n é apenas um limite superior, e seu número real de cálculos podem ser significativamente menos para quaisquer cenários reais. Ou seja, se C [1,2] é zero, então é assim C [1,2, ...]. Considere o seguinte: para cada restrição, conjuntos de "moita" de restrições em conjunto, se eles compartilham todas as opções em comum. É claro que o seu tempo de funcionamento reais vai ser definido pelo tamanho do maior "moita" (que, sim, pode ser tão grande como n).

Rethinking : C [x, y] vai ser zero no a maioria casos. A restrição só pode sobreposição com outras restrições envolvendo um diferente grupo. Em outras palavras, (x1 <-> y1) só podem sobreposição com (x1 <-> z1) ou (y1 <-> z2) ou algo assim, não (x1 <-> Y2). Da mesma forma, um conjunto de restrições só podem sobreposição com um novo grupo: o combinação de (x1 <-> y1) com (y1 <-> z2) não tem qualquer interação com (x3 <-> z2) (o grupo X já está fixada em x1). Você só tem que considerar inclusão / exclusão, onde cada regra que você adicionar à combinação adiciona um grupo previamente intocado à mistura. Então você está realmente O (2 ^G), onde G é o número de grupos (e talvez também um diferente encadernados com base no tamanho dos grupos). Muito mais gerenciável!

Editar

Este algoritmo está incorreto. Apresentei uma resposta alternativa em outro post que ainda é 2 ^ N no caso pior, mas pode dar melhores resultados contrário.

Este funciona no exemplo escolhido porque y2 é parte do conjunto de exclusão de x1, e as duas primeiras restrições são baseados em x1. Ainda assim, eu agora ver o que precisa ser feito. Ainda é próximo de 2 ^ N, mas há otimizações que podem levar a ganhos significativos.

Para corrigir esse algoritmo, as regras compostas devem ser do conjunto de formulários (boi) <-> set (oy). Para compor-los, para cada constrain com mão esquerda boi compor, você também fazer outras composições com cada regra que você já composta, se oX não faz parte do lado direito da regra composta, nem é grupo é o mesmo que o lado esquerdo do grupo .

Para constrangimentos completamente independentes, isto é 2 ^ N. Caso contrário, você está reduzindo N fazendo:

unificar constrangimentos com um comum esquerda mão
não se computando combinações de regras que são mutuamente exclusivas, este é dividido em:
- não combinar regras para opções no mesmo grupo
- não combinar regras, onde o lado esquerdo de um aparece no lado direito do outro

Eu não acho que a fixação deste algoritmo é pena. É um pouco de memória-pesado, e teria a mesma ordem que a minha resposta alternativa, que é muito mais leve.

Fim Editar

Vamos virar esse jogo. Como sobre isso por um algoritmo:

regras Fix conforme necessário para garantir que para o1 <-> o2 regra, group(o1) < group(o2)
Compute "composta" regras de dobrar todas as regras oX <-> o? em uma única regra oX <-> Set(o?)
Compute um conjunto "limpa" de grupos, removendo deles a opção esquerda de cada regra
Compute conjuntos alternativos do jogo limpo, um para cada regra composta, substituindo o grupo da opção de esquerda com a própria opção esquerda, e subtraindo os outros grupos as opções do lado direito da regra.
Para cada conjunto de grupos, calcule o número de combinações multiplicando o número de opções em cada grupo no conjunto.
Adicionar todos os resultados da etapa 5.

Vamos ver isso no trabalho:

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

Agora, talvez este algoritmo está incorreto. Agora, eu não posso pensar com clareza suficiente para provar isso corrigir ou não - eu tenho sido muito perto do problema por muito tempo. cheque, mas vamos contra a exemplo:

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 o meu algoritmo é correto, ele parece ser polinomial. Mais uma vez, agora eu não posso pensar com clareza suficiente, e eu preciso considerar o big-O da manipulação nos conjuntos.

Aqui é uma implementação Scala dele:

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

Isto pode não ser uma resposta directamente útil, tão à vontade para ignorá-lo ... no entanto; Atualmente estou trabalhando há um sistema semelhante a mim; e, francamente, diferente para exemplos triviais Eu não tenho certeza que ele é útil para tentar calcular o número de combinações válidas. Como exemplo, os modelos que estou trabalhando no momento têm (por exemplo) 18000 itens candidatos distribuídos por 80+ seleções, alguns single-SELECT / alguns multi-selecionar. Além dos modelos mais pequenos, não há nenhuma benefício em saber o número, como seria simplesmente nunca escrevê-lo como uma tabela verdade completa; você é muito-muito forçada para executar as regras (ou seja, remover qualquer coisa que não é mais válido auto-select nada, conforme apropriado, e verificar se há regras são quebradas) on-demand. Que não é necessariamente um problema; meu código atual processa este modelo (como um serviço web) em ~ 450ms, ea maioria dos que é realmente o tempo gasto processamento XML para entrada / saída. Se a entrada / saída não foi xml, eu acho que seria ~ 150ms, o que é legal.

Eu adoraria convencer meu empregador para open-source do motor; que é uma batalha para outro dia, no entanto.

não ser apenas x ^ n, onde n é o número de opções e x é o número de opções por opção?

Eu acho que Zac está pensando na direção certa. Olhando para a sua expressão para o número de combinações, você vê que os termos de segunda ordem Cr [i, j] são muito menores do que as C termos [k]. Imagine um cubo, onde cada eixo é um grupo de opções. Cada ponto no cubo representa uma combinação específica de opções. Uma primeira ordem C [k] de correcção exclui uma linha de opções entre duas superfícies do cubo. A segunda correcção de C [i, j] só acontece quando duas dessas linhas se encontram num ponto (combinação de opções) no espaço no cubo. Portanto, independentemente do número de grupos que você tem, as correções de ordem superior são sempre cada vez menor. Se se mantiver a

= As combinações C (sem regras) - Cr [1] - Cr [2] - Cr [3]

você acabar com um limite inferior para o número de combinações. Agora que você sabe o tamanho da sua primeira correção ordem e pensamento sobre a observação com o cubo acima, você pode até mesmo estimar a ordem de grandeza da segunda correcção ordem. Vai depender do número de grupos. Seu algoritmo pode então decidir se quer continuar com as ordens superiores ou parar.

Comentário para de Daniel pós :

Seu algoritmo parece boa, mas eu não conseguia me convencer de que realmente funcionou, então eu instalei scala e fez alguns testes. Unfortunaly eu não conseguir resultados corretos.

Por exemplo, considere este 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

I configurado meu algoritmo básico peneira com esta configuração e tem os seguintes resultados ( 227 fortes combinações):

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

No entanto usando esse código em 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)))

Eu tenho a resposta 258 .

Eu verifiquei os cálculos no método peneira e eles parecem estar certo. Talvez seja possível corrigir o seu algoritmo? Eu realmente não posso colocar o dedo sobre o que está errado.

Seu problema é bastante inviável.

A contagem do número de soluções é # P-completo, mesmo se você restringir cada grupo de radioboxes a duas opções
Verificar se há alguma escolha de opções consistentes com restrições é NP-completos
Verificar se há alguma escolha de opções consistentes com restrições pode ser feito muito rápido, se você restringir cada grupo de radioboxes para duas opções (2SAT)

Assim, em geral não conte com um algoritmo polinomial; existência de tais algoritmos implicaria P = NP.

O que você pode fazer:

Use um algoritmo de aproximação. De acordo com o artigo Wikipedia I ligados, são muitas vezes suspectible a eles.
Use um SAT solver http://en.wikipedia.org/wiki/SAT_solver ou uma ferramenta relacionada para a contagem (infelizmente eu não conheço nenhum); pessoas têm criado muitos heurística e que os programas serão, em geral, muito mais rápido do que a sua solução caseira. Existem ainda competições SAT, então este campo é atualmente expandindo muito rápido.
Verifique se você precisar de tal generalidade. Talvez o seu problema tem uma pressupostos adicionais, e isso vai mudar a sua complexidade.

Provas:

A contagem do número de soluções é facilmente demonstrado ser #P, por isso é suficiente para reduzir 2SAT a isso. Tire algum exemplo 2SAT, como

(p1 ou não p2) e (p2 ou não P3)

Permita que o usuário escolher valores de p1, p2, p3. Você pode facilmente formar restrições que forçarão este seja solucionável. Portanto, o número de configurações possíveis = número de possíveis atribuições de p1, p2, p3 tornando a fórmula booleana verdade.

Você pode facilmente verificar se alguma escolha de opções é permitido ou não, por isso esta é NP, por isso é suficiente para reduzir 3SAT para isso. Tire algum exemplo 3SAT, como

(P1 ou P2 ou não P3) e (p2 ou não p1 ou P4)

Dê opções:

grupo p1 p1true p1false

grupo p2 p2false p2true

grupo P3 p3false p3true

grupo p4 p4false p4true

grupo clause_1 C1a C1b C1c

grupo clause_2 c2a C2B c2c

clause_1 será controlar a primeira cláusula: (P1 ou P2 ou não P3). Precisamente, C1a será verificável se p1true foi escolhido, C1b será verificável se p2true foi escolhido, C1c será verificável se p3false foi escolhido. Assim, as restrições são:

p1false <-> C1a

p2false <-> C1b

p3true <-> C1c

Mesmo com clause_2, constrangimentos são

p2false <-> C2A

p1true <-> C2B

p4false <-> c2c

Se o usuário será capaz de escolher todas as respostas (por isso o número de configurações é> 0), ele vai provar que há alguma valorização de variáveis ??p1, ..., p4 que fazem a instância 3SAT verdade. E, inversamente, se o usuário não será capaz de escolher respostas consistentes com suposições (o número de configurações disponíveis = 0), a instância de 3SAT não será satisfable. Então, sabendo se a resposta for> 0 significa saber se instância 3SAT é solucionável.

É claro que esta redução é polinomial-time. Fim da prova.

Se você não estiver satisfeito com o fato de que a resposta pode ser 0: ainda é NP-difícil se você desconsiderar tais configuradores. (Você gostaria de acrescentar alguma opção "falsa" a todos os grupos e permitir exponencialmente muitas escolhas se "falso" não foi escolhido. Isto é mais complexo para explicar, então eu vou fazê-lo a pedido.)

Esta é mencionado brevemente em excelente resposta de sdcvvc acima, mas pode uma aproximação Monte Carlo ser bom o suficiente? Gerar N configurações aleatórias (onde N é escolhido de forma que o poder de sua experiência é alta o suficiente: Eu não sei o suficiente para ajudá-lo aqui), então teste quantos deles são compatíveis com suas limitações. Extrapolar essa proporção para o resto do seu espaço de configuração.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow