Databases
StackOverflow2013
Postsdbo
PONumber of combinations in configurator
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PONumber of combinations in configurator
    primarykey
    data
    text
    <p>I have been asked to program a routine to decide the number of possible combinations in a product configurator.</p> <p>The configurator is really simple. Even though it has more features than this, it can be modeled as several "radio groups" (like the UI control) where one of n options has to be selected.</p> <p>The only kind of constraints that can be used is rules that says if one option is selected another option can not be selected.</p> <p>So what I want to do is to calculate the number of different products that can be configured, given a set of option groups and constraints.</p> <p>I made a naive approach to solve this using the <a href="http://en.wikipedia.org/wiki/Inclusion-exclusion_principle" rel="nofollow noreferrer">Inclusion-exclusion principle</a>. However as far as I can see, any algorithm based on this method should run in O(2^n) which won't work. There are of course several possible optimizations that should give decent runtimes but there are still easily constructed worst case scenarios.</p> <p>Thats pretty much where I am right now. Any suggestions?</p> <p><strong>Update</strong></p> <p>I realize I haven't explained how the rules applies well enough.</p> <p>There are several groups with options. One and only one option must be selected in each group. There can be one or more of options in a group.</p> <p>There is only one type of constraints. If option A in some group is selected, then option B in some other group can't be selected. There can be any number of constraints, there is no limit how many constraints/rules apply to a option group or an option itself.</p> <p>So an example would be:</p> <p><strong>Group 1:</strong><br/> x1 x2 x3 x4 x5</p> <p><strong>Group 2:</strong><br/> y1 y2 y3</p> <p><strong>Group 3:</strong><br/> z1 z2 z3 z4</p> <p><strong>Constraints:</strong><br/> x1 &lt;-> y2 *<br/> x1 &lt;-> z4<br/> y2 &lt;-> z2<br/></p> <p><code>*</code> If option x1 is selected in group1, then option y2 in group 2 can not be selected.</p> <p>Using inclusion-exclusion I would calculate the number of combinations as</p> <p>Combinations = C<sub>no rules</sub> - C<sub>r</sub><code>[1]</code> - C<sub>r</sub>[2] - C<sub>r</sub>[3] + C<sub>r</sub>[1,2] + C<sub>r</sub>[1,3] + C<sub>r</sub>[2,3] - C<sub>r</sub>[1,2,3]</p> <p>Where </p> <p>C<sub>no rules</sub> = 5 * 3 * 4</p> <p>C<sub>r</sub>[a,b,c] = Number of combinations that violates rule a, b and c.</p> <p>The method unfortunately requires 2^|rules| calculations.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USZac Thompson
    1. USDaniel
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PONumber of combinations in configurator
      1. USDaniel
      1. VTBountyStart
    2. VO
      singulars
      1. PONumber of combinations in configurator
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PONumber of combinations in configurator
      1. USTnilsson
      1. VTFavorite
    1. COIt seems to me that the constraints may be arbitrary and affect an arbitrary number of other options in an arbitrary number of groups. So it's the arbitrary constraints that give you difficulty here?
      singulars
      1. PONumber of combinations in configurator
      1. USInshallah
    2. COPlease give an example: a set of option groups together with a constraint.
      singulars
      1. PONumber of combinations in configurator
      1. USInshallah
    3. COPlease make clear whether you only need the number of combinations or the combinations themselves as well.
      singulars
      1. PONumber of combinations in configurator
      1. USWartin
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload