You might find zero suppressed binary decision diagrams (ZDDs) useful. They also allow simple random generation of all kinds of objects (even constrained ones).

You might find zero suppressed binary decision diagrams (ZDDs) useful. They also allow simple random generation of all kinds of objects (even constrained ones). Knuth adjusted his algorithm X for ZDD and got some nice speedups.