2,951
edits
Partition representations: Difference between revisions
Jump to navigation
Jump to search
Partition representations (view source)
Revision as of 14:47, 7 October 2020
, 14:47, 7 October 2020→Target indices: Add BQN link
m (→Target indices: Lists of target indices are in bijection with partitions, not divisions) |
(→Target indices: Add BQN link) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 3: | Line 3: | ||
== Definitions == | == Definitions == | ||
In this page, a '''partition''' of a [[vector]] is defined to be a [[nested]] or [[box]]ed vector containing vectors, such that the [[Raze]] (or equivalently <source lang=apl inline>{⊃⍪/⍵}</source> in [[Nested array model|nested]] APLs) of the partition intolerantly [[match]]es the original vector. A partition contains all the original [[element]]s of the vector, in the same order, but at one greater [[depth]]. | In this page, a '''partition''' of a [[vector]] is defined to be a non-[[empty]] [[nested]] or [[box]]ed vector containing vectors, such that the [[Raze]] (or equivalently <source lang=apl inline>{⊃⍪/⍵}</source> in [[Nested array model|nested]] APLs) of the partition intolerantly [[match]]es the original vector. A partition contains all the original [[element]]s of the vector, in the same order, but at one greater [[depth]]. | ||
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. | 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. | ||
| 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 divisions 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>. BQN's [[Group (BQN)|Group]] uses an extension of this representation. | ||
<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 116: | Line 116: | ||
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: | 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: | ||
<source lang=apl> | <source lang=apl> | ||
⎕←P | |||
┌┬──┬┬────┬┬┬─┐ | ┌┬──┬┬────┬┬┬─┐ | ||
││ab││cdef│││g│ | ││ab││cdef│││g│ | ||
| Line 145: | Line 145: | ||
</source> | </source> | ||
In the above functions, the only difference in code is exchanging 0 and 1, and the only difference in output is an extra trailing 0 when computed from the division lengths. The mesh representation makes the partition representation duality especially clear, as the dual representation can be obtained simply by [[Not|negating]] the mesh vector. | In the above functions, the only difference in code is exchanging 0 and 1, and the only difference in output is an extra trailing 0 when computed from the division lengths. The mesh representation makes the partition representation duality especially clear, as the dual representation can be obtained simply by [[Not|negating]] the mesh vector. | ||
[[Category:Essays]] | |||