## A Greedy Algorithm using Recursive subquery factoring ( or better – read the comments – using pattern matching)

Posted by Matthias Rogel on 22. May 2015

Today is friday and I like the twitter-hashtag #FibonacciFriday,

so I tweeted

```
```Zeckendorfs theorem every positive integer is uniquely the sum of distinct nonconsecutive Fibonaccis http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem#FibonacciFriday

— Matthias Rogel (@MatthiasRogel) 22. Mai 2015

Don’t be afraid of having a look at the wikipedia-site, the math is not complicated at all ( you don’t need more than adding natural numbers smaller than hundred ), nevertheless the theorem is nice from a mathematical point of view.

And there is also mentioned

*… For any given positive integer, a representation that satisfies the conditions of Zeckendorf’s theorem can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage. …*

After thinking a bit about it, I came to the idea to implement it solely in SQL which might show the strength of this language.

Here we go, we compute the Zeckendorf representations of the first 200 natural numbers in SQL.

If you are not familiar with the xmlquery-part of it, see what Tom Kyte learned from me

with n as ( /* the first 200 natural numbers */ select level as n from dual connect by level <= 200 ), f(n, a, b) as ( /* construct fibonaccis, 30 are surely enough ... */ select 1 as n, 1 as a, 1 as b from dual union all select n+1, b, a+b from f where n<=30 ) , fibonaccis as ( select f.a as f from f ), decomp(n, s) as ( /* here is the magic recursive subquery factoring */ select n.n, (select cast(max(fibonaccis.f) as varchar2(100)) from fibonaccis where fibonaccis.f <= n.n) from n union all select d.n, rtrim ( d.s || ' + ' || ( select cast(max(fibonaccis.f) as varchar2(10)) from fibonaccis where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal() ), ' + ' ) from decomp d where d.s != rtrim ( d.s || ' + ' || ( select cast(max(fibonaccis.f) as varchar2(10)) from fibonaccis where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal() ), ' + ' ) ) /* we only want "the last" decomp, the one with maximal length */ select decomp.n || ' = ' || min(decomp.s) keep(dense_rank first order by length(decomp.s) desc) as zeckendorf_representation from decomp group by decomp.n order by decomp.n / ZECKENDORF_REPRESENTATION ------------------------------------------------------------------------------------------------------------------------------------------------------------ 1 = 1 2 = 2 3 = 3 4 = 3 + 1 5 = 5 6 = 5 + 1 7 = 5 + 2 8 = 8 9 = 8 + 1 10 = 8 + 2 11 = 8 + 3 12 = 8 + 3 + 1 13 = 13 14 = 13 + 1 15 = 13 + 2 16 = 13 + 3 17 = 13 + 3 + 1 18 = 13 + 5 19 = 13 + 5 + 1 20 = 13 + 5 + 2 21 = 21 22 = 21 + 1 23 = 21 + 2 24 = 21 + 3 25 = 21 + 3 + 1 26 = 21 + 5 27 = 21 + 5 + 1 28 = 21 + 5 + 2 29 = 21 + 8 30 = 21 + 8 + 1 31 = 21 + 8 + 2 32 = 21 + 8 + 3 33 = 21 + 8 + 3 + 1 34 = 34 35 = 34 + 1 36 = 34 + 2 37 = 34 + 3 38 = 34 + 3 + 1 39 = 34 + 5 40 = 34 + 5 + 1 41 = 34 + 5 + 2 42 = 34 + 8 43 = 34 + 8 + 1 44 = 34 + 8 + 2 45 = 34 + 8 + 3 46 = 34 + 8 + 3 + 1 47 = 34 + 13 48 = 34 + 13 + 1 49 = 34 + 13 + 2 50 = 34 + 13 + 3 51 = 34 + 13 + 3 + 1 52 = 34 + 13 + 5 53 = 34 + 13 + 5 + 1 54 = 34 + 13 + 5 + 2 55 = 55 56 = 55 + 1 57 = 55 + 2 58 = 55 + 3 59 = 55 + 3 + 1 60 = 55 + 5 61 = 55 + 5 + 1 62 = 55 + 5 + 2 63 = 55 + 8 64 = 55 + 8 + 1 65 = 55 + 8 + 2 66 = 55 + 8 + 3 67 = 55 + 8 + 3 + 1 68 = 55 + 13 69 = 55 + 13 + 1 70 = 55 + 13 + 2 71 = 55 + 13 + 3 72 = 55 + 13 + 3 + 1 73 = 55 + 13 + 5 74 = 55 + 13 + 5 + 1 75 = 55 + 13 + 5 + 2 76 = 55 + 21 77 = 55 + 21 + 1 78 = 55 + 21 + 2 79 = 55 + 21 + 3 80 = 55 + 21 + 3 + 1 81 = 55 + 21 + 5 82 = 55 + 21 + 5 + 1 83 = 55 + 21 + 5 + 2 84 = 55 + 21 + 8 85 = 55 + 21 + 8 + 1 86 = 55 + 21 + 8 + 2 87 = 55 + 21 + 8 + 3 88 = 55 + 21 + 8 + 3 + 1 89 = 89 90 = 89 + 1 91 = 89 + 2 92 = 89 + 3 93 = 89 + 3 + 1 94 = 89 + 5 95 = 89 + 5 + 1 96 = 89 + 5 + 2 97 = 89 + 8 98 = 89 + 8 + 1 99 = 89 + 8 + 2 100 = 89 + 8 + 3 101 = 89 + 8 + 3 + 1 102 = 89 + 13 103 = 89 + 13 + 1 104 = 89 + 13 + 2 105 = 89 + 13 + 3 106 = 89 + 13 + 3 + 1 107 = 89 + 13 + 5 108 = 89 + 13 + 5 + 1 109 = 89 + 13 + 5 + 2 110 = 89 + 21 111 = 89 + 21 + 1 112 = 89 + 21 + 2 113 = 89 + 21 + 3 114 = 89 + 21 + 3 + 1 115 = 89 + 21 + 5 116 = 89 + 21 + 5 + 1 117 = 89 + 21 + 5 + 2 118 = 89 + 21 + 8 119 = 89 + 21 + 8 + 1 120 = 89 + 21 + 8 + 2 121 = 89 + 21 + 8 + 3 122 = 89 + 21 + 8 + 3 + 1 123 = 89 + 34 124 = 89 + 34 + 1 125 = 89 + 34 + 2 126 = 89 + 34 + 3 127 = 89 + 34 + 3 + 1 128 = 89 + 34 + 5 129 = 89 + 34 + 5 + 1 130 = 89 + 34 + 5 + 2 131 = 89 + 34 + 8 132 = 89 + 34 + 8 + 1 133 = 89 + 34 + 8 + 2 134 = 89 + 34 + 8 + 3 135 = 89 + 34 + 8 + 3 + 1 136 = 89 + 34 + 13 137 = 89 + 34 + 13 + 1 138 = 89 + 34 + 13 + 2 139 = 89 + 34 + 13 + 3 140 = 89 + 34 + 13 + 3 + 1 141 = 89 + 34 + 13 + 5 142 = 89 + 34 + 13 + 5 + 1 143 = 89 + 34 + 13 + 5 + 2 144 = 144 145 = 144 + 1 146 = 144 + 2 147 = 144 + 3 148 = 144 + 3 + 1 149 = 144 + 5 150 = 144 + 5 + 1 151 = 144 + 5 + 2 152 = 144 + 8 153 = 144 + 8 + 1 154 = 144 + 8 + 2 155 = 144 + 8 + 3 156 = 144 + 8 + 3 + 1 157 = 144 + 13 158 = 144 + 13 + 1 159 = 144 + 13 + 2 160 = 144 + 13 + 3 161 = 144 + 13 + 3 + 1 162 = 144 + 13 + 5 163 = 144 + 13 + 5 + 1 164 = 144 + 13 + 5 + 2 165 = 144 + 21 166 = 144 + 21 + 1 167 = 144 + 21 + 2 168 = 144 + 21 + 3 169 = 144 + 21 + 3 + 1 170 = 144 + 21 + 5 171 = 144 + 21 + 5 + 1 172 = 144 + 21 + 5 + 2 173 = 144 + 21 + 8 174 = 144 + 21 + 8 + 1 175 = 144 + 21 + 8 + 2 176 = 144 + 21 + 8 + 3 177 = 144 + 21 + 8 + 3 + 1 178 = 144 + 34 179 = 144 + 34 + 1 180 = 144 + 34 + 2 181 = 144 + 34 + 3 182 = 144 + 34 + 3 + 1 183 = 144 + 34 + 5 184 = 144 + 34 + 5 + 1 185 = 144 + 34 + 5 + 2 186 = 144 + 34 + 8 187 = 144 + 34 + 8 + 1 188 = 144 + 34 + 8 + 2 189 = 144 + 34 + 8 + 3 190 = 144 + 34 + 8 + 3 + 1 191 = 144 + 34 + 13 192 = 144 + 34 + 13 + 1 193 = 144 + 34 + 13 + 2 194 = 144 + 34 + 13 + 3 195 = 144 + 34 + 13 + 3 + 1 196 = 144 + 34 + 13 + 5 197 = 144 + 34 + 13 + 5 + 1 198 = 144 + 34 + 13 + 5 + 2 199 = 144 + 55 200 = 144 + 55 + 1 200 rows selected. Elapsed: 00:01:28.71

## Oren Nakdimon said

Hi Matthias.

This is really cool!

Encouraged by your post, I wrote another version of this query, using 12c Pattern Matching (with your “Fibonacci generator”).

The elapsed time (for the same population of the first 200 natural numbers) is now less than 0.1 second.

with

f(n, a, b) as

(

/* construct fibonaccis, 30 are surely enough … */

select 1 as n, 1 as a, 1 as b

from dual

union all

select n+1, b, a+b

from f

where n<=30

)

select n.n || ' = ' ||

(select listagg(f,' + ') within group (order by f desc)

from (select n.n,f.a as f from f)

match_recognize(

order by f desc

measures classifier() cls

all rows per match

pattern(A (A|B)*)

define A as sum(A.f) <= n)

where cls='A') zeckendorf_representation

from (select level as n from dual connect by level <= 200) n;

Thanks,

Oren.

## Matthias Rogel said

Hi Oren,

fantastic !

Didn’t know how cool pattern matching really can be !

Thanks Matthias

## stewashton said

Nice post and great reply! Here is a slight variation on the reply:

1. Generate just enough fibonacci numbers to get to 200, by stopping when f(n) + f(n-2) is greater than 200

2. Join n and f such that f is never greater than n.

(The combination of 1. and 2. reduces the number of input rows from 6000 to 1836.)

3. Instead of running a subquery for each n, run one query using “partition by n” and “group by n”.

4. Instead of “where cls = ‘A'”, use the “exclusion syntax {- -}” in the PATTERN clause.

5. Without the WHERE clause, no need for the MEASURES clause.

with n as (

select level as n

from dual

connect by level <= 200

)

,f(b,f) as (

select 1 as b, 1 as f

from dual

union all

select f, b+f

from f

where 2*b+f = f

)

select n, listagg(f,’+’) within group(order by f desc) z_r

from candidates

match_recognize(

partition by n order by f desc

all rows per match

pattern((A|{-B-})+)

define A as sum(A.f) <= n

)

group by n;

To me, Oren's use of (A|B)* to implement the greedy algorithm was the fundamental insight that allowed for use of MATCH_RECOGNIZE. Hats off to you both!

## Matthias Rogel said

Stew, thanks for commenting, I appreciate it very much from the guru of pattern matching !

Seems that your SQL has one or two typos in it, I assume

was meant.

## stewashton said

Wow, I don’t know what happened with the copy and paste there! The “candidates” subquery was NOT left as an exercise for the reader, at least not deliberately. Thanks for correcting. Also, I’ll have to remember that [ code ] can be used in comments on WordPress.

Best regards, Stew