{"id":73308,"date":"2012-06-19T10:55:45","date_gmt":"2012-06-19T10:55:45","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/uncategorized\/pascal-matrix-sql-puzzle-solution\/"},"modified":"2021-07-14T13:07:56","modified_gmt":"2021-07-14T13:07:56","slug":"pascal-matrix-sql-puzzle-solution","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/oracle-databases\/pascal-matrix-sql-puzzle-solution\/","title":{"rendered":"Pascal matrix SQL puzzle solution"},"content":{"rendered":"<p>I&#8217;ve been impressed with the solutions to\u00a0<a href=\"http:\/\/www.oraclemusings.com\/?p=221\">my little problem<\/a>\u00a0of generating a symmetric Pascal matrix using SQL.\u00a0<a href=\"http:\/\/hoopercharles.wordpress.com\/2012\/06\/14\/sql-challenges\/\">Charles Hooper in particular<\/a>\u00a0has provided some very nice commentary on the problem, complete with diagrams and 2 alternative solutions.<\/p>\n<p>I thought I\u2019d walk through my solution in order to explain my thought process and see if it resonates with anyone.<\/p>\n<p>Usually when I think about generating rows with SQL I think about the Oracle \u201ctrick\u201d of using the CONNECT BY clause to generate rows:<\/p>\n<pre>select level from dual connect by level <= k<\/pre>\n<p>You\u2019ll see a lot of constructs like this in the solutions provided by commenters.<\/p>\n<p>However, lately I\u2019ve been tending more toward the ANSI SQL Recursive construct instead, which works in Oracle and many other SQL databases:<\/p>\n<pre>\r\nwith f (n) as (\r\nselect 1 from dual\r\nunion all\r\nselect n+1 from f where n < k\r\n)\r\nselect n from f;\r\n<\/pre>\n<p>I think the symmetric Pascal matrix lends itself to this kind of technique especially because it involves factorials.<br \/>\nCharles (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:<\/p>\n<pre>select exp(sum(ln(level))) from dual connect by level <=n<\/pre>\n<p>However, the neat thing about factorials is that they are easily defined in recursive terms:<\/p>\n<p>f(0) = 1<br \/>\nf(n+1) = (n+1) * f(n)<\/p>\n<p>And this definition maps really nicely to the ANSI SQL Recursive construct:<\/p>\n<pre>\r\nwith f(n,nf) as (\r\nselect 0,1 from dual\r\nunion all\r\nselect n+1, n+1 * nf from f where n < k\r\n)\r\nselect n,nf from from f;\r\n<\/pre>\n<p>Given this idea of using the Recursive construct, I set about seeing if I could use it to solve my challenge...<\/p>\n<p>You can see how I got on by reading the full article on my <a href=\"http:\/\/www.oraclemusings.com\/?p=226\" target=\"blank\">Oracle Musings blog<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve been impressed with the solutions to\u00a0my little problem\u00a0of generating a symmetric Pascal matrix using SQL.\u00a0Charles Hooper in particular\u00a0has provided some very nice commentary on the problem, complete with diagrams and 2 alternative solutions. I thought I\u2019d walk through my solution in order to explain my thought process and see if it resonates with anyone. Usually when I think about&hellip;<\/p>\n","protected":false},"author":316178,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143533],"tags":[],"coauthors":[],"class_list":["post-73308","post","type-post","status-publish","format-standard","hentry","category-oracle-databases"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/73308","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/316178"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=73308"}],"version-history":[{"count":1,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/73308\/revisions"}],"predecessor-version":[{"id":91758,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/73308\/revisions\/91758"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=73308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=73308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=73308"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=73308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}