Sokrates on Oracle

Archive for May 22nd, 2015

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

Advertisements

Posted in fun, sql | Tagged: , | 5 Comments »