# Chapter 9Sorting

The typescript for chapter 9 is provided in AutomatedComposition09.pdf.

The idea of heuristic selection was first introduced by Chapter 6 in relation to what I then called “cumulative feedback”. In particular, heuristic selection referred to the approach taken at a decision point, where each available option would be assigned a numeric quantity reflecting how far the option lagged behind its fair share of usage. The options lagging farthest behind would be given first preference, but would be selected only if all constraints were satisfied. The process of selection would iterate through every option and evaluate both the option's statistical desirability and the option's constraint adherence.

Chapter 9 generalizes heuristic selection to allow for multiple criteria. It also introduces the implementation step of organizing options into a schedule and of using standard sorting algorithms to arrange this schedule by order of preference. This limits the need to check constraint adherence to the earliest schedule entries — once a workable option has been discovered, no further constraint-checking is necessary. Plus, having a schedule means your program can save the schedule and come back to it later, an essential precondition for the search techniques explored in Chapter 12 and Chapter 14.

The chapter explains the single-keyed insertion sort, an easy-to-implement algorithm suitable for populations of the small size encountered in composing programs. It discusses the complications introduced by multi-keyed sorts, then describes how to work around these complications through the agency of a packed key. An example of a packed key is a three-digit decimal number in which the hundreds digit holds a count of capital offences, the tens digit holds a count of other felonies, and the ones digit holds a count of misdemeanors. Notice in this example that packing by powers of ten limits counts to nine offences of any particular type; however in a packed key one must employ a base which accomodates the largest count existing among the population being evaluated.

The first of my own projects to employ packed keys was Protocol for solo piano (1981), but these packed keys provided an easily comparable number evaluating the quality of a search result, and the numbers were not sorted. The topic returns under the guise of “prioritized significances” in pp. 62-64 of “Quantifying Musical Merit”. Later on, the same article describes a prioritized assessment tactic employed by David Levitt, which I liken to a beauty contest:

The program steps through a sequence of tests arranged in priority from gross offenses to relatively minor infractions. … If a test eliminates all choices, the test is bypassed; if a test leaves only one choice the selection process terminates successfully. Otherwise the offending choices are eliminated and the next test applied.

An alternate tactic is to derive for each option a packed key and then to arrange the options in a schedule by sorting on the packed keys. While quite different procedurally from Levitt's tactic, the functional result is seen to be equivalent. Thus though I originally used the term beauty contest in reference to Levitt's approach, my current production framework introduces `BeautyContest` as one of three search-based implementation subclasses for the `Problem` class.

Section 9.2 of Chapter 9 lays out a now-discredited method by which randomness may be introduced into heuristic keys. The method calculates key values using a random multiplier. It was discredited in statistical applications (Chapter 7) because a near-zero multiplier could downgrade an option even when the option's usage fell very far short of all other usages. I found it more effective to introduce randomness as an incremental component, which method is described on p. 41 of my 1986 article, “Two Pieces for Amplified Guitar” (see Expression 3). Introducing randomness as an increment limited the influence of randomness to decisions teetering at the knife edge, e.g., when usage statistics were clustered together.

The practical programming content of Chapter 9 was provided by Demonstration 7: Sorting. This process illustrated the principle of top-down design in that contours describing the overall shape of the form as a whole were consulted to determine specific facts about content. The process had three stages of production:

• Stage I composed a progression of three-part chords. Pitch combinations within each chord were constrained by a matrix, and this matrix also indicated tendencies for each pitch. That is, a pitch could be stable, it could have a low-urgency upward tendency, or it could have a high-urgency downward tendency. The order by which parts were scheduled for pitch-selection for the current chord was determined by urgencies in the previous chord, and the order by which pitches were considered for selection in the current part was determined (1) by how well the pitch resolved tendencies from the same part in the previous chord and (2) by which pitches contributed best to maintaining diatonic balance.
• Stage II assigned durations to chords. This task was done segment by segment. A pool of durations was generated, where shorter durations were more numerous than longer durations. Each chord was evaluated as a packed key using 4 for a base. Let γi,j indicate the count of count of chromatic degrees shared in common between the chord in position i and the chord in position j. Then the packed key μk for the chord in position k was calculated as:
μk  =  16γk,k-1  + 4γk,k-2  + γk,k-3 .
Longer durations could thus be given to the chords sharing fewer chromatic degrees in common with their predecessors.
• Stage III arppeggiated the chords, using statistical feedback to ensure that the three chord tones all received their fair share of notes.

 © Charles Ames Page created: 2017-03-12 Last updated: 2017-03-12