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.
Name ID Parent ID QTY
undershelf 1 1 1
overshelf 2 1 1
wheels 3 1 1
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.
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
2^n - 1.
We can work back from here:
1. generate the list of number from
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
E count the number of the extras, this is used in
C to limit the elements generated by the digit tables
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
JOINed 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.