排列的概念在计算机科学中有许多应用，例如在排序算法的分析和分布式系统的实现中。从形式上讲，置换是集合到自身的双射。为了简单起见，让我们将自己限制在前n个正整数的集合[n]：＝{1，2，…，n}，并用Sn表示[n]上所有排列的集合。用n元组(σ(1)，σ(2)，σ(n))。交换一个排列的两个元素会产生另一个排列。对于i，j∈[n]设Tij:Sn→Sn是交换i和j图像的映射，即，如果σ∈Sn，则τ：=Tij(σ)由τ(i)=σ(j)，τ(j)=σ。实例设σ=(2，4，3，1)。则T13(σ)=(3，4，2，1)。现在，考虑只允许一些对(i，j)的交换。对于任意整数d≥0，设
Pd:={(i，j)∈[n]×[n]：i=j或d≤j−i≤n−d}
假设一个置换τ是(d，)-reachable from σ if there are (i1, j1),(i2, j2), . . . ,(i，j) ∈ Pd such that the corresponding swaps transform σ to τ , that is, τ = Tij`◦ · · · ◦Ti2j2◦Ti1j1(σ)。
问题：
-
证明对于任何正整数n，置换(n，n−1，…，1)是(1，bn/2c)-可从(1，2，…，n)到达的。
-
找出τ是否从σ(d，
)-reachable from σ, one may apply bidirected search as follows: First generate all permutations that are (d, b/2c)-可达。接下来生成从τ到(d，d`/2e)的所有置换。最后，如果生成的两个集合相交，则报告"是"，否则报告"否"。使用伪代码描述算法；特别是描述如何生成排列集合。(您可以假设给定的参数是有效的：您不需要实现错误处理。) -
使用Java编程语言实现上一个任务的算法。显示您的代码。使用您的实现来求解，对于所有d=1，2，4和
= 1, 2, . . . , 9, whether (9, 8, . . . , 1) is (d,)-可从(1，2，…，9)到达。将结果显示为4×9矩阵。
这是赫尔辛基大学CS硕士项目选拔的前期工作。请不要以目前的形式回答这个问题。