LISPを使って総音程音列を生成してみました。いきなり何それ的なフレーズですが、総音程音列というのは、すべての音程を一回ずつ含み重複しない12個すべての音の列のことを言います。

例)
音列 : C D# D A F G C# A# B E G# F#
音程 : 3 11 7 8 2 6 9 1 5 4 10

参考) https://itunes.apple.com/jp/app/yin-le-dian-zhuo-mu-calc/id319666478?mt=8

またLISPというのは、List Processorの略で、カッコの構文が特徴的なリスト処理が得意の古いプログラム言語です。今回はLISP系の言語でよく使われているSchemeを使います。この言語は学習レベルでは使ったことがありますが、実用では現在の高級言語の方が向いているため、あまり使う機会がありませんでした。しかしある特定の処理に関しては、とても効率的に記述できるため、今もよく使われるています。最近のデータ処理の分野で、再び脚光を浴びているといえます。(私感ですが・・)

まず12個の音をすべてならべる順列のプログラムが必要になります。
そこから総音程の条件にあった音列のみをとりだすという手順ですすめます。

順列の生成には下記サイトを参考にしました。

参考) http://www.geocities.jp/m_hiroi/func/abcscm11.html

まずこのプログラムを見て、バックトラックの実装がこんなシンプルなコードで、できるのだろうか、という疑問がわきました。
これがLISPのすごいところです。念のためその挙動を確かめるプログラムを作ってみました。

環境 : DrRacket 6.1.1 / Windows 8.1

#lang racket
(require srfi/1)

(define (remove-item x ls)
    (remove (lambda (a) (equal? a x)) ls))

(define (perm ls a dp)
    (if (null? ls)
        (begin (display (reverse a)) (newline))
        (for-each
            (lambda (n)
                (display (format "i: ~a ~a /~a \n" ls n dp))
                (perm (remove-item n ls) (cons n a) (+ dp 1))
                (display (format "o: ~a ~a /~a \n" ls n dp)))
            ls)))

(perm '(1 2 3) '() 1)

実行結果

i: (1 2 3) 1 /1 ※
i: (2 3) 2 /2
i: (3) 3 /3
(1 2 3)
o: (3) 3 /3
o: (2 3) 2 /2
i: (2 3) 3 /2
i: (2) 2 /3
(1 3 2)
o: (2) 2 /3
o: (2 3) 3 /2
o: (1 2 3) 1 /1
i: (1 2 3) 2 /1 ※
i: (1 3) 1 /2
i: (3) 3 /3
(2 1 3)
o: (3) 3 /3
o: (1 3) 1 /2
i: (1 3) 3 /2
i: (1) 1 /3
(2 3 1)
o: (1) 1 /3
o: (1 3) 3 /2
o: (1 2 3) 2 /1
i: (1 2 3) 3 /1 ※
i: (1 2) 1 /2
i: (2) 2 /3
(3 1 2)
o: (2) 2 /3
o: (1 2) 1 /2
i: (1 2) 2 /2
i: (1) 1 /3
(3 2 1)
o: (1) 1 /3
o: (1 2) 2 /2
o: (1 2 3) 3 /1

一番右の数字は、再帰の深さで※の部分で次の入力データを読み込んでいます。

では、実際に音列を生成するプログラムを作成してみます。
できるだけシンプルにするため、リストの再利用を考えず、生成したらすぐに表示するようにしています。

#lang racket
(require srfi/1)

(define (ss ls ls1 ls2)
  (if (null? ls)
      ls2
      (ss (cdr ls)
          (cons (car ls) ls1)
          (cons (remainder (fold + 0 ls1) 12) ls2))))

(define (chk ls)
  (call/cc (lambda (ret)
  (for-each (lambda (n)
              (if (memv n ls) '() (ret #f))) 
            '(0 1 2 3 4 5 6 7 8 9 10 11)) #t )))

(define (tonerow ls a)
    (if (null? ls)
        (if (chk (ss a '() '())) 
        (begin (display a) (display (ss a '() '())) (newline)) '())
        (for-each
            (lambda (n)
                (tonerow (remove (lambda (a) (equal? a n)) ls) (cons n a)))
            ls)))

(tonerow '(1 2 3 4 5 6 7 8 9 10 11 12) '())

ss関数は、音列を足して音程のリストを作ります。chk関数で、すべての音程が含まれているかチェックします。
これを再帰を使わずにやると、12階層のループを使うことになりプログラムはこんなに簡単に書けません。最初にC言語でこのプログラムを作ったときは、ループでやったのですが、当時の最新コンパイラMS-C v5.1(Microsoft)では、ネストが深すぎでコンパイルが不可能でした。Turbo-C(Borland)では可能だった記憶があります。

ただこのプログラムは実行に約45分かかりました。(最近購入した標準的なノートPC)

実行結果 (3858行)

(9 5 8 10 11 6 3 7 4 2 1 12)(6 5 3 11 4 1 7 8 10 2 9 0)
(9 5 11 6 3 10 8 7 4 2 1 12)(6 5 3 11 4 8 10 7 1 2 9 0)
(10 3 8 11 6 5 9 7 4 2 1 12)(6 5 3 11 4 7 2 8 9 1 10 0)
・・・・
(2 9 4 1 6 7 3 5 8 10 11 12)(6 7 9 1 8 5 10 4 3 11 2 0)
(3 7 1 6 9 2 4 5 8 10 11 12)(6 7 9 1 8 4 2 5 11 10 3 0)
(3 7 4 2 1 6 9 5 8 10 11 12)(6 7 9 1 8 11 5 4 2 10 3 0)

そこで、ChickenSchremeを使って、C言語にトランスレートしてコンパイルしてみました。
(ちなみにcsiというREPL環境もあります)
上記コードの先頭を(require-extension srfi-1)に変更したものをtwelve.scmとします。

環境 : Ubuntu 14.04(DrRacketを動かしたPC上のVirtualBox)

apt-get install chicken-bin

chicken twelve.scm
cc -o twelve twelve.c -I/usr/include/chicken -lchicken
./twelve > twelve.txt

インストールもコンパイルも簡単にできました。
これでも実行時間は約30分くらいでした。(VMということであまり参考になる計測方法ではありません)
また機会があれば、他の処理系も使ってきちんと計測したいと思います。