New SQL Puzzle

Sorry for the drought — to keep everyone’s mind fresh, how about a little puzzle?

Use SQL to create a symmetric Pascal matrix, with the output being (i,j,v). So that a Pascal matrix of size 4 would end up as:

1,1,1
2,1,1
3,1,1
4,1,1
1,2,1
2,2,2
3,2,3
4,2,4
1,3,1
2,3,3
3,3,6
4,3,10
1,4,1
2,4,4
3,4,10
4,4,20

Try to stay with ANSI SQL 2008 if possible — bailing out to other languages and functions is discouraged :-)

Efficiency is an interesting idea here, as it’s pretty easy to do this by brute force calculations of factorials for every entry — but where’s the fun in that?

Extra credit for solutions which can take in the matrix size as some sort of parameter.

14 Responses to “New SQL Puzzle”

  1. Charles Hooper Says:

    I put together a solution using WITH blocks and Oracle specific syntax, so a solution is possible using just SQL (but I am not sure if that Oracle specific syntax qualifies as ANSI SQL 2008).

    This is my output:

    I J V
    – — —-
    1 1 1
    2 1 1
    3 1 1
    4 1 1
    1 2 1
    2 2 2
    3 2 3
    4 2 4
    1 3 1
    2 3 3
    3 3 6
    4 3 10
    1 4 1
    2 4 4
    3 4 10
    4 4 20

    Any interest in seeing the Oracle specific code?

  2. ddelmoli Says:

    Charles, sure! WITH blocks aren’t Oracle-specific (I was able to run my solution in Postgres and Oracle), so I’d love to see what you came up “with”. :-)

  3. Charles Hooper Says:

    I have a degree in mathematics, but that degree is very, very rusty. Based on the provided link, we are trying to produce an array like the following, where the value in a cell in the array is the sum of the value immediately above and immediately to the left:

    1 1 1 1 1
    1 2 3 4 5
    1 3 6 10 15
    1 4 10 20 35
    1 5 15 35 70

    The first rows have the following values:

    1^0 + 2^0
    1^0 + 2^0 + 3^0
    1^0 + 2^0 + 3^0 + 4^0
    1^0 + 2^0 + 3^0 + 4^0 + 5^0

    The second row has the following values:

    1^0 + 2^0 + 1^0
    1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 = 1 * 3^0 + 2 * 2^0 + 3 * 1^0
    1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 = 1 * 4^0 + 2 * 3^0 + 3* 2^0 + 4 * 1^0
    1^0 + 2^0 + 3^0 + 4^0 + 5^0 + 1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 = 1 * 5^0 + 2 * 4^0 + 3 * 3^0 + 4 * 2^0 + 5 * 1^0

    The third row:

    1^0 + 2^0 + 1^0 + 1^0
    1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 1^0 + 1^0 = 1 * 3^0 + 3 * 2^0 + 6 * 1^0
    1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 1^0 + 1^0 = 1 * 4^0 + 3 * 3^0 + 6 * 2^0 + 10 * 1^0
    1^0 + 2^0 + 3^0 + 4^0 + 5^0 + 1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 3^0 + 4^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 3^0 + 1^0 + 2^0 + 1^0 + 1^0 + 2^0 + 1^0 + 1^0

    Now we can just… cheat and look at the formula from the article that you provided:

    (i + j – 2)! / ((i – 1)! * (j – 1)!)

    ! is short for factorial

    4! = 4 * 3 * 2 * 1
    3! = 3 * 2 * 1
    2! = 2 * 1
    1! = 1

    Calculating the factorial is a bit of a challenge. The SUM analytic function can be used to generate running sums of a column, but there is no equivalent for running products of a column.
    If we calculate the natural log of a column value, generate a running sum of those natural log values, and then generate the anti-log, we can essentially generate a running product (factorial) for a column:

    WITH
    FACTORIAL AS
    (SELECT /*+ MATERIALIZE */
    N,
    EXP(SUM(LN(N)) OVER (ORDER BY N)) FACTORIAL
    FROM
    (SELECT
    ROWNUM N,
    LN(ROWNUM) RNL
    FROM
    DUAL
    CONNECT BY
    LEVEL<=20))
    SELECT
    N,
    FACTORIAL F
    FROM
    FACTORIAL;

    N F
    – ———-
    1 1
    2 2
    3 6
    4 24
    5 120
    6 720
    7 5040
    8 40320
    9 362880
    10 3628800
    11 39916800
    12 479001600
    13 6227020800
    14 8.7178E+10
    15 1.3077E+12
    16 2.0923E+13
    17 3.5569E+14
    18 6.4024E+15
    19 1.2165E+17
    20 2.4329E+18

    One problem is that with the formula (i + j – 2)!, we could very well need to calculate 0!, which is defined as 1. To accomplish this, we need to add the following inside the WITH block:

    UNION ALL
    SELECT
    0 N,
    1 FACTORIAL
    FROM
    DUAL

    Now it is just a matter of defining how large of an array is needed, performing a Cartesian join to achieve the correct number of rows (I * J), and placing the factorial values where necessary:

    WITH
    FACTORIAL AS
    (SELECT /*+ MATERIALIZE */
    N,
    EXP(SUM(LN(N)) OVER (ORDER BY N)) FACTORIAL
    FROM
    (SELECT
    ROWNUM N,
    LN(ROWNUM) RNL
    FROM
    DUAL
    CONNECT BY
    LEVEL<=20)
    UNION ALL
    SELECT
    0 N,
    1 FACTORIAL
    FROM
    DUAL),
    I AS
    (SELECT /*+ MATERIALIZE */
    ROWNUM I
    FROM
    DUAL
    CONNECT BY
    LEVEL<=4),
    J AS
    (SELECT /*+ MATERIALIZE */
    ROWNUM J
    FROM
    DUAL
    CONNECT BY
    LEVEL<=4)
    SELECT
    I.I,
    J.J,
    F1.FACTORIAL / (F2.FACTORIAL * F3.FACTORIAL) V
    FROM
    FACTORIAL F1,
    FACTORIAL F2,
    FACTORIAL F3,
    I,
    J
    WHERE
    F1.N=(I.I + J.J – 2)
    AND F2.N=(I.I – 1)
    AND F3.N=(J.J – 1)
    ORDER BY
    J.J,
    I.I;

  4. SQL Challenges « Charles Hooper's Oracle Notes Says:

    [...] Dominic’s challenge probably would not be much of a challenge if we could just type in formulas like the above into a SQL statement.  Give his challenge a try to see if you are able to derive a unique solution to the problem.  I probably spent a couple of minutes (maybe 60 seconds with the help of copy and paste) creating the above example using Microsoft Excel, but spent a couple of hours trying to produce a solution that worked using SQL. [...]

  5. Timo Raitalaakso Says:

    A PostgreSQL approach – Mixing analytic functions and recursive subquery factoring. http://rafudb.blogspot.fi/2012/06/pascal-matrix.html

  6. ddelmoli Says:

    Nice one Timo — glad to see another approach!

  7. Anton Says:

    select i
    , j
    , ( select exp( sum( ln( level ) ) ) from dual connect by level <= i + j – 2 )
    / ( select exp( sum( ln( level ) ) ) from dual connect by level <= i – 1 )
    / ( select exp( sum( ln( level ) ) ) from dual connect by level <= j – 1 ) v
    from ( select mod( level – 1, n ) + 1 i
    , ceil( level / n ) j
    from ( select 8 n from dual )
    connect by level <= n * n
    )

  8. ddelmoli Says:

    Anton, good one — I particularly like the single reference to the size of the array. And so far I’ve been impressed with the use of the exp(sum(ln())) construct to calculate the factorials.

  9. Arjen Says:

    I think the statement below does the trick:

    with r as (select level nr from dual connect by level <= 9 ) , z as (select r.nr row_nr , c.nr col_nr from r r , r c ) , p as (select * from z model dimension by (row_nr, col_nr) measures (cast(null as number) new_val) rules ( new_val[any, any] order by row_nr, col_nr = greatest(case when new_val[cv()-1, cv()] is null then 0 else new_val[cv()-1, cv()] end + case when new_val[cv(),cv()-1] is null then 0 else new_val[cv(),cv()-1] end ,1 ) ) ) select * from p pivot (sum(new_val) for col_nr in (1,2,3,4,5,6,7,8,9)) order by row_nr –, col_nr ;

    The pivot is just for formatting the output. If you comment it out, the fixed number for the matrix size can be made dynamic.

  10. Kim Berg Hansen Says:

    I admit this is probably pure Oracle (I have no idea which other databases might support the MODEL clause), but it was fun to make so I might as well share it :-)

    SQL> variable matrixsize number
    SQL>
    SQL> begin
    2 :matrixsize := 4;
    3 end;
    4 /

    PL/SQL procedure successfully completed.

    SQL>
    SQL> select
    2 i, j, v
    3 from dual
    4 model
    5 dimension by (1 i, 1 j)
    6 measures (1 v)
    7 rules automatic order (
    8 v[for i from 2 to :matrixsize increment 1, 1] = 1,
    9 v[1, for j from 2 to :matrixsize increment 1] = 1,
    10 v[for i from 2 to :matrixsize increment 1,
    11 for j from 2 to :matrixsize increment 1
    12 ] = v[cv(i)-1,cv(j)] + v[cv(i),cv(j)-1]
    13 )
    14 order by
    15 i, j;

    I J V
    ———- ———- ———-
    1 1 1
    1 2 1
    1 3 1
    1 4 1
    2 1 1
    2 2 2
    2 3 3
    2 4 4
    3 1 1
    3 2 3
    3 3 6
    3 4 10
    4 1 1
    4 2 4
    4 3 10
    4 4 20

    16 rows selected.

  11. Charles Hooper Says:

    Here is another possible solution that uses SYS_CONNECT_BY_PATH to create formulas and XMLQUERY to calculate the value of those formulas to generate the factorial values.

    First, the formulas are built:

    SELECT
    ROWNUM N,
    FF
    FROM
    (SELECT
    ’1′||SYS_CONNECT_BY_PATH(ROWNUM,’ * ‘) FF
    FROM
    DUAL
    CONNECT BY
    LEVEL<=8
    ORDER BY 1);

    N FF
    - ———————————
    1 1 * 1
    2 1 * 1 * 2
    3 1 * 1 * 2 * 3
    4 1 * 1 * 2 * 3 * 4
    5 1 * 1 * 2 * 3 * 4 * 5
    6 1 * 1 * 2 * 3 * 4 * 5 * 6
    7 1 * 1 * 2 * 3 * 4 * 5 * 6 * 7
    8 1 * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8

    As shown above, I am only planning to calculate through 8!, but that will later be changed to 20!.

    Next, the value of the formulas are calculated:

    SELECT
    ROWNUM N,
    XMLQUERY((FF) RETURNING CONTENT).GETNUMBERVAL() FACTORIAL
    FROM
    (SELECT
    ’1′||SYS_CONNECT_BY_PATH(ROWNUM,’ * ‘) FF
    FROM
    DUAL
    CONNECT BY
    LEVEL<=8
    ORDER BY 1);

    N FACTORIAL
    - ———-
    1 1
    2 2
    3 6
    4 24
    5 120
    6 720
    7 5040
    8 40320

    The above SQL statement does not calculate 0!, so that problem will be handled later by a DECODE statement.

    The following will be used to derive the i and j values for an 8 x 8 matrix:

    SELECT
    MOD(ROWNUM-1,8)+1 I,
    TRUNC((ROWNUM-1)/8)+1 J
    FROM
    DUAL
    CONNECT BY
    LEVEL <= 8 * 8;

    The final query uses two WITH block subqueries, and scalar subqueries to pull the correct factorial value for the calculation:

    WITH
    FACTORIAL AS
    (SELECT /*+ MATERIALIZE */
    ROWNUM N,
    XMLQUERY((FF) RETURNING CONTENT).GETNUMBERVAL() FACTORIAL
    FROM
    (SELECT
    ’1′||SYS_CONNECT_BY_PATH(ROWNUM,’ * ‘) FF
    FROM
    DUAL
    CONNECT BY
    LEVEL<=20
    ORDER BY 1)),
    NUMBERS AS
    (SELECT
    MOD(ROWNUM-1,8)+1 I,
    TRUNC((ROWNUM-1)/8)+1 J
    FROM
    DUAL
    CONNECT BY
    LEVEL <= 8 * 8)
    SELECT
    N.I,
    N.J,
    DECODE((N.I + N.J – 2),0,1,
    (SELECT
    F.FACTORIAL
    FROM
    FACTORIAL F
    WHERE
    F.N=(N.I + N.J – 2))) /
    DECODE((N.I – 1),0,1,
    (SELECT
    F.FACTORIAL
    FROM
    FACTORIAL F
    WHERE
    F.N=(N.I – 1))) /
    DECODE((N.J – 1),0,1,
    (SELECT
    F.FACTORIAL
    FROM
    FACTORIAL F
    WHERE
    F.N=(N.J – 1))) V
    FROM
    NUMBERS N;

    I J V
    – — —–
    1 1 1
    2 1 1
    3 1 1
    4 1 1
    5 1 1
    6 1 1
    7 1 1
    8 1 1
    1 2 1
    2 2 2
    3 2 3
    4 2 4
    5 2 5
    6 2 6
    7 2 7
    8 2 8
    1 3 1
    2 3 3
    3 3 6
    4 3 10
    5 3 15
    6 3 21
    7 3 28
    8 3 36
    1 4 1
    2 4 4
    3 4 10
    4 4 20
    5 4 35
    6 4 56
    7 4 84
    8 4 120
    1 5 1
    2 5 5
    3 5 15
    4 5 35
    5 5 70
    6 5 126
    7 5 210
    8 5 330
    1 6 1
    2 6 6
    3 6 21
    4 6 56
    5 6 126
    6 6 252
    7 6 462
    8 6 792
    1 7 1
    2 7 7
    3 7 28
    4 7 84
    5 7 210
    6 7 462
    7 7 924
    8 7 1716
    1 8 1
    2 8 8
    3 8 36
    4 8 120
    5 8 330
    6 8 792
    7 8 1716
    8 8 3432

  12. anton Says:

    with pascal( i, j, v, n, pv )
    as ( select 1, 1, 1, 8, mdsys.sdo_numtab( 1 )
    from dual
    union all
    select case when i = n then 1 else i + 1 end
    , case when i = n then j + 1 else j end
    , case when i = n or j = 1 then 1 else v + ( select column_value from table( pv ) where rownum < 2 ) end
    , n
    , case when cardinality( pv ) = n then pv multiset except ( select mdsys.sdo_numtab( column_value ) from table( pv ) where rownum < 2 ) else pv end multiset union mdsys.sdo_numtab( case when i = n or j = 1 then 1 else v + ( select column_value from table( pv ) where rownum < 2 ) end )
    from pascal
    where i < n or j < n
    )
    select i, j, v
    from pascal

  13. Oracle Musings » Pascal matrix SQL puzzle solution Says:

    [...] Comments anton on New SQL PuzzleCharles Hooper on New SQL PuzzleKim Berg Hansen on New SQL [...]

  14. Pascal matrix SQL puzzle solution – All Things Oracle Says:

    [...] been impressed with the solutions to my little problem of generating a symmetric Pascal matrix using SQL. Charles Hooper in particular has provided [...]

Leave a Reply

Posting code can be a pain. To make sure your code doesn't get eaten, you may want to pre-format it first by using HTML Encoder