Implementation of efficient voice leading algorithm

README.md

THE GEOMETRY OF MUSICAL CHORDS

Dmitri Tymoczko, Princeton University

Figure S12 illustrates the technique, identifying the smallest voice leading between the C and E major-seventh chords, {4, 7, 11, 0} and {4, 8, 11, 3}, such that the voice leading contains the pair (4,4). In constructing this matrix I have used the L1 “taxicab” norm to measure voice-leading size. The voice leading in the bottom-right entry, (4, 4, 7, 11, 0)(3, 4, 8, 11, 11), is one of the minimal voice leadings between the two chords that contains (4, 4). To remove this last restriction, we would need to repeat the calculation three more times, each time cyclically permuting the order of one of the chords so as to fix a different initial pair. As it happens, however, the voice leading shown in Figure S12 is minimal. This follows from the fact that the mapping in the top- left position, (4, 4), contributes nothing to the overall size of the voice leading; we can therefore add it to any voice leading without increasing its L1 size.

Figure S12 includes in each entry both the numerical size of the voice leading and the voice leading itself. With the L1 norm this is unnecessary: we need to keep track of the size, but not the voice leading. To determine the value of entry ei, j we can simply add the distance between the pair (ai, bj) to the minimum value in the entries ei-1, j, ei, j-1, and ei-1, j-1. (For the other Lp norms we can calculate the pth power of the voice- leading size in this way, taking the pth root before output.) Having filled in the matrix, we can recover a minimal voice leading between the two chords by “tracing back” a path that moves from the bottom-right entry to the top left, moving only up, left, and diagonally up-and-left, such that the size of the voice leading decreases as much as possible with each step. The entries in boldface indicate the path such a traceback algorithm would take. Due to the circular structure of pitch-class space, the voice leading in the lower right-hand corner of the matrix counts the pair (a1, b1) = (am+1, bn+1) twice; this can easily be corrected prior to output. The resulting algorithm is easy to implement and suitable for time-critical applications such as interactive computer music.

voice_leading.rb

# squish things into a single octave for comparison
# between chords and sort from lowest to highest
def octave_transform(input_chord, root)
  input_chord.map {|x| root + (x%12) }.sort
end

# get the distances between the notes
def t_matrix(chord_a, chord_b)
  root = chord_a.first
  z = octave_transform(chord_a, root).zip(octave_transform(chord_b, root))
  z.map {|a,b| b - a }
end

def voice_lead(chord_a, chord_b)
  # get mapping of notes in chord a
  # to the sorted version of the chord a
  root = chord_a.first
  
  a_leadings = chord_a.map {|x|
    [x, octave_transform(chord_a, root).index(root + (x%12))]
  }
  t_matrix = t_matrix(chord_a, chord_b)
  b_voicing = a_leadings.map {|x,y|
    x + t_matrix[y]
  }
  b_voicing
end

use_synth :saw

loop do
  [
    chord(:e5, :minor),
    chord(:c5, :major),
    chord(:fs5, :minor),
    chord(:b5, :minor)
  ].each_cons(2) do |a,b|
    if @last_c.nil?
      play a
      sleep 1
    end
    
    @last_c ||= a
    
    @last_c = voice_lead(@last_c,b)
    play @last_c
    sleep 1
  end
  @last_c = nil
end

I've changed the three defs into define format which is probably nicer for Sonic Pi.

define :octave_transform do |chord|
  chord.map {|x| 60 + (x%12) }.sort
end

define :t_matrix do |chord_a, chord_b|
  z = octave_transform(chord_a).zip(octave_transform(chord_b))
  z.map {|a,b| b - a }
end

define :voice_lead do |chord_a, chord_b|
  a_leadings = chord_a.map {|x|
    [x, octave_transform(chord_a).index(60 + x%12)]
  }
  t_matrix = t_matrix(chord_a, chord_b)
  b_voicing = a_leadings.map {|x,y|
    x + t_matrix[y]
  }
  b_voicing
end

use_synth :saw

loop do
  [
    [60, 64, 67, 71-12],
    chord(:e, 'm7-5'),
    chord(:f, :major7),
    chord(:e, 'm7-5'),
    chord(:a, '7+5-9'),
    chord(:d, :minor7),
    chord(:d, :minor7),
    chord(:g, '7sus4'),
    chord(:g, '7')
  ].each_cons(2) do |a,b|
    if @last_c.nil?
      play a
      sleep 1
    end
    
    @last_c ||= a
    
    @last_c = voice_lead(@last_c,b)
    play @last_c
    sleep 1
  end
  @last_c = nil
end