My wife has a nutcracker collection. One of them includes a pair of cubes for use as a counter. One of the cubes has the digits 0,1,2,3,4,5 on the faces. The other cube has the digits 0,1,2,6,7,8. The 6 is invertible to be used as a 9, thus allowing for 7 digits on 6 faces. These cubes produced a few mathematical questions and, of course, I used SQL to solve them.
It was immediately obvious that even though we could represent 2 digit numbers with the cubes we could not do a full range of one-hundred numbers: 00-99. So, the first question was how far could we count using these cubes? I answered this with the following query and simply scanned through the results until I found a gap.
WITH
a AS(SELECT x FROM XMLTABLE('0,1,2,6,9,7,8' COLUMNS x NUMBER PATH '.')),
b AS(SELECT y FROM XMLTABLE('0,1,2,3,4,5' COLUMNS y NUMBER PATH '.')),
c
AS
(SELECT x * 10 + y result
FROM a, b
UNION
SELECT 10 * y + x
FROM a, b)
SELECT *
FROM c
ORDER BY result;
This showed the highest number we could generate without skipping was 32.
Breaking down the query into it’s components, I needed a way to make every combination of faces from each cube with every face of the other cube, and I can reverse the cubes, choosing which one to be the tens-digit and which to be the ones-digit to make even more combinations. Combining every value from one source with every value of another source sounds like a Cartesian join which is easily written in SQL. Then it was just a matter of creating a table for each cube. I could have created physical tables for each but I decided to include the A and B cubes within the SQL so the solution could be picked up an run as is, i.e. without any extra installation steps. There are a variety of methods I could have used: recursive sql, nested table type objects, views of union statements, but I thought the XMLTABLE function had the best combination of compactness and ease of reading. The simplest method for representing the invertible (6,9) face was to simply list both digits for that face as only value at a time will be used in each join result.
To create each number I multiply a digit from one cube by 10 and add one digit from the other cube. Using UNION, I do the same thing with the cubes reversed to produce the entire set of distinct combinations. Then ordering the results reveals the gap after 32 where the next number is 36. For the sake of completeness I looked for other gaps as well, so I used the same query with a LAG.
SQL> WITH
2 a AS(SELECT x FROM XMLTABLE('0,6,9,1,2,7,8' COLUMNS x NUMBER PATH '.')),
3 b AS(SELECT y FROM XMLTABLE('0,1,2,3,4,5' COLUMNS y NUMBER PATH '.')),
4 p
5 AS
6 (SELECT x * 10 + y result
7 FROM a, b
8 UNION
9 SELECT 10 * y + x
10 FROM a, b)
11 SELECT *
12 FROM (SELECT result, LAG(result) OVER (ORDER BY result) prev FROM p)
13 WHERE result != prev + 1
14 ORDER BY result;
RESULT PREV
------- -----
36 32
46 42
56 52
70 65
80 75
90 85
6 rows selected.
Note though the cubes can only represent numbers up to 95. So, 96-99 are left out of the gap search. In order to find the missing values from the full range 00-99 I used the MINUS operator.
SQL> WITH
2 a AS(SELECT x FROM XMLTABLE('0,6,9,1,2,7,8' COLUMNS x NUMBER PATH '.')),
3 b AS(SELECT y FROM XMLTABLE('0,1,2,3,4,5' COLUMNS y NUMBER PATH '.')),
4 c
5 AS
6 (SELECT x * 10 + y result
7 FROM a, b
8 UNION
9 SELECT 10 * y + x
10 FROM a, b),
11 full_range
12 AS
13 (select z FROM XMLTABLE('0 to 99' COLUMNS z NUMBER PATH '.'))
14 SELECT * FROM full_range
15 MINUS
16 SELECT * FROM c
17 ORDER BY 1;
Z
---------
33
34
35
43
44
45
53
54
55
66
67
68
69
76
77
78
79
86
87
88
89
96
97
98
99
25 rows selected.
Thus, out of 100 numbers these cubes can only represent 75 of the results and top out at 32 as the highest consecutive number they can generate.
The next question then was – can we do better? That is, is there a different combination of digits on the faces of each cube that will allow for a higher number?
This turns out to be quite a bit trickier. First I needed to find all of the possible ways to put 9 digits (0-8, because 6 can be reused) across 6 faces. From math we know the number of distinct combinations of 9 values taken 6 at a time is C(9,6) = 84.
The formula for calculating combinations is: C(n,k) = n! / (k! (n-k)!)
So, for these cubes:
9! / (6! * (9-6)!)
9! / (6! * 3!)
362880 / (720*6)
362880 / 4320
84
So, we have 84 different types of cubes that must be paired with each other. This sounds like another Cartesian join; but… while a Cartesian join is one possible method (and I will show it below) it is not the way I recommend for this problem. Another thing to consider is that I wasn’t looking for a single value from the join, instead I was looking for sets of digits. From the original question I had cubes A and B, each of which was represented in SQL using a WITH-expression that returned a 6 or 7 values. So, for these 84 combinations, I don’t want 84 single values, I want 84 sets of 6 or 7 values. The Oracle database includes a public table type ORA_MINING_NUMBER_NT for holding a set of numbers.
Here is what the combinations might look like using a Cartesian join and we get the expected number of rows:
SQL> WITH
2 digits AS(SELECT n FROM XMLTABLE('0,1,2,3,4,5,6,7,8' COLUMNS n NUMBER PATH '.')),
3 combos
4 AS
5 (SELECT ora_mining_number_nt(a.n,b.n,c.n,d.n,e.n,f.n) t
6 FROM digits a
7 JOIN digits b ON b.n > a.n
8 JOIN digits c ON c.n > b.n
9 JOIN digits d ON d.n > c.n
10 JOIN digits e ON e.n > d.n
11 JOIN digits f ON f.n > e.n)
12 SELECT *
13 FROM combos;
T
-----------------------------------------
ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 5)
ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 6)
ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 7)
.
. (results are abbreviated)
.
ORA_MINING_NUMBER_NT(1, 4, 5, 6, 7, 8)
ORA_MINING_NUMBER_NT(2, 4, 5, 6, 7, 8)
ORA_MINING_NUMBER_NT(3, 4, 5, 6, 7, 8)
ORA_MINING_NUMBER_NT(0, 1, 2, 3, 7, 8)
ORA_MINING_NUMBER_NT(0, 1, 2, 4, 7, 8)
ORA_MINING_NUMBER_NT(0, 1, 2, 5, 7, 8)
84 rows selected.
As I mentioned before though; this works but it’s not the way I’d suggest doing it. Oracle has a native SQL function for generating combinations of subsets of elements in a set. These are the POWERMULTISET functions. In this case the POWERMULTISET_BY_CARDINALITY function is what we’re looking for. You simply give it the source set and the number of elements to be used in each subset combination.
SQL> SELECT COLUMN_VALUE T 2 FROM POWERMULTISET_BY_CARDINALITY( 3 ora_mining_number_nt(0,1,2,3,4,5,6,7,8) 4 ,6); T ----------------------------------------- ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 5) ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 6) ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 7) . . (results are abbreviated) . ORA_MINING_NUMBER_NT(2, 3, 4, 6, 7, 8) ORA_MINING_NUMBER_NT(2, 3, 5, 6, 7, 8) ORA_MINING_NUMBER_NT(2, 4, 5, 6, 7, 8) ORA_MINING_NUMBER_NT(3, 4, 5, 6, 7, 8) 84 rows selected.
This is not only easier but more efficient as well. For this one-time use, small data set, performance isn’t particularly important; but given the choice between a way that works and a better way, I’ll use the better way in the rest of the examples.
There is a problem in the results above though – they don’t take into account the invertible (6,9) values. We can’t simply add 9 to the source set, as that would cause the function (or the join) to return combinations that had both 6 and 9 in them and still limited to subsets of just 6 elements. What we really want is to generate all of the combinations of 0-8, and for each set with a 6, add a 9 to it to create a 7-element set. I’m also displaying the original sets as text to give an easier-to-read visualization of the original subsets generated. I’ll also uses these text values as grouping columns in later steps.
SQL> SELECT (SELECT LISTAGG(COLUMN_VALUE, ',') 2 WITHIN GROUP (ORDER BY COLUMN_VALUE) 3 FROM TABLE(COLUMN_VALUE)) s, 4 CASE 5 WHEN 6 MEMBER OF COLUMN_VALUE THEN 6 COLUMN_VALUE MULTISET UNION ora_mining_number_nt(9) 7 ELSE 8 COLUMN_VALUE 9 END t 10 FROM (SELECT COLUMN_VALUE 11 FROM POWERMULTISET_BY_CARDINALITY( 12 ora_mining_number_nt(0,1,2,3,4,5,6,7,8) 13 ,6)); S T ------------- ------------------------------------------ 0,1,2,3,4,5 ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 5) 0,1,2,3,4,6 ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 6, 9) 0,1,2,3,4,7 ORA_MINING_NUMBER_NT(0, 1, 2, 3, 4, 7) . . (results abbreviated) . 2,3,5,6,7,8 ORA_MINING_NUMBER_NT(2, 3, 5, 6, 7, 8, 9) 2,4,5,6,7,8 ORA_MINING_NUMBER_NT(2, 4, 5, 6, 7, 8, 9) 3,4,5,6,7,8 ORA_MINING_NUMBER_NT(3, 4, 5, 6, 7, 8, 9) 84 rows selected.
Now that I have all 84 variations of cube faces I need to join them with each other like I did in the original query. Since the sets are columns within each row result of the join, I’ll have expand them into something queryable. There are 239008 distinct results from these joins. I’ve restricted the query to returning just the first 10 rows. To aid in sorting and finding distinct pairs within the results I use LEAST and GREATEST to ensure the (A,B) pairs are always arranged so the smaller numbers are in A and the larger in B.
SQL> WITH 2 combos 3 AS 4 (SELECT (SELECT LISTAGG(COLUMN_VALUE, ',') 5 WITHIN GROUP (ORDER BY COLUMN_VALUE) 6 FROM TABLE(COLUMN_VALUE)) s, 7 CASE 8 WHEN 6 MEMBER OF COLUMN_VALUE THEN 9 COLUMN_VALUE MULTISET UNION ora_mining_number_nt(9) 10 ELSE 11 COLUMN_VALUE 12 END t 13 FROM (SELECT COLUMN_VALUE 14 FROM POWERMULTISET_BY_CARDINALITY( 15 ora_mining_number_nt(0,1,2,3,4,5,6,7,8) 16 ,6)) 17 ), 18 results 19 AS 20 (SELECT DISTINCT 21 LEAST(a, b) a, 22 GREATEST(a, b) b, 23 CASE 24 WHEN n = 1 THEN 25 x.COLUMN_VALUE * 10 + y.COLUMN_VALUE 26 ELSE 27 10 * y.COLUMN_VALUE + x.COLUMN_VALUE 28 END c 29 FROM (SELECT c1.s a, 30 c2.s b, 31 c1.t t1, 32 c2.t t2 33 FROM combos c1, combos c2 34 WHERE c1.s != c2.s), 35 TABLE(t1) x, 36 TABLE(t2) y, 37 (SELECT 1 n FROM DUAL 38 UNION ALL 39 SELECT 2 FROM DUAL)) 40 SELECT * 41 FROM results 42 ORDER BY a, b, c 43 FETCH FIRST 10 ROWS ONLY; A B C ----------- ----------- --- 0,1,2,3,4,5 0,1,2,3,4,6 0 0,1,2,3,4,5 0,1,2,3,4,6 1 0,1,2,3,4,5 0,1,2,3,4,6 2 0,1,2,3,4,5 0,1,2,3,4,6 3 0,1,2,3,4,5 0,1,2,3,4,6 4 0,1,2,3,4,5 0,1,2,3,4,6 5 0,1,2,3,4,5 0,1,2,3,4,6 6 0,1,2,3,4,5 0,1,2,3,4,6 9 0,1,2,3,4,5 0,1,2,3,4,6 10 0,1,2,3,4,5 0,1,2,3,4,6 11 10 rows selected.
You can see the pairing of (0,1,2,3,4,5) with (0,1,2,3,4,6) is very limited, only able to count from 00-07 before hitting a gap. The next step will be finding the gaps in each (A,B) pair’s results, and then finding the minimum gap for each of those pairs. I also restrict the results to only those pairs that can start counting from 00.
SQL> WITH 2 combos 3 AS 4 (SELECT (SELECT LISTAGG(COLUMN_VALUE, ',') 5 WITHIN GROUP (ORDER BY COLUMN_VALUE) 6 FROM TABLE(COLUMN_VALUE)) s, 7 CASE 8 WHEN 6 MEMBER OF COLUMN_VALUE THEN 9 COLUMN_VALUE MULTISET UNION ora_mining_number_nt(9) 10 ELSE 11 COLUMN_VALUE 12 END t 13 FROM (SELECT COLUMN_VALUE 14 FROM POWERMULTISET_BY_CARDINALITY( 15 ora_mining_number_nt(0,1,2,3,4,5,6,7,8) 16 ,6)) 17 ), 18 results 19 AS 20 (SELECT DISTINCT 21 LEAST(a, b) a, 22 GREATEST(a, b) b, 23 CASE 24 WHEN n = 1 THEN 25 x.COLUMN_VALUE * 10 + y.COLUMN_VALUE 26 ELSE 27 10 * y.COLUMN_VALUE + x.COLUMN_VALUE 28 END c 29 FROM (SELECT c1.s a, 30 c2.s b, 31 c1.t t1, 32 c2.t t2 33 FROM combos c1, combos c2 34 WHERE c1.s != c2.s), 35 TABLE(t1) x, 36 TABLE(t2) y, 37 (SELECT 1 n FROM DUAL 38 UNION ALL 39 SELECT 2 FROM DUAL)) 40 SELECT a, b, MIN(lagc) 41 FROM (SELECT a, b, c, 42 MIN(c) OVER (PARTITION BY a, b) minc, 43 LAG(c) OVER(PARTITION BY a, b ORDER BY c) lagc 44 FROM results) 45 WHERE minc = 0 AND c - lagc > 1 46 GROUP BY a, b 47 ORDER BY MIN(lagc) DESC, a, b 48 FETCH FIRST 15 ROWS ONLY; A B MIN(LAGC) ----------- ----------- --------- 0,1,2,3,4,5 0,1,2,6,7,8 32 0,1,2,3,4,6 0,1,2,5,7,8 32 0,1,2,3,4,7 0,1,2,5,6,8 32 0,1,2,3,4,8 0,1,2,5,6,7 32 0,1,2,3,5,6 0,1,2,4,7,8 32 0,1,2,3,5,7 0,1,2,4,6,8 32 0,1,2,3,5,8 0,1,2,4,6,7 32 0,1,2,3,6,7 0,1,2,4,5,8 32 0,1,2,3,6,8 0,1,2,4,5,7 32 0,1,2,3,7,8 0,1,2,4,5,6 32 0,1,2,3,4,5 0,1,3,6,7,8 21 0,1,2,3,4,5 0,1,4,6,7,8 21 0,1,2,3,4,5 0,1,5,6,7,8 21 0,1,2,3,4,6 0,1,3,5,7,8 21 0,1,2,3,4,6 0,1,4,5,7,8 21 15 rows selected.
And now after all those variations I have my answer to the second question: Can we do better? The answer is no. Using 2 cubes, even with an invertible (6/9) on a face, the best we can do is 00-32.
I hope you enjoyed this exercise as much as I did and hopefully found something useful in it as well. Questions and comments, as always, are welcome.
Hello Sean,
Interesting exercise 🙂
For some reason, it suddenly reminded me of a “classical” question from an IQ test …
namely: “What 4 integer weight values you can use, so that by combining them without repetitions,
by using additions and subtractions only, you could weigh any integer value between 1 and 40 ?
And, the nice answer is: 1, 3, 9, 27.
And, it can be generalized to 5 numbers: 1, 3, 9, 27, 81 to weigh any value up to 121,
then to 6 numbers: 1,3,9,27,81,243 to weigh any value up to 364, and thus further 🙂
I never tried to use SQL to solve it … this was many years before “my SQL era” 🙂
But, I still remember my satisfaction of solving it with pencil and paper only …
and, of course, with a much younger and stronger brain :):)
Cheers and Enjoy a Happy and Healthy New Year 2021 🙂
Iudith
Howdy! I’m happy to hear from you and glad you found it interesting.
The weights question sounds like an fun exercise. I might have to turn that into an article too.
Thank you and a happy new year to you as well!