Partition representations: Difference between revisions

Jump to navigation Jump to search

Partition representations (view source)

Revision as of 14:38, 27 January 2020

6 bytes removed ,  14:38, 27 January 2020
m
half a dozen "partition" → "division" changes according to definition above although that on line 69 may be contentious
mNo edit summary
m (half a dozen "partition" → "division" changes according to definition above although that on line 69 may be contentious)
Line 30: Line 30:
== Representation using divider locations ==
== 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 partition whenever a 1 is encountered in the [[Boolean]] left argument:
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:
<source lang=apl>
<source lang=apl>
       1 0 1 1 0 0 1 ⊂ 'abcdefg'
       1 0 1 1 0 0 1 ⊂ 'abcdefg'
Line 39: Line 39:
{{Works in|[[Dyalog APL]]}}
{{Works in|[[Dyalog APL]]}}
This style of partition function is slightly harder to understand and implement, but does have advantages:
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 partition might be started whenever a space is encountered.
* The left argument can sometimes be obtained directly from the right argument. For example, a division might be started whenever a space is encountered.
* Left arguments can be merged using arithmetic. For two [[Partitioned Enclose]] arguments <source lang=apl inline>a</source> and <source lang=apl inline>b</source>, the [[Maximum]] <source lang=apl inline>a⌈b</source> 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 <source lang=apl inline>a</source> and <source lang=apl inline>b</source>, the [[Maximum]] <source lang=apl inline>a⌈b</source> gives a common [[wikipedia:Partition of a set#Refinement of partitions|refinement]] of the two corresponding partitions.


Line 53: Line 53:
└──┴────┴─┘
└──┴────┴─┘
</source>
</source>
A more rigorous approach is to allow the left argument to specify the [[index]] of the division to which the corresponding element belongs. In order for this to produce a partition, the left argument must be a vector of non-decreasing non-negative integers (as with the division endpoint representation). Then for a left argument <source lang=apl inline>l</source> the number of partitions is <source lang=apl inline>⊃⌽l</source>.
A more rigorous approach is to allow the left argument to specify the [[index]] of the division to which the corresponding element belongs. In order for this to produce a partition, the left argument must be a vector of non-decreasing non-negative integers (as with the division endpoint representation). Then for a left argument <source lang=apl inline>l</source> the number of divisions is <source lang=apl inline>⊃⌽l</source>.
<source lang=apl>
<source lang=apl>
       1 1 3 3 3 3 6 part 'abcdefg'
       1 1 3 3 3 3 6 part 'abcdefg'
Line 69: Line 69:
0 2 0 4 0 0 1
0 2 0 4 0 0 1
</source>
</source>
This conversion can be used to show that like the other two representations, target indices represent partitions bijectively. However, there is a concern regarding the final element, which is used to find the length of the division length vector above, that is, the number of divisions. If the target indices correspond exactly to the elements of the partitioned vector, then the last target index is the index of the last ''non-empty'' division. However, it is valid in a partition to include empty divisions at the end. In order to represent such divisions, we must allow an additional index after the last element of the partitioned vector.
This conversion can be used to show that like the other two representations, target indices represent divisions bijectively. However, there is a concern regarding the final element, which is used to find the length of the division length vector above, that is, the number of divisions. If the target indices correspond exactly to the elements of the partitioned vector, then the last target index is the index of the last ''non-empty'' division. However, it is valid in a partition to include empty divisions at the end. In order to represent such divisions, we must allow an additional index after the last element of the partitioned vector.


=== Divider counts ===
=== Divider counts ===
Line 82: Line 82:
└┴──┴┴────┴┴┴─┘
└┴──┴┴────┴┴┴─┘
</source>
</source>
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 partitions 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 partition, 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]] 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.


== Unification ==
== Unification ==
Phil Last
19

edits

Retrieved from ‘https://aplwiki.com/wiki/Special:MobileDiff/2565’

Navigation menu