Partition - Maple Help

ArrayTools

 Partition
 partially sort an rtable around a given order statistic

 Calling Sequence Partition(A, k) Partition(A, k, ord, opts)

Parameters

 A - rectangular storage Vector or 1-D Array with no indexing functions, or a list k - integer, or list of integers ord - (optional) comparison function opts - (optional) keyword option(s) of the form opt = value, where opt is one of inplace, bounds, or testreflexive

Description

 • 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, $-1$ represents the last entry of A, $-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.

Examples

The implementation of this command uses functionality that depends on your operating system, so if you run these examples on your computer, the results may differ in minor ways from what you see in the help page. For example, the results may in some cases be fully sorted. That won't always happen for longer inputs, though.

 > $\mathrm{with}\left(\mathrm{ArrayTools}\right):$
 > $v≔\left[5,2,5,2,3,4,4,5,3,1,5,2,3,2,2,4,3,3,1,2\right]$
 ${v}{≔}\left[{5}{,}{2}{,}{5}{,}{2}{,}{3}{,}{4}{,}{4}{,}{5}{,}{3}{,}{1}{,}{5}{,}{2}{,}{3}{,}{2}{,}{2}{,}{4}{,}{3}{,}{3}{,}{1}{,}{2}\right]$ (1)

To find the third-smallest entry of $v$, we can use Partition.

 > $w≔\mathrm{Partition}\left(v,3\right)$
 ${w}{≔}\left[{1}{,}{1}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{5}{,}{3}{,}{4}{,}{5}{,}{4}{,}{3}{,}{3}{,}{2}{,}{4}{,}{3}{,}{3}{,}{5}{,}{5}\right]$ (2)
 > $w\left[3\right]$
 ${2}$ (3)

We see that ${w}_{3}=2$, so the third-smallest entry of $v$ is 2.

We can find the fourth-largest entry of $v$ by having Partition partition around the fourth entry from the end of $v$.

 > $w≔\mathrm{Partition}\left(v,-4\right)$
 ${w}{≔}\left[{2}{,}{2}{,}{1}{,}{2}{,}{2}{,}{2}{,}{1}{,}{3}{,}{3}{,}{3}{,}{2}{,}{3}{,}{4}{,}{3}{,}{4}{,}{4}{,}{5}{,}{5}{,}{5}{,}{5}\right]$ (4)
 > $w\left[-4\right]$
 ${5}$ (5)

Alternatively, we can partition around the fourth entry of $v$ in descending order.

 > $w≔\mathrm{Partition}\left(v,4,\mathrm{>}\right)$
 ${w}{≔}\left[{5}{,}{5}{,}{5}{,}{5}{,}{4}{,}{4}{,}{3}{,}{4}{,}{3}{,}{3}{,}{2}{,}{3}{,}{3}{,}{2}{,}{2}{,}{2}{,}{1}{,}{2}{,}{1}{,}{2}\right]$ (6)
 > $w\left[4\right]$
 ${5}$ (7)

If we want to know both the third-smallest and the fourth-largest entries of $v$, we can call Partition with a list value for the k parameter.

 > $w≔\mathrm{Partition}\left(v,\left[3,-4\right]\right)$
 ${w}{≔}\left[{1}{,}{1}{,}{2}{,}{2}{,}{2}{,}{3}{,}{2}{,}{3}{,}{2}{,}{3}{,}{2}{,}{3}{,}{4}{,}{3}{,}{4}{,}{4}{,}{5}{,}{5}{,}{5}{,}{5}\right]$ (8)
 > $w\left[3\right]$
 ${2}$ (9)
 > $w\left[-4\right]$
 ${5}$ (10)

Alternatively, we can first fix the third-smallest entry and then use the bounds option to partition the rest of $v$.

 > $w≔\mathrm{Partition}\left(v,3\right)$
 ${w}{≔}\left[{1}{,}{1}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{5}{,}{3}{,}{4}{,}{5}{,}{4}{,}{3}{,}{3}{,}{2}{,}{4}{,}{3}{,}{3}{,}{5}{,}{5}\right]$ (11)
 > $w\left[3\right]$
 ${2}$ (12)
 > $u≔\mathrm{Partition}\left(w,-4,\mathrm{bounds}=4..\right)$
 ${u}{≔}\left[{4}{,}{2}{,}{2}{,}{2}{,}{3}{,}{3}{,}{3}{,}{4}{,}{2}{,}{3}{,}{3}{,}{2}{,}{4}{,}{5}{,}{5}{,}{5}{,}{5}\right]$ (13)
 > $u\left[-4\right]$
 ${5}$ (14)

As another alternative, if $v$ is an rtable, we can do both of these manipulations in-place.

 > $v≔\mathrm{Vector}\left(v\right)$
 ${v}{≔}\begin{array}{c}\left[\begin{array}{c}{5}\\ {2}\\ {5}\\ {2}\\ {3}\\ {4}\\ {4}\\ {5}\\ {3}\\ {1}\\ {⋮}\end{array}\right]\\ \hfill {\text{20 element Vector[column]}}\end{array}$ (15)
 > $\mathrm{Partition}\left(v,3,\mathrm{inplace}\right):$
 > $\mathrm{Partition}\left(v,-4,\mathrm{bounds}=4..,\mathrm{inplace}\right):$
 > $\mathrm{convert}\left(v,\mathrm{list}\right)$
 $\left[{1}{,}{1}{,}{2}{,}{4}{,}{2}{,}{2}{,}{2}{,}{3}{,}{3}{,}{3}{,}{4}{,}{2}{,}{3}{,}{3}{,}{2}{,}{4}{,}{5}{,}{5}{,}{5}{,}{5}\right]$ (16)
 > $v\left[3\right]$
 ${2}$ (17)
 > $v\left[-4\right]$
 ${5}$ (18)

Compatibility

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