patternMinor
How many permutations in a trainset?
Viewed 0 times
trainsetpermutationsmanyhow
Problem
If I have the following pieces to a train set:
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:
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?
- (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:
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?
Solution
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,
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,
Context
StackExchange Computer Science Q#40296, answer score: 3
Revisions (0)
No revisions yet.