The Problem
-----------
We would like to find a method of generating all partitions of a set
so that the partitions are known to be in some specific order and,
given one partition, it is easy to find the next partition without
having to generate all partitions. In fact, we would like to have
to generate only the next one in order to find the next one.
Description of the Solution
---------------------------
To talk about the order of partitions, we need to be able to
distinguish one partition from another in the first place. To do this,
label the members of the set with letters a b c d ... in order. Thus
the general problem is equivalent to the solving the problem when the
set is (a b ... ?), where the last letter is determined by the length
of the set. If the set is large, numbering the set rather than
lettering it can be done, and similar methods used as described
below, but the methods are easier to describe and understand using
letters.
Observe that a typical computer program which generates the set of all
partitions will always generate them in the same order, so the first
part of the problem, establishing a specific order, is trivial if you
have a partition generator. In principle, one could take a partition
generator and analyze it to determine what order it produces and then
figure out how one partition in that order relates to the next one, so
that the next one could be generated. To do this for the generators I
have written and read about appears to me to be difficult. A better
approach might be to ask if there is some "natural" order for
partitions and (if one can be found) try to build a new generator that
produces partitions in that order. This is what is done below.
In thinking about a natural order for the partitions of (a b c ...),
observe that, since the order of the elements of a set may be whatever
one chooses, the subsets of a partition may always each be put in
alphabetical order. Similarly, considering that each subset may be
considered to be a word, the partition itself may then be put in
alphabetical order.
Next we can put partitions in alphabetical order. However, in doing
this, it is necessary to decide how to deal with the spaces between
the words. For example, what is the correct order of the two
partitions ((a b) (c)) and ((a) (b c))? The obvious choices are to let
a space either come before A or after every letter. Here we use the
"after every letter" rule. To visualize this rule, we will replace all
the spaces with z and suppress some parentheses. Thus the partitions
from the example become (a b z c) and (a z b c), and it is easy to
determine the correct alphabetical order. Of course this will limit an
implementation which uses this representation to consideration of sets
of 25 or fewer elements, but the method generalizes readily. Observe
that we do not need a rule for handling two partitions of different
lengths which are identical as far as the shorter one goes, because
this cannot happen (all the letters are used up where the shorter one
ends).
Now all we need is a rule for generating the next partition from a given
partition. Actually, we need a few rules, as follows. We will use
the term "come after" to mean to come after in the alphabet.
1. If the partition is of the form (a z b z c z d z e), with a z
between each pair of successive non-z letters, there is no next
partition. This is the last one.
2. If the partition ends with two consecutive non-z letters, form
the new partition by sticking a z into the old one just before
the last letter.
3. Otherwise, start at the right of the partition, and work left until you
find a non-z letter which is not preceded by z. For example, in the
partition (a z b d z c z e), the letter is d. Call this the "key
letter". Call the part of the partition which follows the z after the
key letter the "tail". In the example, the tail is (c z e).
A. If there is a non-z letter in the tail which comes after the key
letter, call the (alphabetically) first such letter the "replacement
letter". Form the new partition as follows:
(i) Before the key letter, the new partition is the same as the
given partition.
(ii) The replacement letter is the next letter in the new partition.
Remove the replacement letter from the tail.
Put the key letter into the tail.
(iii) Remove the non-z letters from the tail that come after the replacement
letter and put them into the new partition in alphabetical order.
There might not be any such letters.
(iv) Put a z into the partition followed by the remaining non-z letters
from the tail in alphabetical order. Observe that there is at least
one letter, the key letter, to use in this step.
For example, using the partition above, (a z b d z c z e), where the
key letter is d, the replacement letter is e, and the new partition
is generated in the above four steps as follows:
(i) Partial new partition is (a z b) tail is (c z e)
(ii) Partial new partition is (a z b e) and the tail becomes (c z d)
(iii) No change
(iii) Complete new partition is (a z b e z c d)
B. Otherwise, form the new partition as follows:
(i) Before the key letter, the new partition is the same as the
given partition.
(ii) Replace the key letter with z and put the key letter into the tail.
(iii) Put all the non-z letters from the tail into the new partition
in alphabetical order.
For example, if the given partition is (a e z b d z c), the key letter
is d, and the new partition is generated in the above three steps as
follows:
(i) Partial new partition is (a e z b) tail is (c)
(ii) Partial new partition is (a e z b z) tail is (c d)
(iii) Complete new partition is (a e z b z c d)
An implementation of the solution in Lisp
-----------------------------------------
The following implementation works as described above. It assumes the
input partition has correct format.
(defun next_partition (partition)
(prog (noititrap end)
(setq noititrap (reverse partition))
(if (not (eq (second noititrap) 'z)) ; checks for case 2 above.
(return (reverse (cons (first noititrap)
(cons 'z (rest noititrap))))))
loop
(cond ((null (rest noititrap)) ; checks for case 1 above
(return nil))
((eq (second noititrap) 'z) ; did not find the key letter
(push (pop noititrap) end)
(pop noititrap)
(go loop))
(t ; found the key letter
(return (new_partition (reverse (rest noititrap))
(first noititrap)
(sort (cons (first noititrap)
end) #'string-lessp)))))))
(defun new_partition (beginning key_letter end_plus)
(let* ((last_bit (rest (member key_letter end_plus)))
(replacement (first last_bit)))
(cond (replacement ; checks 3A above
(append beginning
last_bit
(list 'z)
(ldiff end_plus last_bit)))
(t ; checks 3B above
(append beginning
(list 'z)
end_plus)))))
The following will generate and print (in order) all partitions which
follow a given partition.
(defun print_all_partitions (partition)
(do ((new partition (next_partition new)))
((null new))
(print new)))
This code is intended to implement the algorithm exactly as described,
not to be particularly efficient. There is probably a more efficient
way to implement essentially the same thing.
Thanks for the fun question.
Tom Kramer
······@cme.nist.gov