Skip to content

Partitioning [mp]

Micro pattern

Description

Divide input into regions or pieces satisfying distinct ordering or validity properties.

Problems

Three-way value partitioning

Maintain regions smaller than, equal to, and greater than a category.

Partition into valid pieces

Choose a valid next segment and solve the remaining suffix.

Partition into adjacent runs

Cut a sequence into sorted runs for pairwise merging.

Balanced sorted partitions

Choose cuts whose combined left side has a desired rank.

Interval splits

Select a position separating an interval into independent subintervals.