The short answer is: it depends upon what you mean by making the notes in the melody "fit the new chord progression". You could put any chords with a melody; but it might sound very dissonant some or all of the time! And this would: no longer produce an effect similar to the original relationship between melody and harmony (if you have already composed chords to fit with your melody); no longer produce an effect which displays the usual characteristics of common-practice harmony.
Here's an example:
The top line represents the simplest possible harmonisation for this melody, and certainly what one would consider to be the harmonisation most obviously suggested by the melody. But the use of an Ab Major chord throughout sounds good: very different but good. It gives the typical "horror-movie" effect of the "wrong" harmonisation of a such a simple children's melody. It works for a couple of reasons: the simple melody and use of only one major chord are both easily recognisable elements, even though they produce dissonance; there is still some recognisable relationship between the melody and harmony, the note C for instance is now the major third of the underlying chord, and the other notes (besides the E) all have a Lydian relationship with the underlying chord.
You could have chords below this unchanged melody that would be both more or less dissonant:
- you could reharmonise this in a fairly traditional manner to use more chords from C Major (or maybe A Minor).
- you could reharmonise this with chords that fit with the melody in a less traditional manner, but which are not dissonant, for instance by using chords from keys or modes that contain these five pitches, or that are in fact modes of C Major. (For example: F Lydian, D Dorian, F Major...)
- you could have chords that are extremely dissonant against the melody, for instance a C#7 chord against this melody will produce a highly chromatic amalgam.
The longer answer is: if you want to have your melody retain a "traditional" relationship with the underlying chords (in other words retaining relationships characteristic of common-practice harmony) you will need to change elements of your melody as and when your chords stray from what would be considered a "comfortable" harmonisation.
In order to preserve the identity of your melodic material as far as possible, you should aim to:
- keep the contour of the melodic line as similar to the original as possible.
- keep the horizontal relationships between melodic intervals as similar to the original as possible.
- trying to map chord tones and non-chord-tones in the original melody to chord-tones and non-chord-tones at the same points in your new melody.
Of course, this is easier said than done: and would require a bit of experimentation. It is almost certainly easier to do this on a case-by-case basis, rather than by creating an algorithm, but I like the sound of your challenge, and you may be able to produce rules that create melodic changes you are generally more happy than not, with.
Having pointed out the difficulties with these melodic adjustments, here are some approaches that might work, to produce traditional harmonic/melodic relationships:
- if two or more consecutive chords can fit within one major or minor key or mode, adjust the accidentals of your melody to also fit within this key or mode.
- where consecutive chords won't fit into a single key or mode, aim to adjust your melodic notes to be in a key which the underlying chord could be in.
- while retaining the melodic contour as far as possible, by introducing slightly larger or smaller intervals you can aim to retain the chord-tones and non-chord-tones at the same places within your melody. (For instance, where there is a second in your original melody, you may choose to use a third instead, which may keep chord-tones and non-chord-tones in the same relative positions.)
- consider transposing the whole melody up or down before making any other adjustments (in other words, start the melody on a different pitch). With a bit of experimentation you may find that such a transposition already makes more of your melody "fit" with more of your chords, before you then have to make other adjustments.
Two really important things to bear in mind:
- it may be that your melody has quite a chromatic/dissonant character to start with: in this case you will need to assess whether you want your changed melody to retain a similarly chromatic/dissonant relationship with any chord changes, or whether you want to "smooth" out these dissonances to create more consonant relationships.
- This is probably the most significant aspect of what you are trying to do: if your changed chords don't seem to have an easily recognisable relationship horizontally, it is likely that any changes you make to your melody, in order to make it "fit" with your underlying harmony, will result in a melody that fails to retain important horizontal relationships. (Yes, I know this is really obvious!) Put most simply: if your chords jump from key to key, your melody is likely to be similarly disjointed as it jumps from key to key.
As I see it, there is one other big choice that you should probably make: when changes are made to your melody, do you then continue your melody wholly changed in relationship to the one changed note (e.g. if a note is flattened by a semitone, do you continue with every other note "transposed" down by a semitone), or do you continue as you would have done, with just the one note changed? Again, this is likely to be dependent upon which of these will allow the most notes to "comfortably" fit with the underlying chord or chords.
Although your chord changes could be arbitrarily complex, let's stick with the melody and new chord from the example above, even though this represents a very simple case. (The original melody is harmonised with a single major chord and the new chord progression consists of a single major chord, too. So a trivial solution is to transpose the whole melody down a major third, to start on Ab.) If we take the Ab Major chord as our tonic chord (we may as well - it is the only chord!) we can adjust the pitches to be in Ab Major:
This works well; in particular, because the first two bars still have chord-tones in the same relative positions. The Gs in the third and fourth bars sound less good: they are not especially dissonant, but would sound better if they were adjusted to chord-tones - this suits these longer notes, as the melody comes to rest on them. Although neither of the following solutions (bars 3-4) are as effective as the original melody, they do work better for having the Ab chord-tone for the minims (personally I prefer the fourth bar):
The example above would sound okay with Ds instead of Dbs, too. This could be interpreted as Ab Lydian, or as being on chord IV of Eb Major.
But let's try a more difficult example. The chords below were chosen at random (not that interesting to know how, but it was fair!):
Okay, pretty weird chords - but that's a random choice for you! This works fairly well as an example though, because as it stands the melody certainly doesn't seem to fit well with the underlying chords.
At first glance, Bbm and Eb are fairly closely related (they could both be in the related keys/modes of Ab Major, Bb Dorian, F Natural Minor...), so we may be able to transpose our melody to fit better over these chords. Here are a couple of ways to change the melody to fit over the first two chords. Both retain (mostly) the position of chord-tones and non-chord-tones. The first retains the repetition of pitches bar-to-bar, but changes the intervals (and implies Eb7); the second retains the exact intervals, but uses a sequence for the second bar (i.e. the notes are transposed up a tone):
Both of these solutions have their merits, but trying these out with the next chord, I think the second will work better:
Here we manage to keep the exact intervallic relationships in the third and fourth bars as are in the original melody (and the repetition). In fact, the third bar has exactly the same relationship between melody and harmony as the original. Also, the fourth bar has the same relationship between melody and harmony as the second bar of the altered melody (again implying a 7th chord).
But how good does it sound? Well, to my ears, it sounds pretty bad. It might be the best solution possible, but not necessarily what I would compose if given a free choice of underlying harmony. In other words, the chord progression sounds a bit weird, like it doesn't quite work, and so it is no surprise that the altered melody sounds like this too...
A few closing comments:
Here I've just given one simple example. But the possibilities are of course endless (quicker changes of chord; different chord types/extensions; more complex melodic lines). And this is the essential problem: here I've come up with just one "bespoke" solution for one melody and set of chords - this has involved a certain amount of reasoning about the melodic and harmonic materials involved. As these will inevitably be different in each case, I'm not sure whether an algorithmic solution will be possible. And if it is, it won't be easy to find!
Lastly, if you haven't already, you need to make sure you have a good understanding of common-practice harmony and how to approach harmonisation and reharmonisation of melodies (essentially what you are doing is very closely related, even though it may seem like the opposite). Also, reading up on fugal technique, particularly about how real and tonal answers are adjusted to fit different harmonies and key centres, may be of use.