arrays - APL 中的 3+ 维真值表

Question

我想枚举满足给定条件的 3 个或更多有限值变量的所有组合(值的元组)。用数学符号表示:

例如(灵感来自 Project Euler problem 9 ):

一次两个变量的真值表很简单:

    a ∘.≤ b
1 1 1 1
0 1 1 1
0 0 1 1
    b ∘.≤ c
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1

经过一番苦思冥想，我设法将它们结合起来，通过计算前者的每个 4 值行的 ∧ 与后者的每个 4 值列，并在正确的轴上公开 (⊃)，介于 1 之间和2:

    ⎕← tt ← ⊃[1.5] (⊂[2] a ∘.≤ b) ∘.∧ (⊂[1] b ∘.≤ c)
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1

0 0 0 0 0
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1

0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
0 0 0 1 1

然后我可以使用它的 ravel 来过滤所有可能的值元组:

    ⊃ (,tt) / , a ∘., b ∘., c
1 1 1                       
1 1 2                       
1 1 3                       
1 1 4                       
1 1 5                       
1 2 2                       
1 2 3                       
...
3 3 5                       
3 4 4                       
3 4 5                       

这是解决 APL 中此类特定问题的最佳方法吗？

对于此示例或一般情况，是否有更简单或更快的公式？

<小时/>

更一般地说，将我上面的(天真的？)数组方法与传统标量语言进行比较，我可以看到我正在将每个循环转换为一个附加维度:3 个嵌套循环变成一个 3 阶真值表:

for c in 1..NC:
    for b in 1..min(c, NB):
        for a in 1..min(b, NA):
            collect (a,b,c)

但是在标量语言中，我们可以一路进行优化，例如尽快打破循环，或者动态选择循环边界。在这种情况下，我什至不需要测试 a ≤ b ≤ c，因为它隐含在循环边界中。

在此示例中，两种方法的复杂度均为 O(N³)，因此它们的运行时间仅相差一个因子。但我想知道:如果需要的话，如何以更优化的方式编写数组解决方案？

是否有任何好书或在线资源可以解决 APL 中的算法问题或最佳实践？

Answer 1

这是一种替代方法。我不确定它是否会运行得更快。 根据标量语言的算法，c 的可能值为

⎕IO←0
c←1+⍳NC

在内循环中，b 和 a 的值为

b←1+⍳¨NB⌊c
a←1+⍳¨¨NA⌊b

如果我们将这些结合起来

r←(⊂¨¨¨a,¨¨¨b),¨¨¨c

我们得到一个(a，b，c)三元组的嵌套数组，可以在矩阵中展平和重新排列

r←∊r
(((⍴r)÷3),3)⍴r

<小时/>

添加:

Morten Kromberg 向我发送了以下解决方案。在 Dyalog APL 上，它的效率比上面的高约 30 倍:

⎕IO←1
AddDim←{0≡⍵:⍪⍳⍺ ⋄ n←0⌈⍺-x←¯1+⊢/⍵ ⋄ (n⌿⍵),∊x+⍳¨n} 
TTable←{⊃AddDim/⌽0,⍵}
TTable 3 4 5