views:

189

answers:

2

Short version: I am interested in some Clojure code which will allow me to specify the transformations of x (e.g. permutations, rotations) under which the value of a function f(x) is invariant, so that I can efficiently generate a sequence of x's that satisfy r = f(x). Is there some development in computer algebra for Clojure? For (a trivial) example

(defn #^{:domain #{3 4 7} 
         :range #{0,1,2}
         :invariance-group :full} 
          f [x]  (- x x))

I could call (preimage f #{0}) and it would efficiently return #{3 4 7}. Naturally, it would also be able to annotate the codomain correctly. Any suggestions?

Longer version: I have a specific problem that makes me interested in finding out about development of computer algebra for Clojure. Can anyone point me to such a project? My specific problem involves finding all the combinations of words that satisfy F(x) = r, where F is a ranking function and r a positive integer. In my particular case f can be computed as a sum

F(x) = f(x[0]) + f(x[1]) + ... f(x[N-1])

Furthermore I have a set of disjoint sets S = {s_i}, such that f(a)=f(b) for a,b in s, s in S. So a strategy to generate all x such that F(x) = r should rely on this factorization of F and the invariance of f under each s_i. In words, I compute all permutations of sites containing elements of S that sum to r and compose them with all combinations of the elements in each s_i. This is done quite sloppily in the following:

(use 'clojure.contrib.combinatorics)
(use 'clojure.contrib.seq-utils)


(defn expand-counter [c]
 (flatten (for [m c] (let [x (m 0) y (m 1)] (repeat y x)))))

(defn partition-by-rank-sum [A N f r]
  (let [M (group-by f A)
    image-A (set (keys M))
    ;integer-partition computes restricted integer partitions,
    ;returning a multiset as key value pairs
    rank-partitions (integer-partition r (disj image-A 0))
    ]
    (apply concat (for [part rank-partitions]
        (let [k (- N (reduce + (vals part)))
          rank-map (if (pos? k) (assoc part 0 k) part) 
          all-buckets (lex-permutations (expand-counter rank-map))
          ]
          (apply concat (for [bucket all-buckets]
        (let [val-bucket (map M bucket)
              filled-buckets (apply cartesian-product val-bucket)]
          (map vec filled-buckets)))))))))

This gets the job done but misses the underlying picture. For example, if the associative operation were a product instead of a sum I would have to rewrite portions.

+1  A: 

I am unaware of any computer algebra systems written in Clojure. However, for my rather simple mathematical needs I have found it often useful to use Maxima, which is written in lisp. It is possible to interact with Maxima using s-expressions or a higher-level representations, which can be really convenient. Maxima also has some rudimentary combinatorics functions which may be what you are looking for.

If you are hellbent on using Clojure, in the short term perhaps throwing your data back and forth between Maxima and Clojure would help you achieve your goals.

In the longer term, I would be interested in seeing what you come up with!

ivar
+1  A: 

There's Clojuratica, an interface between Clojure and Mathematica:

http://clojuratica.weebly.com/

See also this mailing list post by Clojuratica's author.

While not a CAS, Incanter also has several very nice features and might be a good reference/foundation to build your own ideas on.

Regarding "For example, if the associative operation were a product instead of a sum I would have to rewrite portions.": if you structure your code accordingly, couldn't you accomplish this by using higher-order functions and passing in the associative operation? Think map-reduce.

Michael Kohl