3

我想枚举满足给定条件的 3 个或更多有限值变量的所有组合（值的元组）。在数学符号中：

例如（受Project Euler 问题 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 算法问题或最佳实践的好书或在线资源？

4

1 回答 1

2

这是另一种方法。我不确定它是否会运行得更快。c按照您的标量语言算法，可能的值为

⎕IO←0
c←1+⍳NC

在内部循环中， forb和的值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
于 2014-01-07T17:18:03.170 回答