The Partition command reorders the n entries of a Vector, Array, or list, A, so that the first k - 1 entries are less than or equal to the kth entry, and the kth entry is less than or equal to the last n - k entries.

This can often be done more quickly than fully sorting A, especially if A has many entries. In particular, the Partition command has linear time complexity in the number of entries of A. (Full sorting can be done with the sort command.)

If k is negative, this is understood as counting from the end of A (unless the lowerbound of A is different from 1). That is, $\mathrm{-1}$ represents the last entry of A, $\mathrm{-2}$ represents the next-to-last entry, and so on.

The parameter k can also be passed as a list, say k = [k1, k2, ..., km]. The order of entries in k does not matter, but it is easiest to explain what happens if they are in ascending order. In this case, the Partition command reorders A so that:

the entries that occur before position k1 are less than or equal to A[k1],

the entries that occur between positions k1 and k2 are between A[k1] and A[k2] in magnitude,

the entries that occur between positions k2 and k3 are between A[k2] and A[k3] in magnitude, and so on, and

the entries that occur after position km are greater than or equal to A[km].

By default, the comparison function is <, the built-in less-than operator. A different comparison function (ordering predicate) can be specified as the third argument. For technical reasons, this should be the strict (non-reflexive) comparison version of this predicate. For example, if a procedure ord is specified, and k is a single integer, then A is reordered so that ord(A[k], A[i]) returns false for i < k, and ord(A[j], A[k]) returns false for k < j. This predicate should be transitive; that is, if ord(x, y) and ord(y, z) return true, then ord(x, z) should return true.

By default, the Partition command returns a permuted copy of A. If the option inplace = true is specified and A is a Vector or Array, then A is modified in-place. This option can also be specified with just the keyword inplace.

By default, the Partition command applies the reordering to all of A. If the option bounds = a .. b is specified, then the reordering is applied to the positions a to b of A, inclusive, and only the reordered entries are returned. Negative values for a and b count from the end rather than the beginning. The left hand bound, a, can be omitted, which will be interpreted as starting from the start (a = 1); the right hand bound, b, can also be omitted, which will be interpreted as ending at the end (b = -1). The options inplace and bounds can be combined to reorder only some of As entries in-place.

By default, if an ordering predicate ord is specified (and A is not empty), then the Partition command does a rudimentary test of its reflexivity: it tests that ord(A[1], A[1]) returns false. If this is not true, an error is raised. The option testreflexive = false turns off this test. This can lead to unexpected results if the predicate is not reflexive.

$\mathrm{with}\left(\mathrm{ArrayTools}\right)\&colon;$

$v≔\left[5\&comma;2\&comma;5\&comma;2\&comma;3\&comma;4\&comma;4\&comma;5\&comma;3\&comma;1\&comma;5\&comma;2\&comma;3\&comma;2\&comma;2\&comma;4\&comma;3\&comma;3\&comma;1\&comma;2\right]$

$v≔\left[5\&comma;2\&comma;5\&comma;2\&comma;3\&comma;4\&comma;4\&comma;5\&comma;3\&comma;1\&comma;5\&comma;2\&comma;3\&comma;2\&comma;2\&comma;4\&comma;3\&comma;3\&comma;1\&comma;2\right]$

$w≔\mathrm{Partition}\left(v\&comma;3\right)$

$w≔\left[1\&comma;1\&comma;2\&comma;2\&comma;2\&comma;2\&comma;2\&comma;5\&comma;3\&comma;4\&comma;5\&comma;4\&comma;3\&comma;3\&comma;2\&comma;4\&comma;3\&comma;3\&comma;5\&comma;5\right]$

$w\left[3\right]$

$2$

$w≔\mathrm{Partition}\left(v\&comma;-4\right)$

$w≔\left[2\&comma;2\&comma;1\&comma;2\&comma;2\&comma;2\&comma;1\&comma;3\&comma;3\&comma;3\&comma;2\&comma;3\&comma;4\&comma;3\&comma;4\&comma;4\&comma;5\&comma;5\&comma;5\&comma;5\right]$

$w\left[-4\right]$

$5$

$w≔\mathrm{Partition}\left(v\&comma;4\&comma;\mathrm{`>`}\right)$

$w≔\left[5\&comma;5\&comma;5\&comma;5\&comma;4\&comma;4\&comma;3\&comma;4\&comma;3\&comma;3\&comma;2\&comma;3\&comma;3\&comma;2\&comma;2\&comma;2\&comma;1\&comma;2\&comma;1\&comma;2\right]$

$w\left[4\right]$

$5$

$w≔\mathrm{Partition}\left(v\&comma;\left[3\&comma;-4\right]\right)$

$w≔\left[1\&comma;1\&comma;2\&comma;2\&comma;2\&comma;3\&comma;2\&comma;3\&comma;2\&comma;3\&comma;2\&comma;3\&comma;4\&comma;3\&comma;4\&comma;4\&comma;5\&comma;5\&comma;5\&comma;5\right]$

$w\left[3\right]$

$2$

$w\left[-4\right]$

$5$

$w≔\mathrm{Partition}\left(v\&comma;3\right)$

$w≔\left[1\&comma;1\&comma;2\&comma;2\&comma;2\&comma;2\&comma;2\&comma;5\&comma;3\&comma;4\&comma;5\&comma;4\&comma;3\&comma;3\&comma;2\&comma;4\&comma;3\&comma;3\&comma;5\&comma;5\right]$

$w\left[3\right]$

$2$

$u≔\mathrm{Partition}\left(w\&comma;-4\&comma;\mathrm{bounds}=4..\right)$

$u≔\left[4\&comma;2\&comma;2\&comma;2\&comma;3\&comma;3\&comma;3\&comma;4\&comma;2\&comma;3\&comma;3\&comma;2\&comma;4\&comma;5\&comma;5\&comma;5\&comma;5\right]$

$u\left[-4\right]$

$5$

$v≔\mathrm{Vector}\left(v\right)$

$\mathrm{Partition}\left(v\&comma;3\&comma;\mathrm{inplace}\right)\&colon;$

$\mathrm{Partition}\left(v\&comma;-4\&comma;\mathrm{bounds}=4..\&comma;\mathrm{inplace}\right)\&colon;$

$\mathrm{convert}\left(v\&comma;\mathrm{list}\right)$

$\left[1\&comma;1\&comma;2\&comma;4\&comma;2\&comma;2\&comma;2\&comma;3\&comma;3\&comma;3\&comma;4\&comma;2\&comma;3\&comma;3\&comma;2\&comma;4\&comma;5\&comma;5\&comma;5\&comma;5\right]$

$v\left[3\right]$

$2$

$v\left[-4\right]$

$5$

The ArrayTools[Partition] command was introduced in Maple 2019.

For more information on Maple 2019 changes, see Updates in Maple 2019.