http://www.perlmonks.org?node_id=520773


in reply to Closed geometry: a train track problem

You know, starting out with a finite number of pieces should mean that there is a finite number of connecting track sequences. If you are choosing from N pieces you can produce a series of subsets which can be viewed using n-choose-k.

N-choose-k only gives us a certain number of distinct subsets. It answers the question, "How many ways can I pick k pieces from the box?" For instance, if the set was {1,2,3} we and we want sets of two we wind up with ({1,2}, {1,3}, {2,3}) or 3!/2!(3-2)! == 6/2(1)= 3 distinct sets. Running through this process iteratively should reveal all of the possible subsets (e.g. 4, 5, 6...N - 1).

Any given subset is going to have N! orderings or permutations. Going back to our above example of {1,2,3} a subset of {1,2} has two permutations: {1,2} and {2,1}. A set of three elements (i.e. {a,b,c}) will have 6 because 3! == 3*2*1 == 6.

Armed with the permutations for each k-subset we can start the process of eliminating those that cannot form a complete circuit by graphing out the connections somehow. It is fair to say that any less than four pieces will not produce the desired result, so k < 4 cases should be ignored.

In order to discover whether your graph is undirected or not, you would probably need to build an adjacency matrix and check to see if it is symmetric.

Celebrate Intellectual Diversity