search

statusfailed / open-hypergraphs

a datastructure for scalable combinatorial syntax
MIT License
10 stars 0 forks source link

Knuth's latest sparse hypergraph code #2

Open chadbrewbaker opened 6 months ago

chadbrewbaker commented 6 months ago

Knuth's latest sparse hypergraph code he gave his tree lecture on a few weeks ago. I haven't kicked the tires yet. For f :: 2^{a} -> 2^{b} it should make a really good solver.

https://www-cs-faculty.stanford.edu/~knuth/programs/ssxcc.w

This is the z3py MIN_DOM_SET solver my Haskell code shells out to for finding the list of non-identity cycles you have to sample to detect any permutation other than the identity. I could probably re-write it into other covering solvers for performance comparison. https://github.com/chadbrewbaker/endoscope/blob/master/src/min_dom_z3.py

See https://oeis.org/A186202 - for non-primes you can save a lot of tests by not doing brute N! search.

statusfailed commented 6 months ago

Only had a quick look, but is this for doing matching of hypergraphs? i.e., solving hypergraph isomorphism?