铁路轨道的排列（堆栈实现）

Question

编号为 1、2、...、n 的引擎在左侧的线上，需要重新排列（排列）引擎，因为它们离开了右侧轨道。位于支线轨道上的引擎可以留在原地，也可以沿正确轨道发送，但永远无法返回到引入轨道。例如，如果 n = 3，并且我们在左侧轨道上有编号为 1、2、3 的引擎，则 3 首先进入支线轨道。然后我们可以将 2 发送到支线，然后在其右侧的途中，然后在途中发送 3，然后 1，获得新顺序 1,3,2。我们必须找到特定 n 的所有可能排列。

对于 n=1，答案 = 1；

对于 n=2 答案 = 2;

对于 n=3 答案 = 5;

没有发现任何共性。使用 Stack Implementation 会很有帮助。

但欢迎任何解决方案。

p.s。这不是家庭作业问题，因为我是一个自学成才的人。

Answer 1

系统的状态可以通过给出 3 个（有序的！）引擎列表来描述，分别位于左轨道、支线和右轨道。给定状态，可以计算出所有可能的移动。这创建了一棵可能性树：树的根是初始状态，每一步都对应一个导致新状态的分支。分支（叶子）末端的最终状态是您在正确轨道上的最终位置。

所以，你必须建造并探索所有的树，最后你必须数所有的叶子。而树是一种常见的数据结构。

澄清一下，本例中的树不会替换堆栈。堆栈用于存储您的数据（引擎的位置）；该树用于跟踪算法的进度。每次你有一个状态（树的一个节点）你必须分析你的数据（=堆栈的内容）并找到可能的移动。每一步都是算法树中的一个分支，它会导致堆栈的新状态（因为引擎已经移动）。所以基本上，对于树的每个节点，您将拥有 3 个堆栈中的一个 "configuration"。

Answer 2

这是我对递归解决方案的尝试（请参阅 Java 代码中的注释）：

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
}

上面的递归解决方案实际上计算了每种可能性。对于组合解决方案，我们考虑 n 支线内外运动的所有组合，其中相邻的此类运动等同于直接从左轨道到右轨道的运动。有 2n choose n 种这样的组合。现在让我们统计无效的：

考虑分支的 (n - 1) 个输入和 (n + 1) 个输出的所有组合。所有这些都包括一个点，p，其中当没有火车在其上时，火车被视为离开支线。假设 p 前面有 k 个输入和 (k + 1) 个输出 - 那么剩余输入的数量是 (n - 1 - k)；和剩余的补牌，(n + 1) - (k + 1) = (n - k)。

现在从 after p 开始反转这些组合中的每一个的来龙去脉，这样 in 就变成了 out 和 out in。每个反转的部分都有必然 (n - k) 进和 (n - 1 - k) 出局。但是现在，如果我们将 p 之前和之后的来龙去脉加起来，我们会得到 k + (n - k) = n 进水和 (k + 1) + (n - 1 - k) = n 出水。我们刚刚统计了 n 个 ins 和 n out 无效的组合数。如果我们假设一个这样的组合可能没有被计算在内，理论上在它的 p 之后反转那个组合，你会发现一个 (n - 1) 进和 (n + 1) 出的组合没有被计算。但根据定义，我们已经将它们全部计算在内，因此我们假设的额外组合不存在。

总有效组合是 2n choose n - 2n choose (n + 1)，加泰罗尼亚数字。

（改编自 Tom Davis 的解释：http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf）

Answer 3

首先，请注意，您可能会忽略将火车从进站直接移到出站的可能性：这样的移动可以通过将火车移至支线然后再次出站来完成。

将火车从进站移动到支线表示为 (，火车从支线移动到出站为 )，您将得到火车的排列和 n 对字符串之间的双射正确平衡的括号。该陈述需要证明，但证明中唯一困难的部分是证明没有两个平衡括号串对应于相同的排列。这样的字符串的个数是第n个Catalan number，或者choose(2n, n)/(n+1)，其中choose(n, k)是从n中选择k项的方式数。

这是计算解决方案的代码：

def perms(n):
    r = 1
    for i in xrange(1, n+1):
        r *= (n + i)
        r //= i
    return r // (n + 1)

您可以使用此代码生成所有排列，这也暴露了解决方案的加泰罗尼亚语性质。

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))

输出：

[[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]]

铁路轨道的排列（堆栈实现）

Permutation At A Railway Track(Stack Implementation)

algorithm

stack

combinatorics

catalan