Enumerative algorithm through inclusion-exclusion - MathOverflow

Enumerative algorithm through inclusion-exclusion

2010-09-10T07:49:17Z

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

Answer by Douglas S. Stones for Enumerative algorithm through inclusion-exclusion

2010-09-10T09:33:00Z

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.

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.

Answer by sleepless in beantown for Enumerative algorithm through inclusion-exclusion

2010-09-10T14:09:44Z

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.

Answer by Mitch Harris for Enumerative algorithm through inclusion-exclusion

2010-09-10T14:21:02Z

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.

Answer by Ashley Montanaro for Enumerative algorithm through inclusion-exclusion

2010-09-12T09:55:22Z

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).