Finding all possible set packings

Question

Say I have a matrix S of size (m,n), where m is the number of sets, and n the number of all possible elements sets can have. In this matrix, if the entry S(i,j) is 1, the set i has element j, and otherwise the element S(i,j) is 0.

My question is: are there any known relatively efficient algorithms to enumerate all possible set packings (i.e. combinations of sets such that no two sets intersect)?

Using this representation, a packing k is defined as a vector p_k = [p_{k,1}, p_{k,1}, ... p_{k,km}] where the elements p_{k,r} are row indices in S (i.e. sets) such that the intersection of of the sets in p_k is 0. Or in other words, the inner product of any two row vectors p_{k,r} * p_{k,s}' indexed by p_k in S is 0.

I'm looking for an implementation in MATLAB (or something callable from MATLAB), but if anybody knows of a fast implementation in some other library, that would also be helpful.

Answer 1

There cannot be any polynomial-order algorithm to enumerate all possible packings for your problem, because there are exponentially many such packings. For example, with m,n=3,4, there are 2^(n-1) packing configurations that include all n elements: {abcd}, {a}{bcd}, {ab}{cd}, {abc}{d}, {a}{b}{cd}, {a}{bc}{d}, {ab}{c}{d}, {a}{b}{c}{d}. (Presumably sets are not distinguished; e.g. {abc}{d} equivalent to {d}{abc}. If sets are distinguished, in following method just count up without excluding any counts, i.e. apply no rules.)

The rest of this answer may provide some ideas or a framework for solving the problem, but (as is) might not be particularly efficient.

One way to enumerate all valid cases is to count a base m+1 number H from H=0 up to a fraction of (m+1)^n, applying some rules to select valid configurations. Let d.j denote the j'th digit of H, with d.1 least significant. If d.j is 0, element j is a member of no set; if d.j = k > 0, j is a member of set k. Let A.i(H) = highest location of digit i in H or -i if i doesn't occur; require A.i > A.(i+1). A(H) can be maintained and tested incrementally in O(1) time as H counts up. For example, to exclude 1323 (== 1232) in following (handmade) example, note that A.2(1323) = 2 < 3 = A.3(1323).

Example: n = 4 = #elements; m = 3 = #sets; H-sequence with indistinguishable sets should be: 0000, 0001, 0010, 0011, 0012, 0100, 0101, 0102, 0110, 0111, 0112, 0120, 0121, 0122, 0123, 1000, 1001, 1010, 1011, 1012, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1121, 1122, 1123, 1200, 1201, 1202, 1203, 1210, 1211, 1212, 1213, 1220, 1221, 1222, 1223, 1230, 1231, 1232, 1233.

Answer 2

Not quite efficient I fear, but surely more than brute force.

I understand that packings have cardinality ranging from 1 to (at most) m.

To find all possible solutions, start from cardinality 1 and iterate until:

• you reach m

• or there are no more candidates for the next iteration (more on this below).

The candidate matrix has the same form as S. At iteration n it contains the elements of the valid packing found at iteration n-1. It's initialized at iteration 1 with S values.

At each cardinality step

• for each row of the candidate matrix, you check wether you can build multiple packings that are still valid by adding one (and only one) row of matrix S:

  • You iterate through each row of S (this could be made faster if you skip rows that are already in the packing itself). If it's valid, you append the considered row index to the packing, send this packing as a new result and add it to the future, next iteration candidate matrix (which will be smaller at each cardinality step, because some combination result in invalid packings).

This way, the candidate matrix is smaller and smaller at each iteration and you can stop as soon as there's no more candidates.

Example

S=
 1 0 0 1  (a)
 1 1 0 0  (b)
 0 0 1 0  (c)

Iteration 1

(initialization) : produce 3 results and candidates : a, b and c (initialization)

results

(a,b,c)

candidates

 1 0 0 1  (a)
 1 1 0 0  (b)
 0 0 1 0  (c)

Iteration 2

iterate on candidate, then on rows:

• take candidate a

  • skip row a (optimization 1)
  • try to combine it with row b -> fail
  • try to combine it with row c -> success
    • new results (ac) and new candidate (ac) for next time

• take candidate b

  • try to combine it with row a -> fail
  • skip row b (optimization 1)
  • try to combine it with row c -> success
    • new results (bc) and new candidate (bc) for next time

• take candidate c

  • skip a -> (already exists as a result)
  • skip c -> (already exists as a result)
  • skip row c (optimization 1)

New results matrix (a,b,c,ac,bc)

New candidates matrix

 1 0 1 1 (ac)
 1 1 1 0 (bc)

Iteration 3

Same as above...

• take candidate (ac)

  • skip row a (optimization 1)
  • try to combine it with row b -> fail
  • skip row c (optimization 1)

• take candidate (bc)

  • try to combine it with row a -> fail
  • skip row b (optimization 1)
  • skip row c (optimization 1)

No more candidates: end.

Final results matrix (a,b,c,ac,bc)

Final candidates matrix

 ()

About the optimizations

• optimization 1 is: no need to try to combine a row with a packing-candidate that already contains it