**Enumerating every pair of cycles in Kn**
I'm currently doing research in knot theory with one of my professors. I'm running into an issue where for n nodes, I need to generate every pair of length i and j cycles (i + j = n). For example, K6 is pretty simple to verify by hand; if you label each node 1-6, then you should come out to (6 choose 3)/2 = 10 different pairs of disjoint cycles (123,456),(124,356),(125,346),(126,345),(134,256), (135,246),(136,245),(145,236),(146,235),(156,234). Once i or j > 3, it gets more complicated. If I'm working with K8, one of the cycle pairs will be (1234,5678), but since 1234,1243,1423 as well as 5678,5687,5867 are not cyclically identical or mirrors of each other, every pair of those cycles must be included in the enumeration. K6 is easier because 3 nodes only have 1 permutation that isn't cyclically identical or a mirror. I'm having trouble finding an efficient way to do this, I currently have it so it only runs once and the same enumeration of cycles is used for every trial to remove unnecessarily recalculating it, but I still can't find a better way than brute forcing every permutation and comparing every element and removing cyclically identical or mirror pairs of cycles, which, as you can guess, blows up very quickly in complexity.
For the reference, I'm doing this in Matlab.
Thanks in advance to anyone that can help.
*
Last edited by skipjack; April 15th, 2019 at 12:05 PM.
* |