Computational Aspects of Ordered Integer Partitions with Bounds
- PDF / 4,311,226 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 64 Downloads / 147 Views
Computational Aspects of Ordered Integer Partitions with Bounds Roland Glück1 · Dominik Köppl2 Received: 11 June 2017 / Accepted: 6 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 (z1 , … , zn ) with z = z1 + ⋯ + zn for zi ∈ [xi , yi ] with inte‑ gers ( xi )and yi and 1 ≤ i ≤ n . We show an algorithm computing this number in in O(n) time, O nzlg n average time, and a data structure computing this ( number ) independently of z. The data structure is constructed in O 2n n3 time. Its construc‑ tion algorithm only depends on the intervals [xi , yi ] ( 1 ≤ i ≤ n ). This ( construction ) ( ) 3 algorithm can be parallelized with 𝜋 = O n3 processors, yielding O 2n n𝜋 con‑ struction time with high probability.
1 Introduction The class of balls and urns problems is classic in the field of enumerative combinat‑ orics: Let us consider n distinguishable urns with unbounded capacity that are enu‑ merated from one up to n, and z indistinguishable balls. A basic question, called stars and bars [8], asks to enumerate of how to distribute the balls to ( all possibilities ) z+n−1 is trivially computable, there is no the urns. Although its answer of z known polynomial time (with respect to n) algorithm when adding a seemingly sim‑ ple constraint like an upper bound to each urn’s capacity. Unfortunately, a lot of practical questions involve constraints on the urn’s size: Parts of this work have already been presented at the 12th International Symposium on Experimental Algorithms [10]. * Dominik Köppl [email protected]‑u.ac.jp Roland Glück [email protected] 1
German Aerospace Center, Am Technologiezentrum 4, 86159 Augsburg, Germany
2
Department of Computer Science, Kyushu University, Fukuoka, Japan
13
Vol.:(0123456789)
Algorithmica
– Creating groups of restricted size is a common problem of everyday’s life like assigning z employees to n working teams, or z students into n exercise classes. – In quantum mechanics, the electron configuration assigns z electrons to n atomic orbitals (see e.g., [15, Chapter X]). – A chained hash table of size n can use a linked list with a restricted maximum size for each bucket. – Given a finite set U and n total orders on U, the Pareto order [4] induced by the total orders is an irreflexive, transitive and strict order. The order can be visual‑ ized as a Hasse diagram. Common problems ask for (a) the number of nodes on a given depth z of the Hasse diagram, and (b) the number of depths that share the same maximal number of nodes (see Sect. 9). This article addresses the aforementioned problems by studying the following formal problem: Given n integer intervals [xi , yi ] with xi , yi ∈ ℤ and an integer z ∈ ℤ , return ∑ the cardinality of the set {(z1 , … , zn ) ∈ ℤn ∶ zi ∈ [xi , yi ] ∀i ∈ [1, n] ∧ ni=1 zi = z} . ∑ n Translating this problem by z�
Data Loading...
