3

交换网络

编号为 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；

没有发现任何普遍性。使用堆栈实现将非常有帮助。

但欢迎任何解决方案。

ps 这不是作业问题，因为我是一个自学成才的人。

4

3 回答 3

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

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

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

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

于 2015-05-10T01:12:54.983 回答
1

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

表示一列火车从输入到支线 as(和一列火车从支线到输出 as )，你会得到火车的排列和 n 对正确平衡括号的字符串之间的双射。该陈述需要证明，但证明中唯一困难的部分是证明没有两串平衡括号对应于相同的排列。此类字符串的数量是第 n 个加泰罗尼亚数，或 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]]
于 2015-05-10T05:30:52.603 回答
0

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

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

澄清一下，这种情况下的树不会取代堆栈。堆栈用于存储您的数据（引擎的位置）；树用于跟踪算法的进度。每次你有一个状态（树的一个节点）时，你都必须分析你的数据（=堆栈的内容）并找到可能的移动。每一次移动都是算法树中的一个分支，它会导致堆栈的新状态（因为引擎已经移动）。因此，基本上您将为树的每个节点拥有 3 个堆栈的一个“配置”。

于 2015-05-09T15:42:34.553 回答