Partitions#

It’s harder to read code than to write it. –Joel Spolsky

]box on

Was ON

We often need to group or select items in an array based on some criterion – perhaps stretches of items that are equal, or perhaps we have a boolean mask indicating which stretches of elements should be joined up.

Other resources:

Note

This is a feature that different APL dialects treat differently. Dyalog’s ⎕ML setting allows a degree of conformity if you need it: if ⎕ML≥3, the symbol ⊂ means the same as ⊆. We’ll use the default Dyalog approach throughout.

Partition ⊆#

The glyph Partition, ⊆, selects groups elements based on a vector where new selections are started where the corresponding element is larger than its predecessor. In its simplest form it’s like Compress, but enclosing elements corresponding to stretches of 1s. Compare:

1 1 0 1 0 0 0 0 1 1 0 1⊆⍳12 ⍝ Partition
1 1 0 1 0 0 0 0 1 1 0 1/⍳12 ⍝ Compress

┌───┬─┬────┬──┐
│1 2│4│9 10│12│
└───┴─┴────┴──┘

1 2 4 9 10 12

This can be supremely handy: apply some predicate to an array to give a boolean vector. Use enclose to get the matching elements, grouped. As we noted above, the left argument array doesn’t have to be Boolean, just integer. That gives us a bit more flexibility in our mapping.

Partitioned enclose A⊂B#

Partitioned enclose, A⊂B, groups items based on a Boolean mask where enclosures start on 1. For example:

1 0 1 0 1 0 1 0 1 0⊂⍳10

┌───┬───┬───┬───┬────┐
│1 2│3 4│5 6│7 8│9 10│
└───┴───┴───┴───┴────┘

We can use this to group stretches of elements which are equal:

{⍵⊂⍨1,2≠/⍵} 1 1 1 1 1 2 2 1 4 4 4 4 1 1 2 2

┌─────────┬───┬─┬───────┬───┬───┐
│1 1 1 1 1│2 2│1│4 4 4 4│1 1│2 2│
└─────────┴───┴─┴───────┴───┴───┘

We can apply the same technique to group based on sign:

{⍵⊂⍨1,2≠/×⍵} 0 0 1 2 3 0 ¯1 ¯7 ¯8 0 0 1 2 3

┌───┬─────┬─┬────────┬───┬─────┐
│0 0│1 2 3│0│¯1 ¯7 ¯8│0 0│1 2 3│
└───┴─────┴─┴────────┴───┴─────┘

In the above two examples we generate the mask by a windowed reduction of size 2:

{2≠/×⍵} 0 0 1 2 3 0 ¯1 ¯7 ¯8 0 0 1 2 3

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

but we also need to prepend a 1, as we want the first partition to start at the beginning.

Note that the left argument doesn’t have to be the same length as the right. If it’s shorter, it will be padded with zeros, allowing us a convenient way to chop a vector into a head and tail:

1 1⊂⍳10

┌─┬──────────────────┐
│1│2 3 4 5 6 7 8 9 10│
└─┴──────────────────┘

Non-boolean left ⊂#

From v18 of Dyalog, the left argument is no longer restricted to a Boolean array, which allows us to generate empty partitions:

1 0 0 2 0 0 3 0 1 ⊂ ⍳20

┌─────┬┬─────┬┬┬───┬──────────────────────────────────┐
│1 2 3││4 5 6│││7 8│9 10 11 12 13 14 15 16 17 18 19 20│
└─────┴┴─────┴┴┴───┴──────────────────────────────────┘

We can think of each number as specifying how many partitions beyond its neighbor to the left it is. So 0 means same partition, 1 means new partition, 2 means “skip one”, 3 means “skip two” etc.