Exact cover problem in Milton Babbitt's all-partition array

Brian Bemman

David Mérédith

pp. 237-242

in: Tom Collins, David Mérédith, Anja Volk (eds), Mathematics and computation in music, Berlin, Springer, 2015

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.