Repository | Series | Book | Chapter
Exact cover problem in Milton Babbitt's all-partition array
pp. 237-242
Abstract
One aspect of analyzing Milton Babbitt's (1916–2011) all-partition arrays requires finding a sequence of distinct, non-overlapping aggregate regions that completely and exactly covers an irregular matrix of pitch class integers. This is an example of the so-called exact cover problem. Given a set, A, and a collection of distinct subsets of this set, S, then a subset of S is an exact cover of A if it exhaustively and exclusively partitions A. We provide a backtracking algorithm for solving this problem in an all-partition array and compare the output of this algorithm with an analysis produced manually.
Publication details
Published in:
Collins Tom, Meredith David, Volk Anja (2015) Mathematics and computation in music: 5th international conference, MCM 2015, London, UK, June 22-25, 2015. Dordrecht, Springer.
Pages: 237-242
DOI: 10.1007/978-3-319-20603-5_25
Full citation:
Bemman Brian, Meredith David (2015) „Exact cover problem in Milton Babbitt's all-partition array“, In: T. Collins, D. Meredith & A. Volk (eds.), Mathematics and computation in music, Dordrecht, Springer, 237–242.