音楽と数学：コード進行と整数の結合

はじめに

前回の記事の通り、私はランダム関数を用いてランダム且つリアルタイムに楽曲を生成し演奏するということを趣味でやっています。その中で以下のようなコード進行を用いていました。

単純なCキーのII-V-I-VI進行というもので、各コードは4拍が割り当てられています。対して普段聴く音楽の楽譜を見てみると以下のように、割り当てられている拍数は様々で、小節の途中でコード進行があったりします。

私のシステムではこの固定数の小節中のコード進行タイミングのパターンもランダムに生成したいため数学的に分析し、全列挙し任意にパターン指定できるようにしました。
もちろんgreedyな方法でも目的は達成できますが、より一般化して使いやすくしたいという意図もあります。

数学的構造の分析

コード進行タイミングは一拍単位で行われると仮定すると、上記の例では4小節の全16拍をDm,G,C,Amのコード間で拍を取り合っていると捉えられます。またDm,G,C,Amは順番が前後することは無く、最低でも1拍はどのコードも割当があります。これは音楽的な要請からです。これを単純化すると、整数の結合(順序つき分割)の問題と捉えることが出来ます。整数の結合とは、ある整数を再現するための足し算のパターンを考えるというものです。例えば答えが16となる足し算のパターンは以下があります。+が一般的な足し算の意味合いと異なり、順序を考慮したものとなるため+>としています。

16 = 1 +> 15
16 = 15 +> 1　　上と使っている数は一緒だが順序が異なるため別パターンと見做す
16 = 4 +> 8 +> 3
16 = 1 +> 1 +> ... +> 1 (16個分)

今回の課題のII-V-I-VIの進行は4個のコードで構成されるため、項数が4に固定されます。なので16拍を4個のコードで進行するパターンは以下のようなものと表せます。

16 = 4 +> 4 +> 4 +> 4  一番目の例に対応する
16 = 2 +> 5 +> 5 +> 4　二番目の例に対応する
16 = 4 +> 2 +> 4 +> 6

たとえば最後の4 +> 2 +> 4 +> 6はDmが4拍、Gが2拍、Cが4拍、Amが6拍のパターンを表しています。
これで問題に、"要素数を固定した整数の結合"という数学モデルが適用出来たこととなります。

このモデルには入れ子構造を見ることが出来ます。
4 +> 2 +> 4 +> 6は16拍の結合パターン中にありますが、同時に1要素目を4拍に固定した場合の残り12拍(16拍-4拍)の結合パターンの１つとも見れます。これを繰り返し最終的には4 +> 2 +> 4を固定した場合の残り6拍の残り1要素の結合パターンを求めることとなり、これは1つのパターンである6のみです。
先頭4を固定しましたが、これを1~13拍(13は残り3コードに最小の1拍ずつを割り当てられる最大値)の範囲でループさせ、残りの要素の先頭もループが、、、と見れば列挙できそうですね。正直これで上手く説明できている気がしません、、、以下も合わせて読んでください。n=5,p=3の列挙パターンを見れば分かるかも知れません。

パターン総数

上記分析から、n拍をp個のコード進行に割り当てる場合のパターン総数$B(n,p)B(n,p)$が以下のようになると言えます。

$$B(n,p)={1if p=1∑i=1n−p+1B(n−i,p−1)otherwise B(n,p) = \begin{cases} 1 & \text{if p=1}\\ \sum_{i=1}^{n-p+1}B(n-i,p-1) & \text{otherwise} \end{cases}$$

試しに、3拍を2コードで割り当てる例を考えましょう。このパターンは以下のみです。

3=1+>2
3=2+>1

つまり以下の様に見ることが出来ます。

一番目のコードに1拍割り当て。残りの2拍は残りコードが1つなのでそれに全部の2拍を割り当て。
一番目のコードに2拍割り当て。残りの1拍は残りコードが1つなのでそれに全部の1拍を割り当て。

数式に適用すると、以下のように総数と合致します。

$$B(n=3,p=2)=∑i=12B(3−i,1)=B(3−1,1)+B(3−2,1)=B(2,1)+B(1,1)=1+1=2 \begin{align} B(n=3,p=2) &= \sum_{i=1}^{2}B(3-i,1)\\ &= B(3-1,1) + B(3-2,1) = B(2,1) + B(1,1) \\ &= 1 + 1 = 2 \end{align}$$

n=5,p=3ではどうでしょうか？以下が全6パターンとなります。

1 +> 1 +> 3
1 +> 2 +> 2
1 +> 3 +> 1
2 +> 1 +> 2
2 +> 2 +> 1
3 +> 1 +> 1

以下の様に整合します。$B(3,2)B(3,2)$は上で計算済みですね。

$$B(n=5,p=3)=∑i=13B(5−i,2)=B(4,2)+B(3,2)+B(2,2)=(B(3,1)+B(2,1)+B(1,1))+2+(B(1,1))=(1+1+1)+2+(1)=6 \begin{align} B(n=5,p=3) &= \sum_{i=1}^{3}B(5-i,2)\\ &= B(4,2) + B(3,2) + B(2,2)\\ &= (B(3,1) + B(2,1) + B(1,1)) + 2 + (B(1,1)) \\ &= (1+1+1) + 2 + (1) = 6 \end{align}$$

実装例は以下となります。HaskellとPythonの両方を示します。また実践的に冒頭の例であるn=16,p=4の結果も示します。

f n p | p == 1 = 1
      | otherwise = sum [f (n-i) (p-1) | i <- [1..(n-p+1)]]

main = do
  print $ f 5 3  -- Output: 6
  print $ f 16 4  -- Output: 455

def f(n, p):
    if p == 1:
        return 1
    return sum(f(n - i, p - 1) for i in range(1, n - p + 2))

print(f(5, 3))    # Output: 6
print(f(16, 4))   # Output: 455

パターン全列挙

総数と同様のイメージのもと、再帰的に以下のように列挙アルゴリズムが組めます。

n,pを引数として受ける。
0. p=1の場合はnをリストのリスト([[n]])として返す。
1. その他の場合は、1~(n-p+1)の整数ループ。xでイテレーションする。
 1-1. n'=(n-x) p'=(p-1)として再帰呼出し。xs(リストのリスト)とする。
 1-2. xをxsの要素数分コピーし、xとxsの各要素を結合。結果とする。
2.1のループの各結果を結合し返す。

実装例は以下となります。HaskellとPythonの両方を示します。
Haskellではリストのモナドとしての用法を活用しています。

f :: Int -> Int -> [[Int]]
f n 1 = [[n]]
f n p = do
  x <- [1..(n - p + 1)]
  xs <- f (n-x) (p-1)
  return $ x : xs

main = do
  mapM_ print $ f 16 4

def f(n, p):
    if p == 1:
        return [[n]]
    result = []
    for x in range(1, n - p + 2):
        for xs in f(n - x, p - 1):
            result.append([x] + xs)
    return result

print(f(16,4))

以下は演算結果です。

演算結果

[1,1,1,13]
[1,1,2,12]
[1,1,3,11]
[1,1,4,10]
[1,1,5,9]
[1,1,6,8]
[1,1,7,7]
[1,1,8,6]
[1,1,9,5]
[1,1,10,4]
[1,1,11,3]
[1,1,12,2]
[1,1,13,1]
[1,2,1,12]
[1,2,2,11]
[1,2,3,10]
[1,2,4,9]
[1,2,5,8]
[1,2,6,7]
[1,2,7,6]
[1,2,8,5]
[1,2,9,4]
[1,2,10,3]
[1,2,11,2]
[1,2,12,1]
[1,3,1,11]
[1,3,2,10]
[1,3,3,9]
[1,3,4,8]
[1,3,5,7]
[1,3,6,6]
[1,3,7,5]
[1,3,8,4]
[1,3,9,3]
[1,3,10,2]
[1,3,11,1]
[1,4,1,10]
[1,4,2,9]
[1,4,3,8]
[1,4,4,7]
[1,4,5,6]
[1,4,6,5]
[1,4,7,4]
[1,4,8,3]
[1,4,9,2]
[1,4,10,1]
[1,5,1,9]
[1,5,2,8]
[1,5,3,7]
[1,5,4,6]
[1,5,5,5]
[1,5,6,4]
[1,5,7,3]
[1,5,8,2]
[1,5,9,1]
[1,6,1,8]
[1,6,2,7]
[1,6,3,6]
[1,6,4,5]
[1,6,5,4]
[1,6,6,3]
[1,6,7,2]
[1,6,8,1]
[1,7,1,7]
[1,7,2,6]
[1,7,3,5]
[1,7,4,4]
[1,7,5,3]
[1,7,6,2]
[1,7,7,1]
[1,8,1,6]
[1,8,2,5]
[1,8,3,4]
[1,8,4,3]
[1,8,5,2]
[1,8,6,1]
[1,9,1,5]
[1,9,2,4]
[1,9,3,3]
[1,9,4,2]
[1,9,5,1]
[1,10,1,4]
[1,10,2,3]
[1,10,3,2]
[1,10,4,1]
[1,11,1,3]
[1,11,2,2]
[1,11,3,1]
[1,12,1,2]
[1,12,2,1]
[1,13,1,1]
[2,1,1,12]
[2,1,2,11]
[2,1,3,10]
[2,1,4,9]
[2,1,5,8]
[2,1,6,7]
[2,1,7,6]
[2,1,8,5]
[2,1,9,4]
[2,1,10,3]
[2,1,11,2]
[2,1,12,1]
[2,2,1,11]
[2,2,2,10]
[2,2,3,9]
[2,2,4,8]
[2,2,5,7]
[2,2,6,6]
[2,2,7,5]
[2,2,8,4]
[2,2,9,3]
[2,2,10,2]
[2,2,11,1]
[2,3,1,10]
[2,3,2,9]
[2,3,3,8]
[2,3,4,7]
[2,3,5,6]
[2,3,6,5]
[2,3,7,4]
[2,3,8,3]
[2,3,9,2]
[2,3,10,1]
[2,4,1,9]
[2,4,2,8]
[2,4,3,7]
[2,4,4,6]
[2,4,5,5]
[2,4,6,4]
[2,4,7,3]
[2,4,8,2]
[2,4,9,1]
[2,5,1,8]
[2,5,2,7]
[2,5,3,6]
[2,5,4,5]
[2,5,5,4]
[2,5,6,3]
[2,5,7,2]
[2,5,8,1]
[2,6,1,7]
[2,6,2,6]
[2,6,3,5]
[2,6,4,4]
[2,6,5,3]
[2,6,6,2]
[2,6,7,1]
[2,7,1,6]
[2,7,2,5]
[2,7,3,4]
[2,7,4,3]
[2,7,5,2]
[2,7,6,1]
[2,8,1,5]
[2,8,2,4]
[2,8,3,3]
[2,8,4,2]
[2,8,5,1]
[2,9,1,4]
[2,9,2,3]
[2,9,3,2]
[2,9,4,1]
[2,10,1,3]
[2,10,2,2]
[2,10,3,1]
[2,11,1,2]
[2,11,2,1]
[2,12,1,1]
[3,1,1,11]
[3,1,2,10]
[3,1,3,9]
[3,1,4,8]
[3,1,5,7]
[3,1,6,6]
[3,1,7,5]
[3,1,8,4]
[3,1,9,3]
[3,1,10,2]
[3,1,11,1]
[3,2,1,10]
[3,2,2,9]
[3,2,3,8]
[3,2,4,7]
[3,2,5,6]
[3,2,6,5]
[3,2,7,4]
[3,2,8,3]
[3,2,9,2]
[3,2,10,1]
[3,3,1,9]
[3,3,2,8]
[3,3,3,7]
[3,3,4,6]
[3,3,5,5]
[3,3,6,4]
[3,3,7,3]
[3,3,8,2]
[3,3,9,1]
[3,4,1,8]
[3,4,2,7]
[3,4,3,6]
[3,4,4,5]
[3,4,5,4]
[3,4,6,3]
[3,4,7,2]
[3,4,8,1]
[3,5,1,7]
[3,5,2,6]
[3,5,3,5]
[3,5,4,4]
[3,5,5,3]
[3,5,6,2]
[3,5,7,1]
[3,6,1,6]
[3,6,2,5]
[3,6,3,4]
[3,6,4,3]
[3,6,5,2]
[3,6,6,1]
[3,7,1,5]
[3,7,2,4]
[3,7,3,3]
[3,7,4,2]
[3,7,5,1]
[3,8,1,4]
[3,8,2,3]
[3,8,3,2]
[3,8,4,1]
[3,9,1,3]
[3,9,2,2]
[3,9,3,1]
[3,10,1,2]
[3,10,2,1]
[3,11,1,1]
[4,1,1,10]
[4,1,2,9]
[4,1,3,8]
[4,1,4,7]
[4,1,5,6]
[4,1,6,5]
[4,1,7,4]
[4,1,8,3]
[4,1,9,2]
[4,1,10,1]
[4,2,1,9]
[4,2,2,8]
[4,2,3,7]
[4,2,4,6]
[4,2,5,5]
[4,2,6,4]
[4,2,7,3]
[4,2,8,2]
[4,2,9,1]
[4,3,1,8]
[4,3,2,7]
[4,3,3,6]
[4,3,4,5]
[4,3,5,4]
[4,3,6,3]
[4,3,7,2]
[4,3,8,1]
[4,4,1,7]
[4,4,2,6]
[4,4,3,5]
[4,4,4,4]
[4,4,5,3]
[4,4,6,2]
[4,4,7,1]
[4,5,1,6]
[4,5,2,5]
[4,5,3,4]
[4,5,4,3]
[4,5,5,2]
[4,5,6,1]
[4,6,1,5]
[4,6,2,4]
[4,6,3,3]
[4,6,4,2]
[4,6,5,1]
[4,7,1,4]
[4,7,2,3]
[4,7,3,2]
[4,7,4,1]
[4,8,1,3]
[4,8,2,2]
[4,8,3,1]
[4,9,1,2]
[4,9,2,1]
[4,10,1,1]
[5,1,1,9]
[5,1,2,8]
[5,1,3,7]
[5,1,4,6]
[5,1,5,5]
[5,1,6,4]
[5,1,7,3]
[5,1,8,2]
[5,1,9,1]
[5,2,1,8]
[5,2,2,7]
[5,2,3,6]
[5,2,4,5]
[5,2,5,4]
[5,2,6,3]
[5,2,7,2]
[5,2,8,1]
[5,3,1,7]
[5,3,2,6]
[5,3,3,5]
[5,3,4,4]
[5,3,5,3]
[5,3,6,2]
[5,3,7,1]
[5,4,1,6]
[5,4,2,5]
[5,4,3,4]
[5,4,4,3]
[5,4,5,2]
[5,4,6,1]
[5,5,1,5]
[5,5,2,4]
[5,5,3,3]
[5,5,4,2]
[5,5,5,1]
[5,6,1,4]
[5,6,2,3]
[5,6,3,2]
[5,6,4,1]
[5,7,1,3]
[5,7,2,2]
[5,7,3,1]
[5,8,1,2]
[5,8,2,1]
[5,9,1,1]
[6,1,1,8]
[6,1,2,7]
[6,1,3,6]
[6,1,4,5]
[6,1,5,4]
[6,1,6,3]
[6,1,7,2]
[6,1,8,1]
[6,2,1,7]
[6,2,2,6]
[6,2,3,5]
[6,2,4,4]
[6,2,5,3]
[6,2,6,2]
[6,2,7,1]
[6,3,1,6]
[6,3,2,5]
[6,3,3,4]
[6,3,4,3]
[6,3,5,2]
[6,3,6,1]
[6,4,1,5]
[6,4,2,4]
[6,4,3,3]
[6,4,4,2]
[6,4,5,1]
[6,5,1,4]
[6,5,2,3]
[6,5,3,2]
[6,5,4,1]
[6,6,1,3]
[6,6,2,2]
[6,6,3,1]
[6,7,1,2]
[6,7,2,1]
[6,8,1,1]
[7,1,1,7]
[7,1,2,6]
[7,1,3,5]
[7,1,4,4]
[7,1,5,3]
[7,1,6,2]
[7,1,7,1]
[7,2,1,6]
[7,2,2,5]
[7,2,3,4]
[7,2,4,3]
[7,2,5,2]
[7,2,6,1]
[7,3,1,5]
[7,3,2,4]
[7,3,3,3]
[7,3,4,2]
[7,3,5,1]
[7,4,1,4]
[7,4,2,3]
[7,4,3,2]
[7,4,4,1]
[7,5,1,3]
[7,5,2,2]
[7,5,3,1]
[7,6,1,2]
[7,6,2,1]
[7,7,1,1]
[8,1,1,6]
[8,1,2,5]
[8,1,3,4]
[8,1,4,3]
[8,1,5,2]
[8,1,6,1]
[8,2,1,5]
[8,2,2,4]
[8,2,3,3]
[8,2,4,2]
[8,2,5,1]
[8,3,1,4]
[8,3,2,3]
[8,3,3,2]
[8,3,4,1]
[8,4,1,3]
[8,4,2,2]
[8,4,3,1]
[8,5,1,2]
[8,5,2,1]
[8,6,1,1]
[9,1,1,5]
[9,1,2,4]
[9,1,3,3]
[9,1,4,2]
[9,1,5,1]
[9,2,1,4]
[9,2,2,3]
[9,2,3,2]
[9,2,4,1]
[9,3,1,3]
[9,3,2,2]
[9,3,3,1]
[9,4,1,2]
[9,4,2,1]
[9,5,1,1]
[10,1,1,4]
[10,1,2,3]
[10,1,3,2]
[10,1,4,1]
[10,2,1,3]
[10,2,2,2]
[10,2,3,1]
[10,3,1,2]
[10,3,2,1]
[10,4,1,1]
[11,1,1,3]
[11,1,2,2]
[11,1,3,1]
[11,2,1,2]
[11,2,2,1]
[11,3,1,1]
[12,1,1,2]
[12,1,2,1]
[12,2,1,1]
[13,1,1,1]

おわりに

どうせ専門の教科書には既に書かれているような内容なんでしょうが、自力で立式から実装まで行い綺麗に結果が出て満足しています。全列挙のHaskellの関数記述は宇宙との調和を感じるレベルで美しい、、、気に入っているのでもう一度書いておきます。

f :: Int -> Int -> [[Int]]
f n 1 = [[n]]
f n p = do
  x <- [1..(n - p + 1)]
  xs <- f (n-x) (p-1)
  return $ x : xs

リストモナドと再帰がマリアージュしていますね。快感です。