Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Closed geometry: a train track problem

by InfiniteSilence (Curate)
on Jan 04, 2006 at 00:40 UTC ( #520773=note: print w/replies, xml ) Need Help??


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

  • Comment on Re: Closed geometry: a train track problem

Replies are listed 'Best First'.
Re^2: Closed geometry: a train track problem
by pboin (Deacon) on Jan 04, 2006 at 12:43 UTC

    I think you're on the right track (get it?) as far as permutations. The problem I've had (and it's probably me being short-sighted) is that certain pieces (switches) not only have three endpoints instead of two, but they also can have that offshoot node either left or right-handed, depending on which side is up. So, do they take two positions in the permutation matrix?

    Some of you will now be thinking of my omission: the other direction. That same switch piece can not only be flopped left-to-right, but also end-over-end. So, when we get involved with tracking male and female connectors, there's really *four* states for a switch piece, and two for more regular pieces.

    I'm no mathemetician, but this seems to be the most difficult part of the problem, followed closely by differentiating acceptable collisions from unacceptable ones.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://520773]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (2)
As of 2021-09-19 09:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?