babbitt.clj

(ns babbitt.core
  (:require [clojure.math.combinatorics :as combo]))

; insert n at index i in x
; (insert 5 1 [2]) => [2 5]
(defn insert [n i x]
  (let [[before after] (split-at i x)]
    (vec (concat before [n] after))))

; insert ns at indices js in x
; (inserts [7 8 10] [0 2 3] [1 2 3 4 5]) => [7 1 2 8 3 10 4 5]
(defn inserts [[n & ns] [j & js] x]
  (if (empty? js)
    (insert n j x)
    (inserts ns (map inc js) (insert n j x))))

; generate all possible ordered insertions of ns into x
; (insertions [:A :B] [:F :E]) => ([:A :B :F :E], [:A :F :B :E], ...)
(defn insertions [ns x]
  (if (empty? x)
    [(into x ns)]
    (for [cs (filter #(apply <= %) (combo/selections (range (inc (count x))) (count ns)))]
      (inserts ns cs x))))

; generate all possible ordered insertions of ns into multiple xs
; (insertions* [:A :B] [[:F :E] [:E :G]]) => ([:A :B :F :E], [:A :B :E :G], ...)
(defn insertions* [ns xs]
  (mapcat identity (for [l xs] (insertions ns l))))

;(generate-partial [[:A :B] [:E :D :F#] [:G]]) => ([:A :B :E :D :F# :G], ...)
(defn generate-partial [[rule & xs]]
  (if (empty? xs)
    (insertions rule [])
    (insertions* rule (generate-partial xs))))