Skip to Main Content

SQL & PL/SQL

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

Interested in getting your voice heard by members of the Developer Marketing team at Oracle? Check out this post for AppDev or this post for AI focus group information.

Pascal's triangle or binomial coefficients

146850Nov 14 2005 — edited May 3 2008
<font color="red">you know Pascal's triangle like below.</font>

1
11
121
1331
14641
...
...

my question is to find out a query giving nth sequence,
that is to say,

when n=1, that query yields
1

when n=2
1
1

when n=3
1
2
1

when n=4
1
3
3
1

...
...

(oh, but you have NOT to use any subqueries)


for more SQL problems & questions, please visit
http://cafe.daum.net/oraclesqltuning

Comments

Ghulam Mustafa Butt

If you dont want subqueries, you can try in PL/SQL.

Assuming your biggest length of the charector is 6, If the length is more you can copy and paste more ElsIf's:

DECLARE
  lv_text   VARCHAR2(50);
  lv_len    NUMBER;
  CURSOR c1 IS
  SELECT text, length(text)
    FROM table;
BEGIN
  OPEN c1;
  LOOP
    FETCH c1 INTO lv_text;
    EXIT WHEN c1%NOTFOUND;
    IF nvl(lv_length) = 1 THEN
       dbms_output.put_line (lv_text);
    ELSIF
       nvl(lv_length) = 2 THEN
       FOR i IN 1..2 LOOP
         dbms_output.put_line (substr(lv_text, i, i));
    ELSIF
       nvl(lv_length) = 3 THEN
       FOR i IN 1..3 LOOP
         dbms_output.put_line (substr(lv_text, i, i));
    ELSIF
       nvl(lv_length) = 4 THEN
       FOR i IN 1..4 LOOP
         dbms_output.put_line (substr(lv_text, i, i));
    ELSIF
       nvl(lv_length) = 5 THEN
       FOR i IN 1..5 LOOP
         dbms_output.put_line (substr(lv_text, i, i));
    ELSIF
       nvl(lv_length) = 6 THEN
       FOR i IN 1..6 LOOP
         dbms_output.put_line (substr(lv_text, i, i));
    END IF;
  END LOOP;
  CLOSE c1;
END;
/

Not tested !

HTH
Ghulam

452095
Are there restrictions on creating functions?
Ghulam Mustafa Butt
FOR i IN 1..2 LOOP
dbms_output.put_line (substr(lv_text, i, i));
END LOOP;

Sorry you have to add END LOOP; at the end of all For Loops.

HTH
Ghulam
146850
sorry, but i want it in one SQL , not PL/SQL

a variable n is given.
no subqueries allowed.

* this is not a sort of exam.
146850
and the result is n rows....

when n=1
1 (one row)

when n=2
1
1 (two rows)

where n=3
1
2
1 (three rows)
...
...
APC
* this is not a sort of exam.
Do you have a solution and you're just testing us, or is this a kite flying exercise to see whether its possible?

I imagine it might be possible to do this with the Model clause but not having 10g to try it on I can't explore this theory at the moment.

Cheers, APC
94799
I recall the triangle starting at row 0 (perhaps that is a matter of choice)...
Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Production
With the Partitioning, OLAP and Data Mining options

SQL> VARIABLE n NUMBER;
SQL> EXEC :n := 0;

PL/SQL procedure successfully completed.

SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
  3               OVER (ORDER BY LEVEL)) *
  4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
  5               OVER (ORDER BY LEVEL DESC))) n
  6  FROM   dual
  7  CONNECT BY LEVEL <= CEIL (:n + 1);

         N
----------
         1

SQL> EXEC :n := 1;

PL/SQL procedure successfully completed.

SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
  3               OVER (ORDER BY LEVEL)) *
  4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
  5               OVER (ORDER BY LEVEL DESC))) n
  6  FROM   dual
  7  CONNECT BY LEVEL <= CEIL (:n + 1);

         N
----------
         1
         1

SQL> EXEC :n := 2;

PL/SQL procedure successfully completed.

SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
  3               OVER (ORDER BY LEVEL)) *
  4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
  5               OVER (ORDER BY LEVEL DESC))) n
  6  FROM   dual
  7  CONNECT BY LEVEL <= CEIL (:n + 1);

         N
----------
         1
         2
         1

SQL> EXEC :n := 3;

PL/SQL procedure successfully completed.

SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
  3               OVER (ORDER BY LEVEL)) *
  4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
  5               OVER (ORDER BY LEVEL DESC))) n
  6  FROM   dual
  7  CONNECT BY LEVEL <= CEIL (:n + 1);

         N
----------
         1
         3
         3
         1

SQL> EXEC :n := 4;

PL/SQL procedure successfully completed.

SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
  3               OVER (ORDER BY LEVEL)) *
  4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
  5               OVER (ORDER BY LEVEL DESC))) n
  6  FROM   dual
  7  CONNECT BY LEVEL <= CEIL (:n + 1);

         N
----------
         1
         4
         6
         4
         1

SQL> EXEC :n := 5;

PL/SQL procedure successfully completed.

SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
  3               OVER (ORDER BY LEVEL)) *
  4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
  5               OVER (ORDER BY LEVEL DESC))) n
  6  FROM   dual
  7  CONNECT BY LEVEL <= CEIL (:n + 1);

         N
----------
         1
         5
        10
        10
         5
         1

6 rows selected.

SQL> EXEC :n := 6;

PL/SQL procedure successfully completed.

SQL> SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  2            EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) 
  3               OVER (ORDER BY LEVEL)) *
  4            EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1))) 
  5               OVER (ORDER BY LEVEL DESC))) n
  6  FROM   dual
  7  CONNECT BY LEVEL <= CEIL (:n + 1);

         N
----------
         1
         6
        15
        20
        15
         6
         1

7 rows selected.

SQL> 
Laurent Schneider
by the way, how are you going to generate multiple rows in plain SQL?
def n=5

with fac as (select rownum n,exp(sum(ln(rownum))over(order by rownum)) fac from all_objects where rownum<12)
select nvl(n.fac/r.fac/nr.fac,1)
from (select rownum-1 r from all_objects where rownum<=&n+1),
    fac n, fac r, fac nr
where n.n (+)=&n and r.n (+)=r and nr.n(+)=(&n-r)
order by r
/

                        1
                        5
                       10
                       10
                        5
                        1
Message was edited by:
Laurent Schneider
padders, your one is better ;-)
Laurent Schneider
note that I consider CONNECT BY without PRIOR to be disallowed... as specified in the doc, CONNECT BY must contain a PRIOR operator defining the parent-child relationship... but this is just a small note of mines and feel free to use CONNECT BY if you like / trust it ;-)

Message was edited by:
Laurent Schneider
still padders method with analytics rules, because it does not use subquery
452095
Should this work for all values of :n?

When :n = 10...

N
0
10
45
120
210
252
210
120
45
10
0
APC

Should this work for all values of :n?

interesting. Padders version works for me (allowing for the fatc that the CONNECT BY trick doesn't work propperly in 9.2)...

SQL> EXEC :n := 10

PL/SQL procedure successfully completed.

SQL> SELECT * FROM
  2  (
  3   SELECT EXP (SUM (LN (LEVEL)) OVER ()) / (:n + 1) / (
  4              EXP (SUM (LN (GREATEST (LEVEL - 1, 1)))
  5                 OVER (ORDER BY LEVEL)) *
  6              EXP (SUM (LN (GREATEST (:n - (LEVEL - 1), 1)))
  7                 OVER (ORDER BY LEVEL DESC))) n
  8    FROM   dual
  9    CONNECT BY LEVEL <= CEIL (:n + 1))
 10  /
         N
----------
         1
        10
        45
       120
       210
       252
       210
       120
        45
        10
         1

11 rows selected.

SQL> 

Cheers, APC

49084
interesting. Padders version works for me (allowing for the fatc that the CONNECT BY trick doesn't work propperly in 9.2)...
There's an easy workaround for that (I'm sure you're well aware, but just for those who don't know yet):
SELECT EXP (SUM (LN (L)) OVER ()) / (:n + 1) / (
      EXP (SUM (LN (GREATEST (L - 1, 1))) 
                 OVER (ORDER BY L)) *
             EXP (SUM (LN (GREATEST (:n - (L - 1), 1))) 
               OVER (ORDER BY L DESC))) n
  FROM   ( SELECT LEVEL L 
             FROM DUAL 
          CONNECT BY LEVEL <= CEIL (:n + 1)
         )
/
It works perfect on my 9.2 box.

MHE
452095
I'm using 9.2.0.6.0... so there's a flaw with connect by in this version thats affecting the output of the query sometimes? When I use values 0 through 9 and 11 it appears to return the correct values, but for whatever reason it doesn't work when :n equals 10.

Can anyone explain how the query works, not what each function does individually, but why when you put them together they return pascal's triangle?
APC
I'm using 9.2.0.6.0
Me likewise
Can anyone explain how the query works
basically the query is calculating the value of each element in the row; it implements the nCr method using analytic functions to generate factorials.

Cheers, APC
452095
Thanks for your reply APC. I understand the formula (I accept that it works although I have no idea why it works). But how do the functions that padders uses perform the same functionality that a factorial (!) does?
245482
The following are all the same. This is a (sort of) common trick for implementing factorial.
select exp(sum(ln(level)))
  from dual
connect by level <= N

exp(ln(1) + ln(2) + ... ln(N))

exp(ln(1)) * exp(ln(2)) * ... exp(ln(N))

1*2*...N

N!
select x,y,count(1) from (
select x,y,sys_connect_by_path('['||x||','||y||'>',' ') path
from (
select level x from dual
connect by level < 5
), (
select level y from dual
connect by level < 5
) connect by prior x+1 = x and prior y = y
or prior x = x and prior y+1 = y
start with x = 1 and y = 1
) group by x,y;

Nice exercise to include into a book.
452095
Thanks Scott, I must have missed that day in my SQL class.
146850
good job, padders.

and my solution is
SELECT       EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) OVER ())
           / EXP (SUM (LN (GREATEST (LEVEL - 1, 1))) OVER (ORDER BY LEVEL))
           / EXP (SUM (LN (GREATEST (:n - LEVEL, 1))) OVER (ORDER BY LEVEL DESC)
                 ) bin_coef
      FROM DUAL
CONNECT BY LEVEL <= :n
Query Your Dream & Future at
http://www.soqool.com
94799
Just a couple of variations on the theme using a table function as a row source and a user-defined product aggregate (source available on request).
Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Production
With the Partitioning, OLAP and Data Mining options

SQL> VARIABLE r NUMBER;
SQL> EXEC :r := 5;

PL/SQL procedure successfully completed.

SQL> SELECT product (GREATEST (n, 1)) OVER () / 
  2         product (GREATEST (n, 1)) OVER (ORDER BY n) /
  3         product (GREATEST (:r - n, 1)) OVER (ORDER BY n DESC) n
  4  FROM   TABLE (many (0, :r));

         N
----------
         1
         5
        10
        10
         5
         1

6 rows selected.

SQL> SELECT SUBSTR (SYS_CONNECT_BY_PATH (
  2            r, ','), 2) pascals_triangle
  3  FROM  (SELECT a.n an, b.n bn, 
  4                product (GREATEST (b.n, 1)) OVER (
  5                   PARTITION BY a.n) /
  6                product (GREATEST (b.n, 1)) OVER (
  7                   PARTITION BY a.n ORDER BY b.n) /
  8                product (GREATEST (a.n - b.n, 1)) OVER (
  9                   PARTITION BY a.n ORDER BY b.n DESC) r
 10         FROM   TABLE (many (0, :r)) a, 
 11                TABLE (many (0, a.n)) b) 
 12  WHERE  CONNECT_BY_ISLEAF = 1
 13  START WITH bn = 0
 14  CONNECT BY an = PRIOR an AND bn = PRIOR bn + 1;

PASCALS_TRIANGLE
--------------------------------------------------------------------------------
1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
1,5,10,10,5,1

6 rows selected.

SQL> 
Laurent Schneider
strike !
94799
LOL. Is this better?
Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Production
With the Partitioning, OLAP and Data Mining options

SQL> VARIABLE r NUMBER;
SQL> EXEC :r := 10;

PL/SQL procedure successfully completed.

SQL> SELECT LPAD (' ', 5 * (:r - an) / 2) ||
  2           REPLACE (SYS_CONNECT_BY_PATH (
  3              LPAD (r, 5), '/'), '/') pascals_triangle
  4  FROM  (SELECT a.n an, b.n bn,
  5                product (GREATEST (b.n, 1)) OVER (
  6                   PARTITION BY a.n) /
  7                product (GREATEST (b.n, 1)) OVER (
  8                   PARTITION BY a.n ORDER BY b.n) /
  9                product (GREATEST (a.n - b.n, 1)) OVER (
 10                   PARTITION BY a.n ORDER BY b.n DESC) r
 11         FROM   TABLE (many (0, :r)) a,
 12                TABLE (many (0, a.n)) b)
 13  WHERE  CONNECT_BY_ISLEAF = 1
 14  START WITH bn = 0
 15  CONNECT BY an = PRIOR an AND bn = PRIOR bn + 1;

PASCALS_TRIANGLE
--------------------------------------------------------------------------------
                             1
                          1    1
                        1    2    1
                     1    3    3    1
                   1    4    6    4    1
                1    5   10   10    5    1
              1    6   15   20   15    6    1
           1    7   21   35   35   21    7    1
         1    8   28   56   70   56   28    8    1
      1    9   36   84  126  126   84   36    9    1
    1   10   45  120  210  252  210  120   45   10    1

11 rows selected.

SQL> 
Nicolas Gasparotto
Splendid !!

Nicolas.
Aketi Jyuuzou
SQL> col PASCALS_TRIANGLE for a80
SQL> 
SQL> with Renban as (
  2  select RowNum-1 as Val
  3  from dual connect by Level <= 15),
  4  WorkView as (
  5  select Ra.Val as n,Rb.Val as r
  6  from Renban Ra,Renban Rb
  7  where Ra.Val >= Rb.Val),
  8  RowList as (
  9  select n,r,
 10  case when r=0 then 1
 11  else (select round(exp(sum(Ln(a.N-b.R+1)))) from WorkView b
 12        where b.N=a.N
 13          and b.R > 0
 14          and b.R<=a.R) end as NPR,
 15  case when r=0 then 1
 16  else (select round(exp(sum(Ln(b.R)))) from WorkView b
 17         where b.N=a.N
 18           and b.R > 0
 19           and b.R<=a.R) end as "R!"
 20  from WorkView a),
 21  PascalTriangle as (
 22  select N,SubStr(sys_connect_by_path(Val,' '),2) as Pascal
 23   from (select N,R,NPR / "R!" as Val from RowList)
 24  where Connect_by_IsLeaf = 1
 25  start with R=0
 26  connect by prior N=N
 27         and prior R=R-1)
 28  select Lpad(' ',(MaxLength-Length(Pascal))/2-1) || Pascal as PASCALS_TRIANGLE
 29  from PascalTriangle,(select max(Length(Pascal)) as MaxLength from PascalTriangle);

PASCALS_TRIANGLE
--------------------------------------------------------------------------------
                           1
                          1 1
                         1 2 1
                        1 3 3 1
                       1 4 6 4 1
                     1 5 10 10 5 1
                    1 6 15 20 15 6 1
                  1 7 21 35 35 21 7 1
                 1 8 28 56 70 56 28 8 1
              1 9 36 84 126 126 84 36 9 1
          1 10 45 120 210 252 210 120 45 10 1
        1 11 55 165 330 462 462 330 165 55 11 1
      1 12 66 220 495 792 924 792 495 220 66 12 1
  1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
146850
Thanks, Vadim Tropashko.
I'm reading your book, SQL Design Patterns.

Query Your Dream & Future at
http://www.soqool.com
572471
iterative power of model:
SQL> var p number;
SQL> exec :p:=10;

PL/SQL procedure successfully completed
p
---------
10

SQL> 
SQL> select n from (select 1 n from dual)
  2   model
  3    dimension by (0 dim)
  4    measures (n, n n2)
  5     rules iterate(1000) until (iteration_number+1>=:p)
  6      (n2[ANY]=n[CV()],
  7       n[for dim from 1 to iteration_number increment 1] = nvl(n2[CV()]+n2[CV()-1],1))
  8  /

         N
----------
         1
         9
        36
        84
       126
       126
        84
        36
         9
         1

10 rows selected
p
---------
10

SQL> 
Alessandro Rossi

Here it is.

Some needed stuff.

create or replace type string_table is table of varchar2(4000)
/

CREATE OR REPLACE 
FUNCTION tab2string ( tab in string_table, delimitatore in varchar2  default ',' ) return varchar2 as
	out_string varchar2(32767);
begin
	if ( cardinality(tab) > 0 ) then
		for i in tab.first .. tab.last loop
			if ( i != tab.first ) then
				out_string := out_string||delimitatore;
			else
				out_string := '';
			end if;
			out_string := out_string || tab(i);
		end loop;
		return out_string;
	else
		return null;
	end if;
end;
/

create or replace function fact( 
	n in integer
) return integer
as
	out_val number;
begin
	out_val := 1;
	for i in 1 .. n loop
		out_val := out_val * i;
	end loop;
	return out_val; 
end;
/

and some output ( n = 6 )

Processing ...
select fact(:n)/(fact(rownum-1)*fact(:n-rownum+1)) val
from dual
connect by rownum-1 <= :n

Query finished, retrieving results...
                  VAL                  
-------------------------------------- 
                                     1 
                                     6 
                                    15 
                                    20 
                                    15 
                                     6 
                                     1 

7 row(s) retrieved


Processing ...
select tab2string( cast (
			multiset (
				select fact(a.row_no)/(fact(level-1)*fact(a.row_no-level+1)) val
				from dual
				connect by level-1 <= a.row_no 
			)
			as string_table
		),' '
	) as pascal_triangle
from (
	select rownum-1 as row_no
	from dual
	connect by level-1 <= :n
) a

Query finished, retrieving results...
                                 PASCAL_TRIANGLE                                 
-------------------------------------------------------------------------------- 
1                                                                                
1 1                                                                              
1 2 1                                                                            
1 3 3 1                                                                          
1 4 6 4 1                                                                        
1 5 10 10 5 1                                                                    
1 6 15 20 15 6 1                                                                 

7 row(s) retrieved

Bye Alessandro

MichaelS

And of course a XML solution:
michaels>  COLUMN pascal format a30

michaels>  VAR pascal number

michaels>  EXEC :pascal := 7

michaels>  SELECT RTRIM(x.COLUMN_VALUE.EXTRACT('r/text()'),',') pascal
  FROM XMLTable('declare function local:fact($i)
                 {
                   if($i > 0) then 
                     number($i * local:fact($i - 1))
                   else (1)
                 };

                 for $n in 0 to .
                 return <r> {for $k in 0 to $n 
                              return concat(local:fact($n) div (local:fact($k) * local:fact($n - $k)),",")
                            }
                        </r>' PASSING XMLTYPE('<p>'||:pascal||'</p>')) x

PASCAL                        
------------------------------
1                             
1, 1                          
1, 2, 1                       
1, 3, 3, 1                    
1, 4, 6, 4, 1                 
1, 5, 10, 10, 5, 1            
1, 6, 15, 20, 15, 6, 1        
1, 7, 21, 35, 35, 21, 7, 1    


8 rows selected.
486393
exec :l_numrows := 5;

with data as 
(
  select ver,hor,decode(num,0,to_number(null),num) numn
  from   (select level hor from dual connect by level < :l_numrows+2)
  ,      (select level ver from dual connect by level < :l_numrows+1)
  model 
  dimension by (hor,ver)
  measures (cast (null as number(10)) num)
  rules
  (  
     num[1,any] = 1
  ,  num[2,1] = 1
  ,  num[hor>1,ver>1] = nvl(num[cv(hor)-1,cv(ver)-1],0) + nvl(num[cv(hor),cv(ver)-1],0)
  )
)
select ver,totalrow,sumrow
from
(
  select *
  from   data
  model  
  partition by (ver)
  dimension  by (hor)
  measures (numn
           ,cast(null as varchar2(25)) totalrow
           ,count(*) over (partition by ver) counter
           ,cast(0 as number(5)) sumrow)
  rules
  (
    totalrow[any] order by hor = totalrow[cv(hor)-1]  ||' '||numn[cv(hor)] 
  , sumrow[any] order by hor = nvl(sumrow[cv(hor)-1],0) + nvl(numn[cv(hor)],0)
  )
)
where hor=counter
order by ver,totalrow;     

       VER TOTALROW                      SUMROW
---------- ------------------------- ----------
         1  1 1                               2
         2  1 2 1                             4
         3  1 3 3 1                           8
         4  1 4 6 4 1                        16
         5  1 5 10 10 5 1                    32
1 - 29
Locked Post
New comments cannot be posted to this locked post.

Post Details

Locked on May 31 2008
Added on Nov 14 2005
29 comments
8,893 views