Calculate all possible combinations

[1bosborn]

Good morning. I have a script that compares products entered into inventory against known good prices before sending them to our web provider to ensure they are priced correctly. This just got a lot more complicated as we just took on a line of products that have multiple optional features. The base model of each product may have any combination of zero to all five options and I have been unable to conceptualize ho to cycle through all possible pricing combinations. I haven't been able to find anything like it in the tech database or forums but that might just be because I don't even know what to call it. I've been thinking of some sort of binary (boolean?)  table:
o1 o2 o3
0   0   0
0   0   1
0   1   0
etc. to walk through all the combinations but don't know how to convert 2^3 or 8 to binary and get Winbatch to use the binary number to correlate to the option number(s) or if I am even on the right track. If this is outside the scope of the forum I will understand but if you can nudge me in the right direction it would be appreciated.

[1bosborn]

Thanks Jim, I think we're headed in the right direction but I'm looking to do something more like this:
product1 can have any combination of options a, b, c, and/or d
product2 can have any combination of options e, f, and/or g (different possibilities and number of possibilities than product1)
Since the script won't know which options each product shipped with, it needs to calculate all possible variations for each product to see if the price entered by the inventory clerk matches any possible valid price in order to make somewhat sure the inventory clerk entered the price correctly. I would like to compare the value they entered for product1 (from a text file) to every combination of product1, product1 + option a, P1 + Oa + Ob, P1 + Oa + Oc, P1 + Od etc., likewise for product2 and all of the possible combinations of product2  with and without any combination of the possible options.
I can create a list of the product-id with its base price and the prices of its available options but I just can't figure out how to iterate through all of the combinations.

[td]

Thanks Jim, I think we're headed in the right direction but I'm looking to do something more like this:
product1 can have any combination of options a, b, c, and/or d
product2 can have any combination of options e, f, and/or g (different possibilities and number of possibilities than product1)
Since the script won't know which options each product shipped with, it needs to calculate all possible variations for each product to see if the price entered by the inventory clerk matches any possible valid price in order to make somewhat sure the inventory clerk entered the price correctly. I would like to compare the value they entered for product1 (from a text file) to every combination of product1, product1 + option a, P1 + Oa + Ob, P1 + Oa + Oc, P1 + Od etc., likewise for product2 and all of the possible combinations of product2  with and without any combination of the possible options.
I can create a list of the product-id with its base price and the prices of its available options but I just can't figure out how to iterate through all of the combinations.

It's a classic problem. In fact, the C++ standard library has a set of template algorithms for the generation of permutations. It is an interesting problem to solve.  Perhaps someone will take on the challenge and post an example solution.

[edit] This looks interesting:

https://en.wikipedia.org/wiki/Heap%27s_algorithm

[JTaylor]

While I can't take full credit I think this does what you want.  The main issue is that it requires my wbDOMData Extender because I couldn't make the WinBatch Global variables work.  You get that sorted then you could drop the Extender.  Maybe someone here can help with that.

http://www.jtdata.com/anonymous/DomData.zip

Jim

Code: Winbatch

AddExtender(DirScript():"wbdomdata.dll")

#DefineFunction Price_Check_On_Aisle_5(map, reqLen, s, currLen, check, l, plist)

  If(currLen > reqLen)
   Return
  ElseIf currLen == reqLen
    For i = 0 to l-1
      If (check[i] == 1) Then
        dmStorePush("pcheck",map[i]:"+")
      EndIf
    Next
    dmStorePush("pcheck",@CR)
    Return
  EndIf

  If s == l Then
    Return
  EndIf

  check[s] = 1
  Price_Check_On_Aisle_5(map, reqLen, s + 1, currLen + 1, check, l, plist)
  check[s] = 0
  Price_Check_On_Aisle_5(map, reqLen, s + 1, currLen, check, l, plist)

#EndFunction

price_list = "25,32,23.50,44,10,88"
cnt        = ItemCount(price_list,",")
base_price = 10
plist      = ""

map = MapCreate()
check = MapCreate()

  For x = 0 to cnt-1
    map[x] = ItemExtract(x+1,price_list,",")
    check[x] = 0
  Next

  For x = 0 to cnt
    plist = Price_Check_On_Aisle_5(map, x, 0, 0, check, cnt, plist)
  Next

plist = StrReplace(dmStorePull("pcheck"),"+":@CR,@CR)

chk_price = 67.50
matched = 0
cnt     = ItemCount(plist,@CR)
For x = 1 to ItemCount(plist,@CR)
   cprice = ItemExtract(x,plist,@CR)
   If cprice == "" Then Continue
   
   If %cprice% == chk_price Then
      matched = 1
      x = 10000
   EndIf
Next

If matched Then
   Message("Match", chk_price)
Else
   Message("Nope","No Match")
EndIf

 

[td]

This is a take on the OP's original idea of using a sort of binary bit matrix to calculate all possible price combinations.  It is neither particularly efficient nor elegant and I haven't verified that it actually works. There is also some possibility of duplicates in the output but that can be fixed with deduping. So take it for what it is worth which may not be much.

Code: Winbatch

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prices
;;
;; Create a list of all the
;; prices for all combinations
;; of options.
;; Parameter: _aOptPrices array of prices
;; Return: an array of prices combinations
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
#defineFunction Prices( _aOptPrices)
   nOpts = ArrInfo(_aOptPrices, 1)

   ; Number of possible bit combinations
   ; based on the number of prices
   nMax = 2**nOpts
 
   for i = 0 to nMax-1 ; Each bit combination.
      aOut[i]=0
      for j = 0 to nOpts -1 ; Each bit in the combination.
         if i & (1<<j)
            aOut[i] += _aOptPrices[j]
         endif
      next
   next

   return aOut
#endfunction

; Widget option prices.
aWigetOpts[0] = 11
aWigetOpts[1] = 12
aWigetOpts[2] = 13
aWigetOpts[3] = 14
aWigetOpts[4] = 15

; Get the combination prices as an array.
aPrices = Prices(aWigetOpts)

;;; Display the result.
lPrices = ArrayItemize(aPrices, @LF)
Message('List of Combined Option Prices', lPrices)

exit

[JTaylor]

Got it fixed so you do not need the Extender.

Jim

Code: Winbatch

#DefineFunction Price_Check_On_Aisle_5(map, reqLen, s, currLen, pcheck, l, plist, presults)

  If(currLen > reqLen)
   Return presults
  ElseIf currLen == reqLen
    For i = 0 to l-1
      If (pcheck[i] == 1) Then
        If !IsDefined(txt) Then txt = ""
        txt = txt:"+":map[i]
        presults[txt] = 1
      EndIf
    Next
    Return presults
  EndIf

  If s == l Then
    Return presults
  EndIf

  pcheck[s] = 1
  presults = Price_Check_On_Aisle_5(map, reqLen, s + 1, currLen + 1, pcheck, l, plist, presults)
  pcheck[s] = 0
  presults = Price_Check_On_Aisle_5(map, reqLen, s + 1, currLen, pcheck, l, plist, presults)

  Return presults

#EndFunction



price_list = "25,32,23.50,44,10,88"
cnt        = ItemCount(price_list,",")
base_price = 10
plist      = ""

map        = MapCreate()
pcheck     = MapCreate()
presults   = MapCreate()

  For x = 0 to cnt-1
    map[x] = ItemExtract(x+1,price_list,",")
    pcheck[x] = 0
  Next

  For x = 0 to cnt
    presults = Price_Check_On_Aisle_5(map, x, 0, 0, pcheck, cnt, plist, presults)
  Next

chk_price = 67.50
matched = 0
Foreach cprice in presults
   If cprice == "" Then Continue
   If %cprice% == chk_price Then
      matched = 1
      x = 10000
   EndIf
Next

If matched Then
   Message("Match", chk_price)
Else
   Message("Nope","No Match")
EndIf


 

[td]

Realized my previous comments could be interpreted to mean that the idea of using a bit matrix was in and of itself unimaginative or inefficient. But I was referring to my implementation and not the idea.

FWIW, a lightly updated version with a little better optimized and duplicate removal.

Code: Winbatch

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prices
;;
;; Create a list of all the prices
;; for all possible combinations of
;; options.
;;
;; Parameter: _aOptPrices array of prices
;;
;; Return: map of prices combinations
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
#defineFunction Prices( _aOptPrices)
   nOptMax = ArrInfo(_aOptPrices, 1)
   mOut    = MapCreate()

   ; Number of possible bit combinations
   ; based on the number of prices
   nComboMax = (2**nOptMax ) - 1 ; -1 to account for 0 based array indeces.
   nOptMax -= 1 ; -1 to acount for the 0 based bit shifting.

   for i = 0 to nComboMax ; Each bit combination.
      nTotal=0
      for j = 0 to nOptMax  ; Each bit in the combination.
         if i & (1<<j) then nTotal += _aOptPrices[j]
      next
      mOut[nTotal] = nTotal ; Had to use something for a map value.
   next

   return mOut
#endfunction

; Widget option prices.
aWigetOpts[0] = 11
aWigetOpts[1] = 12
aWigetOpts[2] = 13
aWigetOpts[3] = 14
aWigetOpts[4] = 15

; Get the combination prices as an associative array.
mPrices = Prices(aWigetOpts)

;;; Display the result.
lPrices = MapKeysGet(mPrices, 2, @LF)
Message('List of All Combined Option Prices', lPrices)

exit

 

[stanl]

Excel can help visualize combinations:



https://www.extendoffice.com/documents/excel/3097-excel-list-all-possible-combinations.html


https://www.excelhow.net/generate-all-possible-combinations-of-two-lists-in-excel.html


https://stackoverflow.com/questions/10692653/excel-vba-to-create-every-possible-combination-of-a-range