3
$\begingroup$

If I have the following pieces to a train set:

  • (12) Curve
  • (4) Straight

Such as this train set.

I'm looking for an algorithm (to which I can write a program) that creates/lists all permutations. It's not as simple as just creating a list , such as the following, where s=straight and c=curve, and creating all permutations, since the pieces are reversible:

sssscccccccccccc

For example, a Curve piece can either curve left or curve right. I thought about doubling the number of curve pieces and calling them 'cr' and 'cl' and then doing permutations on a list such as:

ssssclclclclclclclclclclclclcrcrcrcrcrcrcrcr

However, I think that is introducing more problems, so I'm thinking of creating a tree structure as such:

enter image description here Each level of tree represents adding a new piece, where cl=Curve Left, s = Straight, cr = Curve Right.

I would then traverse each path in tree structure and determine if it forms a 'solution'. A solution would be defined as starting point = ending point, however, that is a different problem/algorithm as it requires knowing the lengths and arcs of the pieces. The algorithm would need to account for solutions that consist of all pieces (16 in this case), 15, 14 ... down to 8 (as that would be the smallest number to make a circle from the trainset in the picture). To solve those solutions, I would just create paths to all the nodes at a given level. Does this seem reasonable or other thoughts?

$\endgroup$
  • $\begingroup$ Does the track you produce have to be a loop of some sort, or can it just be a line? $\endgroup$ – David Richerby Mar 10 '15 at 22:05
  • $\begingroup$ It has to be a 'solution', defined as an assembly of tracks that allow the train to move around indefinitely. I think that is a seperate problem, in that once all the permutations are found, another algorithm would 'assemble' them and test if starting point = ending point. $\endgroup$ – Mark Mar 10 '15 at 22:44
  • 2
    $\begingroup$ If you make a circle with 4 curves, you will never make an 8 with 4 curves and 2 straights. How long is a straight. Too much is undefined in your problem. $\endgroup$ – babou Mar 10 '15 at 23:41
  • $\begingroup$ good point, the original problem statement would not be able to make a classic 8 and a circle. I've updated problem statement. $\endgroup$ – Mark Mar 12 '15 at 14:47
  • $\begingroup$ The "length and arcs of the pieces" are not necessary to analyze anything. Everything is fully determine (up to scaling) when you know that 8 curves make a circle and 12 curves plus 4 straight make an eight shaped circuit. You can take the circle radius as unit. Then the straight elements have length 1 radius, and the curves make one eighth of a circle. $\endgroup$ – babou Mar 13 '15 at 13:35
3
$\begingroup$

I bought that set for my grand son (nice and cheap Ikea product, kids love it from 18 month to 80 years, though not rcommended before 3 years of age), so I am very experienced with the problem.

For the uninitiated, the tracks are oriented because they connect with a hole on one end and a hooking tongue on the other end. So curved tracks have to be placed with one side or the other up, depending on which way you want to turn. The Ikea picture does not make it obvious: the little plastic pieces are actually glued as tongue on one end of a track, but the curves track have grooves for the wheels on both sides.

Counting the configurations

I will use the word configuration for a way of putting the track elements together. It seems more appropriate than the word "permutation" which has a precise technical meaning.

The first analysis, described in this section, consist in evaluating the total number of possible configurations. This will help us to actually enumerate them in the next part.

You have 16 track elements, including 4 straight and 12 curved.

If you consider your 16 elements in succession, you have $\binom {16} 4 =\frac{16!}{4!\times 12!} $ ways of choosing a combination of positions for the 4 straights tracks, among 16.

Now, if you consider the curved tracks, they can be placed either as left curve or as right curve. For 12 tracks that makes $2^{12}$ possibilities (using train tracks to implement binary numbers makes for heavy duty computers).

So the total number of "permutations" (that use of the word does not seem too appropriate) is the product of the two numbers, since they correspond to independent choices, i.e., $$\frac{2^{12}\times 16!}{4!\times 12!} $$

But this answer may not be quite correct: if you have a closed circuit, you can consider it to start with any of the track elements, so that it counts for 16 "permutations", though one might consider it should count for 1. Hence, it might be appropriate to substract 15 from the result for each closed circuit that can be constructed. Geometric analysis of the shape of track elements shows that there are several closed circuits that can be constructed. Note that, except for the eight shape with crossing tracks, circuits are oriented, and each shape must me counted twice.

Other closed circuits are possible with with less track elements, in particular with exactly 8 curves, and 0, 2, or 4 straight. But we now ignore the issue of closed curves.

If you consider $n$ elements, $8\leq n\leq 16$, of which $m$ are straight, with $0\leq m\leq 4$, the number of circuits is $$\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Thus, for all possible values of $m$, with a number $n$ of elements, including at most 12 curved, the total number of circuits is: $$\sum_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Finally, considering all possible values of $n$ in $[8,16]$, we get the number of circuits: $$\sum_{n=8}^{n=16} \sum_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Then there is the small number of cases when the circuit is closed, which one can analyse to count all their starting element variants as the same circuit. Note that when the track does not cross itself, each closed shape comes in two variants: clockwise and counter-clockwise. But should I go in so many details.

Enumerating the configurations

The analysis used for counting configurationscan be repeated identically to enumerate them.

We consider $n$ track elements, of which $m$ are straight and $p$ are curved: $n=m+p$. We want to enumerate all the circuits that use all these elements.

First, we want to place the $m$ straight track in the sequence of $n$ track element position. For this you must enumerate all combinations of $m$ integers among the first $n$ integers. Algorithms already exists to enumerate these conbinations, available in wikipedia, or fromn other sources, so there is no point in developing that further here.

Then, for each such combination, you simply try all possible combinations of left or right positionning of curved track elements, which you can do by enumerating all possible sequences of$0$ and $1$, hence simply using a counter to enumerate in binary all integers from $0$ to $2^p-1$. It is advisable to use the fast changing bits in the enumeration on the end side of the configuration, in order to factor the beginning of computations that might be used to check whether the configurations give a closed circuit.

Of course, this can be repeated for other values of $m$ and $p$. But configurations for smaller values are just prefixes of the configurations for the maximum values of $n$ and $m$. So, doing it only for the maximum values should be enough to observe on the fly whatever we are interested in regarding smaller configurations. THis is detailed regarding closed circuits in the next section.

Checking a configuration

Given a configuration for a sequence of track elements, and starting from porition (0,0), and direction angle 0, one can compute the position and direction at the end of the first track element, then propagate to the end of the second, and so on till the last. The circuit is closed if the end of the last track element is in position (0,0) with direction angle 0.

The shape of the track elements is determined by the fact that 8 curves make a full circle, and 12 cuves and 4 straight make an eight shaped curve. One can use the radius of the circle as distance unit, Then the staight track elements have a length of 1 radius.

For simplification, one can also take$45^o$ as the angle unit, so that each curved track changes the orientation by plus (left) or minus (right) one unit, and 8 units make a full circle. Hence orientation can be represented byrf an integer modulo 8.

Positions of track elements ends should not be computed as real numbers, but as expression using integers and $\sqrt 2/2$, of the form $a+b\sqrt 2/2$, a bit like complex numbers where $i$ is replaced by $\sqrt 2/2$. That makes the computations much cheaper, based on integer arithmetics on pairs $(a,b)$, and the $\sqrt 2/2$ ultimately cancel each other for closed circuits.

Actually, to explain it formally, plane coordinates reachable from the origin with straight and curved track elements are all expressible as $a+b\sqrt 2/2$. Hence, since 2 coordinates are used on the plane, and since $1$ is incommensurable with $\sqrt 2$, plane coordinates can be seen as a 4-dimensional vector space over the field $\mathbb Q$ of rationals, or better, since we use only integer coordinates in that vector space, as a 4-dimensional module over the ring $\mathbb Z$ of integer. See this mathematics question which is a followup to the question answered here. Hence following track element by track element the configuration of a circuit, for the purpose of checking whether it is closed, can be done using only integer addition and substraction.

A circuit starts at the origin with orientation $0$. The circuit is closed when it ends also at the origin with orientation $0$. In the four dimensional space, the coordinates of the origine are $(0,0,0,0)$

I guess any reader can further develop the computation details, for each type of track element. (this answer is already very long).

As explained in the previous section, doing the enumeration for maximum values of $n$ and $m$ will include smaller configurations as prefixes. In particular, if you are looking for closed circuits of all sizes, the simplest is to compute all configurations with the maximum values of $n$ and $m$, and check closure not just at the end, but at every step of the computation of track elements positions. However, there is a possibility for some optimization in performing these checks, as no closed circuit can be found with less than eight curved track elements.

$\endgroup$
  • $\begingroup$ This answer is missing important information: which of the possible circuits is your grandson's favourite? :-D $\endgroup$ – David Richerby Mar 15 '15 at 11:29
  • $\begingroup$ @DavidRicherby Actually, I was the only one who made closed circuits. That is a bit hard for younger kids, though my seven years old grand sonv can now do it. But my youngest started putting tracks together when hardly more than 18 months, making small open circuits (seldom more than a few elements). Then they roll the train on the track. The cars are connected by magnets. An interesting point is that no one tries to make a simple circular track. Right now, I find more interesting to understand the mathematical structure of the thing. There seem to be two vector spaces. $\endgroup$ – babou Mar 15 '15 at 11:43
  • $\begingroup$ Yes, permutation is the correct technical term here, as we are looking to permute all the members of a set, order does matter. Yes, there are particular nuances of the set, such that if the tracks cross-paths, you must be doing it at a point where two bridge (straight) pieces are used: google.ca/…. $\endgroup$ – Mark Mar 15 '15 at 14:00
  • $\begingroup$ I don't think the fact that it has tounge/groove for the pieces matter for the analysis. They actually could be taken out a put back in place once a solution was found. $\endgroup$ – Mark Mar 15 '15 at 14:19
  • $\begingroup$ I'm going to accept babou's answer. Thank you for the detailed analysis. I used the tree structure in the original post to write a program that assembled each of the pieces for each path to a leaf node in the tree and using a 2d drawing program. I ran it for each of the tree depths of 8-16. Some solutions materialized that I hadn't thought of. I have the source code checked into github and will write a wiki post about it and show the solutions. I'll post the link here if anyone is interested. Thanks again. $\endgroup$ – Mark Mar 15 '15 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.