algorithm - 渐进式索引成语中的 APL 身份

Question

习语 #1 和 #5 是 FinnAPL Idiom Library两者具有相同的名称:“Progressive index of (without replacement)”:

((⍴X)⍴⍋⍋X⍳X,Y)⍳(⍴Y)⍴⍋⍋X⍳Y,X             ⍝ idiom #1
((⍋X⍳X,Y)⍳⍳⍴X)⍳(⍋X⍳Y,X)⍳⍳⍴Y             ⍝ idiom #5

在这种口是心非的背后是否有任何重要的身份？

旁注:

APL 对身份的强调从一开始就是 APL 与众不同的特征之一。 APL 的创始人 Kenneth Iverson 说:

”同一性是两个不同表达式之间的等价。尽管恒等式通常仅被认为是数学分析的工具，但它们可以成为一种重要的实用工具，用于简化和以其他方式修改用于定义函数的表达式。”

Answer 1

这些成语有一些共同点。两者的最后一步是索引操作，它们都使用某种镜像连接策略，也许最重要的是，左右参数的输出对于两者都是相同的。这大大简化了对身份的搜索，因为我们可以将 #1 的正确参数与 #5 的正确参数进行比较:

(⍴Y)⍴⍋⍋X⍳Y,X                ⍝ right arg #1
(⍋X⍳Y,X)⍳⍳⍴Y                ⍝ right arg #5

可以简化搜索的另一件事是删除或修改任何截断输出的内容，因为两个参数的输出在没有截断的情况下是相同的。习语#1使用(⍴Y)⍴将其截断为Y的长度，而习语#5中右参数的长度取决于的长度⍳⍴Y中的Y。第一种情况可以去掉截断，第二种可以修改为Y,X的全长:

⍋⍋X⍳Y,X                     ⍝ #1
(⍋X⍳Y,X)⍳⍳⍴Y,X              ⍝ #5

鉴于两个表达式都包含 ⍋X⍳Y,X，让我们将其分配给变量 A ← ⍋X⍳Y,X 并简化。然而，重要的是要指出，我们现在拥有的恒等式仅适用于 A 是置换向量的情况，稍后我将详细讨论这一点。同时，我们有这个身份:

⍋A ←→ A⍳⍳⍴Y,X

由于“Y,X”在此表达式中除了提供矢量长度外什么都不做，并且由于该长度等于“A”，因此恒等式可以简化为其最终形式:

⍋A ←→ A⍳⍳⍴A, where A is a permutation vector

这很有道理。标识左侧的升级运算符返回 A 的每个值在按升序排列时将具有的索引值。右侧的 index-of 运算符返回 A 中 ⍳⍴A 的升序值所在的索引。例如:

5 2 1 4 3                   ⍝ A←5 2 1 4 3
3 2 5 4 1                   ⍝ ⍋A

5 2 1 4 3                   ⍝ A←5 2 1 4 3
1 2 3 4 5                   ⍝ ⍳⍴A
3 2 5 4 1                   ⍝ A⍳⍳⍴A

查看最后两行，1 在 A 中的索引为 3，2 有 2，3 有 5，4 有 4，最后 5 的索引为 1。这是有道理的，因为这几乎是定义升级运算符的作用。

置换向量

如前所述，此恒等式仅在 A 是置换向量时有效。在他的文章 Notation as a Tool of Thought 中，Kenneth Iverson 定义了一个排列向量:“一个向量 P，其元素是其索引的某种排列(即 ^/1=+/P∘.= ⍳⍴P) 将被称为置换向量。”查看一些成语本身，您可以看到这个想法以各种方式表示:

Y[⍋Y]^.=X[⍋X]           #6 permutations of each other 
X^.=⍋⍋X                 #7 test if permutation vector
X[⍋X]^.=⍳⍴X             #29 test if permutation vector
⍋X                      #48 Inverting a permutation 
X⍳⍳⍴X                   #212 Inverting a permutation
^/1=+⌿X∘.=⍳⍴X           #281 test if permutation vector
^/(⍳⍴X)∊X               #454 test if permutation vector
A←⍳⍴X ⋄ A[X]←A ⋄ A      #654 Inverting a permutation 

在成语#7 中，表达式的右侧是升基数成语，我在另一个 post 中讨论过。 ，在那篇文章中，我谈到了升级运算符在排名和索引这两种状态之间来回切换的事实，因此我们有以下两个身份:

⍋X ←→ ⍋⍋⍋X ←→ ⍋⍋⍋⍋⍋X ...
⍋⍋X ←→ ⍋⍋⍋⍋X ←→ ⍋⍋⍋⍋⍋⍋X ...

第二个身份可以扩展如下，如果 X 是一个排列向量，如习语 #7 所建立的:

X ←→ ⍋⍋X ←→ ⍋⍋⍋⍋X ←→ ⍋⍋⍋⍋⍋⍋X …

我们知道升级运算符会返回从 1 到参数中值个数的所有数字。再应用两次升级运算符，您将以相同的顺序获得完全相同的向量。因此习语 #7 只是说置换向量是一个包含从 1 到某个其他值的所有数字一次且仅一次的向量。 (这里假定 1 被设置为第一个索引值。)

关于上面的习语列表，另一个有趣的地方是习语#48 和#212 是答案中讨论的身份的左侧和右侧:

⍋A ←→ A⍳⍳⍴Y,X