## Enumerative algorithm through inclusion-exclusion

Hello everybody !

I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. For instance, list all the derangements on $n$ elements (I'm not especially interested in enumerating the derangements and I guess there is bound to be a good specific way to enumerate them, but that's the first thing that came to my mind).

In particular, I would like to avoid having to remember all the elements which have already been enumerated (as this can grow very large)...

Thank you for your lights :-)

Nathann

-
I think I do not understand your question very well: It seems to me that inclusion-exclusion is in general a smart way for counting the number of elements in a set. Do you ask for a total order on all elements such that the successor (or predecessor) of an element can be computed efficiently? – Roland Bacher Sep 10 2010 at 8:07
Maybe he is asking for a positive formula or a categorification for inclusion exclusion. – Gjergji Zaimi Sep 10 2010 at 8:35
Inclusion/Exclusion is sometimes a very good way to find the cardinality of a set, but if you want to write a program returning all the elements of a set, the cardinality is not enough. So let us say one is able to compute the cardinality of a set through inclusion-exclusion : is it also possible to list its elements ? – Nathann Cohen Sep 10 2010 at 8:44
Nathan, if you wish to enumerate, it seems that a walk over the tree of the search space is the right way to do it. You can optimize the walk over the tree by pruning your search as soon as it becomes apparent that there can be no further chance of a solution along a branch. You should use a backtracking algorithm as I explain in an answer below. Walking the pruned tree with a depth-first algorithm also will let you avoid keeping track of everything which you have already tested. – sleepless in beantown Sep 10 2010 at 19:12
Do you wish to iterate over all of the search space in order to confirm that your counting by inclusion-exclusion is correct? Or do you want to generate a list of all possible answers in your solution space? Why exactly do you wish to write a program to list the elements? Perhaps a better explanation of the motivation or the underlying problem will help me understand your goal. What formula do you have for your inclusion-exclusion counting of the cardinality of this set? – sleepless in beantown Sep 10 2010 at 19:54
show 1 more comment

Both yes and no. Let me illustrate...

Inclusion-exclusion is typically used to find the cardinality of a set A contain all combinatorial objects that avoid a substructure S (either that, or the complement of A).

Suppose you are at object $x \in A$ and the next object is $y \in A$. Whatever method you use for finding y from x would need to find the combinatorial trade T formed from the difference between y and x. The trade T will typically depend on the structure of x and y, that is, you will probably not be able to use the same trade T in going from most x' to y' later in the iterator.

For example, consider (0,1) sequences of length n without two consecutive 1s. Here's the list for n=3.

000
001
010
100
101


These can be counted using inclusion-exclusion. Notice that, no matter which order we choose to iterate in, the trade T that arises in going from 000 to abc will somehow contain the information of which of a,b,c are non-zero -- i.e. which numbers to toggle. This trade can clearly not be used everywhere in the iterator, although in some cases it could: e.g. if 000 -> 001 then the trade could be reused in going from 100 -> 101.

In some areas of combinatorics, such as Latin squares, we start off with one member L of the set A, then store a sequence of trades $t_1,t_2,\ldots$ (this can require much hard-disk space). We iterate through the Latin squares quickly by applying the trades in sequence, that is, $L \mapsto t_i L$ iteratively.

The problem therefore becomes finding a sequence of trades that are quite "small" (and therefore require less storage) -- e.g. in the binary sequences case, toggles only one or two bits.

-

Consider the smallest nontrivial inclusion-exclusion situation:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

(removing one set of the double counting of $A\cap B$).

In the species interpretation,

$$A \cup B = A \oplus B - A \cap B$$

the $\oplus$ corresponds to disjoint union, but there is no accepted intepretation of $-$ (yes, it is the complement, but there is no systematic way to say which items are being removed.

But one can transform the above equation using grade school arithmetic to get a reasonable correspondence:

$$A \cup B \oplus A \cap B= A \oplus B$$

Form an isomorphism from one side to the other. Then generate and test, that is, assuming you want $A \cup B$, generate $A \oplus B$ sequentially (by unranking, Gray code, whatever), then check if in $A \cap B$ (use a ranking procedure and the isomorphism) and repeatedly try the next one if a member (this is the exclusion step).

Of course, this is not as clean as what one would want (a 'direct' construction of only those items wanted. Also, if the desired set is small or the overlapping is complicated, then lots will need to be excluded and so lots will need to be excluded before reaching the next one. However, you don't need to keep around a list of 'items so far' or ' items to avoid' as long as you have a mapping function (the isomorphism) between the two sides and needed ranking/unranking procedures.

-

Consider using a backtracking and depth-first tree search.

This will iterate over the entire space of solutions. First place or define some ordinality over the alphabet which will compose the components of the elements of the set to be enumerated. This will also allow you to define an ordinality of the sets composed of those elements described as an ordered list. Then the only thing which you have to keep track of as you iterate is the current element of the set which you are testing. Everything else to be tested will be further down further down or to the right on the tree. (or "left" depending on how you draw the tree...)

Example: using backtracking and a depth-tree to help simplify the 8-queen problem on the 8x8 chessboard. The alphabet in this case is the set {1,2,...64}, each element of the set of solutions to the 8-queen problem is a non-empty set consisting of elements of the alphabet.

Worst approach: iterate over all $2^{64}$ positions which could contain queens; this includes cases with less than or more than $8$ queens up to $64$.

Better: iterate over all $\binom{64}{8}$ ways to choose 8 elements out of the 64 squares.

Even better: keep track of a current list, and a still-possible list, and a to-be-skipped list. Add a possible candidate alphabet item to the current list. Based on the current list, figure out which alphabet elements are excluded and eliminate them from the still-possible list. Add the next possible candidate alphabet item to the current list. If you run out of candidates, backtrack, remove the last placed alphabet item, move it to the to-be-skipped list, and skip the last used choice and iterate for the next available alphabet item. I've left out some of the details of clearing out the skip-list, etc, but this should give you the gist of the approach.

This sort of program can be interrupted in the middle and continued from a particular point in the tree without having knowledge of the contents of the previosly explored parts of the tree. This is because calculating the successor to the current set which you are testing can be defined as a function of the current set.

-

There has been some research on algorithms for approximate inclusion-exclusion, in the following sense. If we know the size of all intersections between any $2 \le k \le n$ sets in some family of $n$ sets, we can compute the size of the union of all $n$ sets in the family exactly, by inclusion-exclusion. But what if we only want to approximate the size of the union?

Linial and Nisan have shown that a good approximation can be found if we just know the size of all $k$-wise intersections, for $k=O(\sqrt{n})$. Sherstov has recently extended this to computing more general functions than just the size of the union (where how big $k$ needs to be depends on the function to be computed).

-