I’ve been impressed with the solutions to my little problem of generating a symmetric Pascal matrix using SQL. Charles Hooper in particular has provided some very nice commentary on the problem, complete with diagrams and 2 alternative solutions.
I thought I’d walk through my solution in order to explain my thought process and see if it resonates with anyone.
Usually when I think about generating rows with SQL I think about the Oracle “trick” of using the CONNECT BY clause to generate rows:
1 |
select level from dual connect by level <= k |
You’ll see a lot of constructs like this in the solutions provided by commenters.
However, lately I’ve been tending more toward the ANSI SQL Recursive construct instead, which works in Oracle and many other SQL databases:
1 2 3 4 5 6 |
with f (n) as ( select 1 from dual union all select n+1 from f where n < k ) select n from f; |
I think the symmetric Pascal matrix lends itself to this kind of technique especially because it involves factorials.
Charles (and others) have used the Wikipedia definition of the Pascal matrix for each cell entry which is Aij = (i+j-2)! / ((i-1)!(j-1)!). And most of the solutions have used a clever way to calculate the necessary factorials:
1 |
select exp(sum(ln(level))) from dual connect by level <=n |
However, the neat thing about factorials is that they are easily defined in recursive terms:
f(0) = 1
f(n+1) = (n+1) * f(n)
And this definition maps really nicely to the ANSI SQL Recursive construct:
1 2 3 4 5 6 |
with f(n,nf) as ( select 0,1 from dual union all select n+1, n+1 * nf from f where n < k ) select n,nf from from f; |
Given this idea of using the Recursive construct, I set about seeing if I could use it to solve my challenge…
You can see how I got on by reading the full article on my Oracle Musings blog.
Load comments