Partition representations: Difference between revisions

Jump to navigation Jump to search

Partition representations (view source)

Revision as of 16:19, 30 December 2023

77 bytes removed ,  16:19, 30 December 2023
→‎Representation using divider locations: Non-boolean Partitioned Enclose is now common (Dyalog, April, KAP, dzaima/APL)
m (Text replacement - "<source" to "<syntaxhighlight")
(→‎Representation using divider locations: Non-boolean Partitioned Enclose is now common (Dyalog, April, KAP, dzaima/APL))
 
Line 42: Line 42:
* Left arguments can be merged using arithmetic. For two [[Partitioned Enclose]] arguments <syntaxhighlight lang=apl inline>a</syntaxhighlight> and <syntaxhighlight lang=apl inline>b</syntaxhighlight>, the [[Maximum]] <syntaxhighlight lang=apl inline>a⌈b</syntaxhighlight> gives a common [[wikipedia:Partition of a set#Refinement of partitions|refinement]] of the two corresponding partitions.
* Left arguments can be merged using arithmetic. For two [[Partitioned Enclose]] arguments <syntaxhighlight lang=apl inline>a</syntaxhighlight> and <syntaxhighlight lang=apl inline>b</syntaxhighlight>, the [[Maximum]] <syntaxhighlight lang=apl inline>a⌈b</syntaxhighlight> gives a common [[wikipedia:Partition of a set#Refinement of partitions|refinement]] of the two corresponding partitions.


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.
A shortcoming of [[Partition]], and [[Partitioned Enclose]] in some dialects, 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. [[Dyalog APL 18.0|Dyalog 18.0]] extends the domain of Partitioned Enclose from [[Boolean]] vectors to vectors of non-negative integers, so that the only further change we'll need to make is an offset of one for the first element. [[Partition]] requires more significant changes and couldn't be [[backwards compatible]] with APL definitions.


=== Target indices ===
=== Target indices ===
Line 84: Line 84:
As with the Partition-based representation, we must allow an additional element in the left argument after the end of the right argument in order to encode empty divisions after the end of the data.
As with the Partition-based representation, we must allow an additional element in the left argument after the end of the right argument in order to encode empty divisions after the end of the data.


This definition is nearly identical to the one used in [[Partitioned Enclose]] when the divider counts are [[Boolean]]. The only difference is in the first element: while in Partitioned Enclose a first element of 0 indicates that no division is started, and elements before the first 1 are excluded from the final division, in the version here, a first element of 0 is like a 1 in Partitioned Enclose indicating that a division is started, while an initial 1 indicates that an empty division precedes the first non-empty division. The number used in the representation here is one higher than the one used by Partitioned Enclose. This encoding better represents complete partitions of the right argument because every vector on non-negative integers corresponds to a partition. In Partitioned Enclose vectors beginning with 0 correspond to incomplete partitions where some initial elements are not included. However, the partitioning used in Partitioned Enclose can still be produced by [[drop]]ping the first division.
This definition is nearly identical to the one used in [[Partitioned Enclose]]. The only difference is an offset of 1 in the first element: while in Partitioned Enclose a first element of 0 indicates that no division is started, and elements before the first 1 are excluded from the final division, in the version here, a first element of 0 is like a 1 in Partitioned Enclose indicating that a division is started, while an initial 1 indicates that an empty division precedes the first non-empty division. This encoding better represents complete partitions of the right argument because every vector on non-negative integers corresponds to a partition. In Partitioned Enclose vectors beginning with 0 correspond to incomplete partitions where some initial elements are not included. However, the partitioning used in Partitioned Enclose can still be produced by [[drop]]ping the first division.


== Unification ==
== Unification ==
Retrieved from ‘https://aplwiki.com/wiki/Special:MobileDiff/10614’

Navigation menu