Computational Aspects of Ordered Integer Partitions with Bounds

Abstract

This paper is dedicated to the counting problem of writing an integer number $z$ as a sum of an ordered sequence of $n$ integers from $n$ given intervals, i.e., counting the number of configurations $(z_1,…,z_n)$ with $z=z_1+...+z_n$ for zi\in[x_i,y_i] with integers x_i and y_i and 1\leq i\leq n. We show an algorithm computing this number in $\bigo(n_z lg n)$ average time, and a data structure computing this number in $\bigo(n)$ time, independently of $z$. The data structure is constructed in \bigo(2^nn^3)$ time. Its construction algorithm only depends on the intervals $[x_i,y_i] (1\leq i\leq n)$. This construction algorithm can be parallelized with $p=\bigo(n^3)$ processors, yielding $\bigo(2^n\frac{n^3}{p})$ construction time with high probability.