abnab - 1 year ago 90
SQL Question

# MySQL permutation

I have two tables. One has products and the other has bundles that go with it. I need to figure out the SQL that allows me to find all the combinations in which I can sell the product with extras.

``````Products

Name   ID
Bench   1

Extra

Name           ID     Parent ID  QTY
undershelf     1        1        1
overshelf      2        1        1
wheels         3        1        1
``````

I need and output table that shows all the combination in which I can sell the product:

``````Bench
Bench + undershelf
Bench + undershelf + overshelf
Bench + overshelf
Bench + wheels
bench + wheels + overshelf  and so one.
``````

Every extras can be in the bundle or not, making that a binary property.
A way to visualize the combination is to create a word with a bit for every extra, `1` mean that the extra is in the list, `0` mean the that it is not.
For example `Bench + undershelf + overshelf` is 110 (or 011 if the binary string is read in the opposite order)

Generating every combination of n bit will give every combination of n extras, it will also give every number from `0` to `2^n - 1`.

We can work back from here:
1. generate the list of number from `0` to `2^n - 1`;
2. convert the number to binary, to list the combination of extras
3. match every bit with an extra
4. concatenate the names of the extras in the bundle description.

``````SELECT CONCAT(b.Name
, COALESCE(CONCAT(' + '
, GROUP_CONCAT(x.Name SEPARATOR ' + '))
, '')) Combination
FROM   (SELECT p.Name, p.id
, LPAD(BIN(u.N + t.N * 10), e.Dim, '0') bitmap
FROM   Products p
CROSS JOIN (SELECT 0 N UNION ALL SELECT 1
UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7
UNION ALL SELECT 8 UNION ALL SELECT 9) u
CROSS JOIN (SELECT 0 N UNION ALL SELECT 1
UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7
UNION ALL SELECT 8 UNION ALL SELECT 9) t
INNER JOIN (SELECT COUNT(1) Dim
, `Parent ID` pID
FROM Extra) E ON e.pID = p.ID
WHERE  u.N + t.N * 10 < Pow(2, e.Dim)
) B
LEFT  JOIN (SELECT @rownum := @rownum + 1 ID
, `Parent ID` pID
, Name
FROM   Extra
, (Select @rownum := 0) r) X
ON x.pID = b.ID
AND SUBSTRING(b.bitmap, x.ID, 1) = '1'
GROUP BY b.Name, b.bitmap
``````

this query will work up to six extras, then it'll need another digit table (one digit every three extras).

How it Works

The subquery `E` count the number of the extras, this is used in `C` to limit the elements generated by the digit tables `u` and `t` (unit and tens) to 2^dim.

The number is converted to binary by `BIN(u.N + t.N * 10)`, then left padded with '0' to the number of elements, generating a combination bitmap.

To use the generated bitmap each extras need a fake id that will match a position in it, that's what the subquery `X` is meant for.

The two subqueries are `JOIN`ed by the nth char of the bitmap: if the char is 1 the extra is in the bundle, `LEFT` joined to not loose the product without extras.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download