2,954
edits
Partition representations: Difference between revisions
Jump to navigation
Jump to search
Partition representations (view source)
Revision as of 16:36, 6 January 2020
, 16:36, 6 January 2020Add Cut (K)
(Add Cut (K)) |
|||
| Line 1: | Line 1: | ||
[[Partition]], [[Partitioned Enclose]], | [[Partition]], [[Partitioned Enclose]], the [[Cut]] operator, and [[Cut (K)]] all allow a programmer to split a [[vector]] into differently sized pieces. The left [[argument]] to these operations defines the structure of the partition. This page discusses possible ways partitions can be represented. | ||
This page uses [[index origin]] 0. | This page uses [[index origin]] 0. | ||
| Line 26: | Line 26: | ||
{{Works in|[[Dyalog APL]]}} | {{Works in|[[Dyalog APL]]}} | ||
The division endpoints are another way to represent partitions. The endpoints <source lang=apl inline>+\l</source> computed above form a non-decreasing vector of non-negative integers whose last element is equal to the length of the partitioned vector. It would also be possible to use the partition starting points <source lang=apl inline>+\¯1↓0,l</source>; here we use only endpoints for consistency. | The division endpoints are another way to represent partitions. The endpoints <source lang=apl inline>+\l</source> computed above form a non-decreasing vector of non-negative integers whose last element is equal to the length of the partitioned vector. It would also be possible to use the partition starting points <source lang=apl inline>+\¯1↓0,l</source>; here we use only endpoints for consistency. The latter representation matches [[K]]'s [[Cut (K)|Cut]] function, which produces a complete partition exactly when the left argument contains a zero (otherwise, some initial elements are omitted). | ||
Vectors of division endpoints correspond exactly to vectors of division lengths, because the [[Windowed Reduce|windowed]] [[difference]] <source lang=apl inline>¯2-/0,e</source> is an exact [[inverse]] of Plus Scan which obtains division lengths <source lang=apl inline>l</source> from endpoints <source lang=apl inline>e</source>. | Vectors of division endpoints correspond exactly to vectors of division lengths, because the [[Windowed Reduce|windowed]] [[difference]] <source lang=apl inline>¯2-/0,e</source> is an exact [[inverse]] of Plus Scan which obtains division lengths <source lang=apl inline>l</source> from endpoints <source lang=apl inline>e</source>. | ||
| Line 98: | Line 98: | ||
The partitioning mechanisms shown above can be grouped in categories in several ways. The left and right halves of the diagram each contain vectors of the same length. This is because the vectors have the same domain: on the left, a value is given for each element to be partitioned, while on the right a value is given for each division or divider. The top and bottom halves also share common properties: representations on the top specify where elements should be placed (using either dense indices giving a position for each element or sparse indices giving how many elements go in each slot) while those on the bottom specify where dividers should be placed in the same sense. | The partitioning mechanisms shown above can be grouped in categories in several ways. The left and right halves of the diagram each contain vectors of the same length. This is because the vectors have the same domain: on the left, a value is given for each element to be partitioned, while on the right a value is given for each division or divider. The top and bottom halves also share common properties: representations on the top specify where elements should be placed (using either dense indices giving a position for each element or sparse indices giving how many elements go in each slot) while those on the bottom specify where dividers should be placed in the same sense. | ||
{|class=wikitable style="margin: 1em auto 1em auto" | {|class=wikitable style="margin: 1em auto 1em auto; text-align:center" | ||
|colspan=2 rowspan=2| | |colspan=2 rowspan=2| | ||
!colspan=2| Domain | !colspan=2| Domain | ||
| Line 106: | Line 106: | ||
!rowspan=2|Positions | !rowspan=2|Positions | ||
! Elements | ! Elements | ||
| Target indices || Division lengths | | Target indices<br/>([[Partition]]) || Division lengths | ||
|- | |- | ||
! Dividers | ! Dividers | ||
| Divider counts || Division endpoints | | Divider counts<br/>([[Partitioned Enclose]]) || Division endpoints<br/>([[Cut (K)]]) | ||
|} | |} | ||