The Art Gallery Guardian

Implement a special kind of recurrence relation as a infinite list


A common recurrence has the form an={i=0bianmiif n>kcnif nk a_n = \begin{cases} \sum_{i=0}^\infty b_ia_{n-m_i} &\text{if }n>k\\ c_n & \text{if }n\leq k \end{cases} , where mim_i and bib_i are both infinite sequences, and cic_i is a finite sequence. miNm_i\in \mathbb{N}. ai=0a_{-i}=0 for all positive ii. This is well defined as long as bi,ai,cib_i, a_i, c_i are in the same ring.

One can use a balanced binary tree to store the entire infinite list, and the time to generate the nnth element is O(d(n)logn)O(d(n)\log n), where dd is the density function of {mi}\set{m_i}.

Using an array would make it O(d(n))O(d(n)), but it is too imperative for our taste, how about we only use list and achieve O(d(n))O(d(n)) time, elegantly?

The idea is that we are summing the first item of infinite many stacks. However we don’t have to really sum the infinite stacks, we only sum the stack we require. The code:

What’s a practical usage of this? Produce a infinite list of partition numbers, such that finding the first nn elements can be done in O(n32)O(n^{\frac{3}{2}}) time and 3 lines of code. The code

Posted by Chao Xu on .
Tags: Haskell.