3+ dimensional truth table in APL

Question

I would like to enumerate all the combinations (tuples of values) of 3 or more finite-valued variables which satisfy a given condition. In math notation:

For example (inspired by Project Euler problem 9):

The truth tables for two variables at a time are easy enough:

    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

After much head-scratching, I managed to combine them, by computing the ∧ of every 4-valued row of the former with each 4-valued column of the latter, and disclosing (⊃) on the correct axis, between 1 and 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

Then I could use its ravel to filter all possible tuples of values:

    ⊃ (,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                       

Is this the best approach to this particular class of problems in APL?

Is there an easier or faster formula for this example, or for the general case?

---

More generally, comparing my (naïve?) array approach above to traditional scalar languages, I can see that I'm translating each loop into an additional dimension: 3 nested loops become a 3-rank truth table:

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

But in a scalar language one can effect optimizations along the way, for example breaking loops as soon as possible, or choosing the loop boundaries dynamically. In this case I don't even need to test for a ≤ b ≤ c, because it's implicit in the loop boundaries.

In this example both approaches have O(N³) complexity, so their runtime will only differ by a factor. But I'm wondering: how could I write the array solution in a more optimized way, if I needed to do so?

Are there any good books or online resources that address algorithmic issues or best practices in APL?

Answer 1

Here's an alternative approach. I'm not sure if it would run faster. Following your algorithm for scalar languages, the possible values of c are

⎕IO←0
c←1+⍳NC

In the inner loops the values for b and a are

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

If we combine those

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

we get a nested array of (a,b,c) triplets which can be flattened and rearranged in a matrix

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

---

ADD:

Morten Kromberg sent me the following solution. On Dyalog APL it's ~ 30 times more efficient than the one above:

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