Rearrangement on the railroad track (stack implementation)
Engines numbered 1, 2, ..., n are on the line to the left, and it is advisable to rearrange (rearrange) the engines as they enter the right lane. A motor that is on the spur track can be left or sent on the right track, but it can never be sent back to the incoming track. For example, if n = 3 and we move motors numbered 1,2,3 to the left track, then 3 goes to the spur first. Then we could send 2 on the spur, then on the way to the right, then send 3 on the way, then 1, getting a new order 1,3,2. We have to find all possible permutations for a particular n.
For n = 1 answer = 1;
For n = 2, the answer = 2;
For n = 3, the answer = 5;
I did not find any commonality. Using the Stack Implementation would be very helpful.
But any solution is appreciated.
ps This is not a homework question as I am a self-taught person.
Here's my attempt at a recursive solution (see comments in Java code):
private static int result = 0;
private static int n = 3;
public static void g(int right,int spur){
if (right == n) // all trains are on the right track
result++;
else if (right + spur < n) // some trains are still on the left track
g(right,spur + 1); // a train moved from the left track to the spur
if (spur > 0) // at least one train is on the spur
g(right + 1,spur - 1); // a train moved from the spur to the right track
// (also counts trains moving directly from the left to right track)
}
public static void main (String[] args){
g(0,0);
System.out.println(result); // 5
}
The recursive solution above actually accounts for every possibility. For a combinatorial solution, consider all combinations of motions n
on and out of the spur, where adjacent such motions are equivalent to motions directly from the left to the right path. There are such combinations. Now count the invalid ones:
Consider all combinations of spur (n - 1)
ins and (n + 1)
outs. This all includes the point p
where the train counts as coming out of the spur when there are no trains on it. Let's say it p
has k
ins and (k + 1)
outputs preceding it - then the number of remaining ins is (n - 1 - k)
; and the remaining outputs (n + 1) - (k + 1) = (n - k)
.
Now flip the entries and exits for each of these combinations, starting with p
, so that the resulting exit and exit . Each of the back sections must be (n - k)
ins and (n - 1 - k)
out. But now, if we add up the number of entries and exits before and after p
, we get k + (n - k) = n
ins and (k + 1) + (n - 1 - k) = n
outs. We have just counted the number of n
ins and n
outs combinations that are invalid. Assuming one such hand may not have been counted, theoretically undo that hand after it p
and you will find a combination of (n - 1)
ins and (n + 1)
outs that did not count. But by definition we counted them all, so our supposed complementary combination could not exist.
Final valid combinations:, 2n choose n - 2n choose (n + 1)
Catalan numbers.
(Adapted from Tom Davis' explanation here: http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf )
source to share
First, note that you can ignore the possibility of a train moving from an inbound directly to an outbound one: such a move can be made by moving the train to the spur and then again.
Let's denote the movement of the train from entering to spur as (
, and the train will move from spur to outgoing as )
, and you will get a bijection between train permutations and rows of n pairs of correctly balanced brackets. This statement needs a proof, but the only hard part of the proof is that no row of balanced parentheses match the same permutation. The number of such rows is n'th Catalan number or choose (2n, n) / (n + 1), where choose (n, k) - the number of ways to select k elements from n.
Here's the code to calculate the solution:
def perms(n):
r = 1
for i in xrange(1, n+1):
r *= (n + i)
r //= i
return r // (n + 1)
You can generate all the permutations with this code, which also reveals the Catalan nature of the solution.
def perms(n, i=0):
if n == 0:
yield []
for k in xrange(n):
for s in perms(k, i+1):
for t in perms(n-k-1, i+k+1):
yield s + [i] + t
print list(perms(4))
Output:
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1],
[0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3],
[2, 1, 0, 3], [1, 2, 3, 0], [1, 3, 2, 0], [2, 1, 3, 0],
[2, 3, 1, 0], [3, 2, 1, 0]]
source to share
The state of the system can be described by providing 3 (ordered!) Engine lists, left, spurs and right tracks. Given the status, all possible movements can be calculated. This creates a tree of possibilities: the root of the tree is the initial status, and each move corresponds to a branch that leads to a new status. The final status at the end of the branch (leaf) is your final position on the right track.
So, you need to collect and study the entire tree, and at the end you must count all the leaves. And the tree is a common data structure.
To clarify, a tree would not replace stacks in this case. Stacks are used to store your data (position of motors); the tree is used to track the progress of the algorithm. Every time you have a status (a node of the tree) you have to parse your data (= stack contents) and find possible moves. Each movement is a branch in the tree of the algorithm, and this results in a new status of the stacks (because the engine has moved). This way, you basically have one "configuration" of 3 stacks for each node in the tree.
source to share