2,951
edits
Partition representations: Difference between revisions
Jump to navigation
Jump to search
Partition representations (view source)
Revision as of 21:44, 13 December 2019
, 21:44, 13 December 2019no edit summary
(Created page with "Partition, Partitioned Enclose, and the Cut operator all allow a programmer to split a vector into differently sized pieces. The left argument to these ope...") |
No edit summary |
||
| Line 111: | Line 111: | ||
| Divider counts || Division endpoints | | Divider counts || Division endpoints | ||
|} | |} | ||
== Mesh representation == | |||
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> | |||
⊢P | |||
┌┬──┬┬────┬┬┬─┐ | |||
││ab││cdef│││g│ | |||
└┴──┴┴────┴┴┴─┘ | |||
⊃⍪/ 'ABCDEFG' ,¨ P | |||
ABabCDcdefEFGg | |||
</source> | |||
The above vector is identical to the mesh of <source lang=apl inline>'ABCDEFG'</source> with <source lang=apl inline>'abcdefg'</source> using mesh vector <source lang=apl inline>0 0 1 1 0 0 1 1 1 1 0 0 0 1</source>. | |||
A partition can also be extracted from the mesh using the [[Cut]] operator and the mesh vector. In [[J]]: | |||
<source lang=j> | |||
(-.0 0 1 1 0 0 1 1 1 1 0 0 0 1) <;._1 'ABabCDcdefEFGg' | |||
┌┬──┬┬────┬┬┬─┐ | |||
││ab││cdef│││g│ | |||
└┴──┴┴────┴┴┴─┘ | |||
</source> | |||
{{Works in|[[J]]}} | |||
Here <source lang=j inline>-.</source> is [[Negate]], <source lang=j inline><</source> is [[Box]], and <source lang=j inline>;._1</source> uses the Cut operator <source lang=j inline>;.</source> with dropped initial elements. | |||
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. | |||
<source lang=apl> | |||
{⍵/0 1⍴⍨≢⍵},1,⍤0⍨ 0 0 0 2 1 0 ⍝ From divider counts | |||
1 1 1 0 0 1 0 1 1 | |||
{⍵/1 0⍴⍨≢⍵},1,⍤0⍨ 3 0 1 2 ⍝ From division lengths | |||
1 1 1 0 0 1 0 1 1 0 | |||
</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 [[Negate|negating]] the mesh vector. | |||