Sokrates on Oracle

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

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

```

5 Responses to “A Greedy Algorithm using Recursive subquery factoring ( or better – read the comments – using pattern matching)”

1. Oren Nakdimonsaid

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 Rogelsaid

Hi Oren,

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

Thanks Matthias

2. stewashtonsaid

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 Rogelsaid

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

```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 <= 200
),
candidates as
(
select n.n, f.f
from n, f
where n.n >= 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
```

was meant.

• stewashtonsaid

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