Partition representations: Difference between revisions

== Definitions ==

The vectors contained in a partition are called '''divisions''', and the boundaries between them are called '''dividers'''. Although the English word "partition" can be used for either of these, the ambiguity of using one word for three different objects could be confusing. Only boundaries between divisions are called dividers: we do not name the two outermost edges, which must exist in any partition.

== Representation using division lengths ==

       l ← 2 0 3 3

       X ← 'abcdefgh'

{{Works in|[[Dyalog APL]]}}

== Representation using divider locations ==

Existing APLs rarely define partitioning functions using properties of the resulting divisions. Instead, most partition functions use a vector of the same length as the partitioned vector to control how it is partitioned. For example, [[Partitioned Enclose]] starts a new division whenever a 1 is encountered in the [[Boolean]] left argument:

       1 0 1 1 0 0 1 ⊂ 'abcdefg'

┌──┬─┬───┬─┐

This style of partition function is slightly harder to understand and implement, but does have advantages:

* The left argument can sometimes be obtained directly from the right argument. For example, a division might be started whenever a space is encountered.

A shortcoming of existing [[Partition]] and [[Partitioned Enclose]] is that they do not allow empty divisions to be produced. While the length representation makes empty divisions easy to represent, and the obvious implementation produces them with no trouble, it is less obvious how empty divisions should be represented in APL-style partitions. However, each can be modified to obtain a representation which is complete and one-to-one. In the case of Partitioned Enclose the modification is mostly [[backwards compatible]]: it extends the domain from [[Boolean]] vectors to vectors of non-negative integers, and the only incompatibility between our definition and the existing APL definition will be an offset of one for the first element.

First, we give a representation related to the one used in Partition. Recall that Partition starts a new division whenever values in its left argument increase (similar to [[Key]], except that it cares about whether values are adjacent):

       1 1 3 3 3 3 6 ⊆ 'abcdefg'

┌──┬────┬─┐

└──┴────┴─┘

</syntaxhighlight>

       1 1 3 3 3 3 6 part 'abcdefg'

┌┬──┬┬────┬┬┬─┐

└┴──┴┴────┴┴┴─┘

</syntaxhighlight>

Target indices can be converted to division endpoints using [[Interval Index]], and then to division lengths with a pair-wise difference:

       {1+⍵⍸⍳1+⊃⌽⍵}1 1 3 3 3 3 6

0 2 2 6 6 6 7

The target index of an element is the same as the number of dividers which fall before it. Motivated by this fact, we might use the pair-wise differences of the target indices as another partition representation. Taking differences converts the total number of dividers before each element to the number of dividers immediately preceding it. For example, the vector below encodes the same partition as that shown in the previous section.

       ¯2-/0,1 1 3 3 3 3 6

1 0 2 0 0 0 3

Because it interleaves elements from a vector with dividers, partitioning is closely related to the [[Mesh]] operation. In fact, a partition can be used to produce a mesh by prepending an element to each division and [[Raze]]ing:

       ⎕←P

┌┬──┬┬────┬┬┬─┐

ABabCDcdefEFGg

</syntaxhighlight>

A partition can also be extracted from the mesh using the [[Cut]] operator and the mesh vector. In [[J]]:

   (-.0 0 1 1 0 0 1 1 1 1 0 0 0 1) <;._1 'ABabCDcdefEFGg'

┌┬──┬┬────┬┬┬─┐

</syntaxhighlight>

{{Works in|[[J]]}}

The [[Boolean]] control vector used by Mesh serves as another way to represent partitions. Unlike the case with [[Partitioned Enclose]], a Boolean vector here is sufficient to represent any partition including those with empty divisions. This is possible because of the vector's increased length: while Partitioned Enclose uses only one Boolean for each element in the partitioned vector, the mesh vector has a 1 for each element in the partitioned vector as well as a 0 for each divider.

The mesh vector can be obtained from the other representations. In the diagram above, it contains a 1 for each horizontal line segment in the target indices graph, and a 0 for each vertical one. The directions are reversed for division endpoints.

       {⍵/0 1⍴⍨≢⍵},1,⍤0⍨ 0 0 0 2 1 0  ⍝ From divider counts

1 1 1 0 0 1 0 1 1

Conversion from index-based representations is less obvious but more efficient, and also easily invertible. These representations index into either elements or dividers, but can be converted to index into the mesh vector, which combines both, by adding one for each previous index. These adjusted indices give the locations of all ones, or all zeros, in the mesh vector, depending on the initial representation.

       ⍸⍣¯1{⍵+⍳≢⍵} 0 0 0 2 3 3  ⍝ From target indices

1 1 1 0 0 1 0 1 1