• Mood:

To get a more-than-theoretical handle on Lisp, I have started playing with enumerating the partitions of a set. I found a nice algorithm summary online. Coming from a Python mindset, my natural inclination was to make a set partition iterator.

Beginning there, I created a Lisp class for a set partition iterator. The class maintains three pieces of state information: a copy of the original set we are to partition, a vector called κ that keeps a running counter of where we are in the iteration, and a vector M where the i-th element is the maximum of all the first i elements of κ.

With the class, you can do something like this to enumerate the 15 different partitions of the set `{ a, b, c, d }`.:

```(let ((my-set '(:a :b :c :d)))
(let ((iter (make-instance 'set-partition-iterator :list my-set)))
(do ((pp (get-partition iter) (next-partition iter)))
((not pp))
(format t "~a~%" pp)))
```

This first cut was very poor Lisp. I directly followed the pseudo code in the article. As such, there is a great deal of indexing into vectors and walking backwards through lists and such.

For my second approach, I just used a list for my data structure. I kept the copy of the original set as the first element of the list. The rest of the list was just the κ state. And, I calculated the M information every time I needed it.

My goal in this phase was to make it much more Lisp-y. For starters, I reversed the order of the κ information so that I could walk through the list forward instead of backward and so that I could use Lisp built-ins to calculate the M list:

```(let ((MM (maplist #'(lambda (lst) (reduce #'max lst)) kappa)))
...)
```

Note: this is elegant to look at, but it is O(n2) for an operation that only needs to be O(n).

I had intended to make the iterator using closures so that you never got to handle the list containing the state. But, I wasn't too keen on that because one of the things that I wanted to do in moving to the list instead of the class was make it easy for you to fork the iterator. I went so far as to make it entirely functional.

In the class version, the `next-partition` method returned a partition. In this functional version, the `next-partition` returns a new iterator that begins at the partition after where the given iterator is. So, now you need to call `get-partition` explicitly, but looping makes more sense.

```(let ((my-set '(:a :b :c :d)))
(do ((ii (make-set-partition-iterator my-set) (next-partition ii)))
((not ii))
(format t "~a~%" (get-partition ii))))
```

Because it's functional, you could nest another `do` in there to run through all of the partitions you have left at any given point:

```(let ((my-set '(:a :b :c :d)))
(do ((ii (make-set-partition-iterator my-set) (next-partition ii)))
((not ii))
(do ((jj ii (next-partition jj)))
((not jj))
(some-operation (get-partition jj)))))
```

I could rewrite the class version to keep κ in a better order. It would be annoying to make the class version functional yet it seems very anti-Lisp to give it a copy constructor to allow the forking.

The number of partitions in a set grows very rapidly. There are 2 partitions of a two-element set, 5 partitions of a three-element set, 15 partitions of a 4-element set, 51 partitions of a 5-element set, and 72697 partitions of a 10-element set. I'm most always going to be using sets with more than 20 elements.

I really, really believe that functional stuff is easier to understand, to debug, and to re-use. But, it feels wrong to rebuild two 20+ element lists a few hundred thousand times even if the body of the loop is going to be doing much more work than my little iterator. So, I'm caught in the middle ground. I have a non-trivial amount of state which I need to copy a bazillion times, or I have a non-trivial amount of state that morphs behind my back.

Maxims, analogies, and/or dogma welcomed.

Tags:
• Post a new comment

#### Error

default userpic