arrays - APL中的3+维真值表

我想列举满足给定条件的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值行的with与后者的每个4值列进行计算，并在正确的轴上披露（and）在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

然后，我可以使用它的奇特过滤所有可能的值元组：

    ⊃ (,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中算法问题或最佳做法的好书或在线资源？

最佳答案

这是另一种方法。我不确定它是否会运行得更快。
按照标量语言的算法，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

关于arrays - APL中的3+维真值表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20907144/