A hack inspired by a 2009 post by Christopher Carlson on the Mathematica blog entitled “Minimum Inventory, Maximum Diversity”, a generalization of the yin-yang symbol. Here we consider (without loss of generality) only half-turn-symmetric configurations.
The number of collages on N intervals is OEIS A054726, “Number of graphs with n nodes on a circle without crossing edges”.
| intervals | configurations |
|---|
It’s interesting and amusing that the non-crossing chord diagrams on N nodes on a circle are homeomorphic to these non-crossing circle diagrams of N nodes on a line. It’s intuitive that it is so if you consider that the property of crossing, here, is topological, so it survives deformations, including a deformation that puts a point on the circle at infinity.
The code herein initially computes a compact DAG representation of the set of distinct non-crossing collages with a worst-case size only quadratic in the number of intervals. (To represent the 3.1e17 collages on 19 intervals, the DAG contains 8555 nodes, thus representing some 3.6 × 10¹³ collages per DAG node.) The DAG provides an efficient way to compute the total number of collages and to compute the ith collage from that exponentially large set. Among other things, this means you can sample collages from the set with uniform probability.