4
$\begingroup$

I am having a bit of brain fail and I can't remeber the name of the following problem (so I can find some literature around it...).

Given a sequence of values, sort it in a way that equal elements are compacted in runs (contiguous subsequences of identical elements).

For instance:

$$ \{1, 2, 4, 2, 1, 3\} \rightarrow \{ 2, 2, 4, 3, 1, 1 \} $$

The runs are not otherwise sorted -- only equality comparison is required, not ordering; and they're compacted (there should not be two different runs containing equal elements).

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ What about "counting"? $\endgroup$
    – Raphael ♦
    Jul 31, 2015 at 15:55
  • $\begingroup$ Why isn't the sorted array $\{1,1,4,2,2,3\}$? If the elements are not sorted the basic logic will be to check for the current element and swap all elements which are identical to it. $\endgroup$
    – Sagnik
    Jul 31, 2015 at 17:06
  • $\begingroup$ @Raphael: it's not exactly counting -- elements in the same run can be different by other means; for instance, a sequence of "employees" arranged in runs by "year of birth". $\endgroup$
    – peppe
    Jul 31, 2015 at 18:43
  • $\begingroup$ @Sagnik: sure, sorting would lead to a solution, however it requires an ordering (which is not necessary in the formulation of the problem above), and might possibly be less efficient... $\endgroup$
    – peppe
    Jul 31, 2015 at 18:45
  • $\begingroup$ In distributed environments data is typically partitioned by a hash so that identical keys are stored on the same node; is that the type of situation you're thinking of? In that case the runs are on different nodes. The map phase in map-reduce is similar. $\endgroup$
    – KWillets
    Jul 31, 2015 at 19:39

1 Answer 1

Reset to default
1
$\begingroup$

Gopan et al. seem to define a more general problem and call it array partitioning [1].

The goals of array partitioning are twofold. First, we would like to isolate in separate groups [...] we partition an array so that each element whose index is equal to the value of any of the vari ables in the set is placed in a group by itself. [...]

[W]e partition each array $A \in Array$ by grouping together elements of $A$ for which all partitioning functions in $\Pi_A$ evaluate to the same values.

I have not dug into how their formal framework captures your problem and it may not even do so. Still, I think the general idea is close enough to use the word.

Come to think of it, Quicksort-style partitioning is related as well: you want to partition w.r.t. identify, in Quicksort we partition w.r.t. equivalence classes induced by some pivots.

  1. A framework for numeric analysis of array operations by D. Gopan, T. Reps and M. Sagiv (2005) [preprint]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.