probe::exc does not handle equivalent elements correctly

[Morwenn]

Despite an early attempt at making probe::exc handle values that compare equivalent (#143), and a more recent fix for the specific case where the first and elements of a cycle compare equivalent (#230), it appears that the measure of presortedness still does not fully handle them.

Case in point, once again courtesy of RapidCheck, though with manual reduction: we have probe::exc({1, 1, 1, 0, 0}) == 3 when the expected result is $Exc(\langle 1, 1, 1, 0, 0 \rangle) = 2$.

I still need to analyze that case in detail, but my guess is that we end up with two cycles:

• One that handles the lone $1$ in the middle.
• Another one that handles the four remaining values.

And that's not an incorrect way to make cycles, but the issue is that we need three cycles so that $|X| - N_{cycles}$ returns $2$. That means that we need to maximize the number of cycles in the face of equivalent elements. It remains to be checked, but believe that we find a $\langle 1, 0, 1, 0 \rangle$ cycle: we don't have to consecutive elements that compare equivalent, therefore we count a single cycle.

I need to find a way to either maximize the number of cycles, or to take into account such scenarios specifically.

[Morwenn]

I devised a heuristic that works for the case highlighted above, and that's guaranteed to continue working as it did before for distinct elements and elements that are already in their correct place. It works as follows:

1. For each cycle, create a "counter" map which maps elements to how many times they were seen in the current cycle (two elements $a$ and $b$ are considered equivalent when $\neg (a < b \lor a > b)$ by std::map).
2. Whenever an element of the cycle is different from the following previous element, add add $1$ to the count for that element. When two following elements compared equivalent, a cycle is added to the global count.
3. Add to the global count a number of cycles corresponding to the highest count in the map. For example if we have {a: 5, b: 1, c: 4}, we add $5$ cycles to the global count.

So far RapidCheck has been unable to craft a scenario that made this heuristic produce a failing test, though the test suite might not be robust enough in this area. In the time being it covers the scenario that led me to open this issue, and passes the non-regression tests for #143 and #230, which is a good start. I'm gonna keep this issue open a bit longer, and close it if no new problem arises.

[Morwenn]

Apparently the algorithm is not a good enough heuristic. I added a RapidCheck test to ensure that all measures of presortedness respect Mannila's third criterion (a subsequence contains no more disorder than the whole sequence), and it broke with the following inputs:

std::vector<int> const sequence =    {-13, 24, -26, 10, 19, 20, -17, 11, -30, 31, -13, -4};
std::vector<int> const subsequence = {-13, 24, -26, 10, 19, 20, -17, 11,      31, -13, -4};

With these inputs, probe::exc(sequence) returns 8 and probe::exc(subsequence) returns 9. The old implementation returns 9 for both, satisfying the property. I still need to analyze to understand what the result should be, and how to improve the algorithm.

[Morwenn]

That's gonna be a tough one: according to this Q&A, the problem is NP-hard: https://cs.stackexchange.com/q/119293/29312

The answer cites On the Cost of Interchange Rearrangement in Strings by Amir et al for that bound.

Given that result, I can't possibly provide an extension of $Exc$ that correctly handles equivalent elements, so I have to settle on an approximation when equivalent elements are present. The question is now: can I find an approximation that otherwise respects all the properties of a measure of presortedness?

Either way I need to review the new heuristic-based algorithm to check that it never underestimates the number of exchanges needed: I consider it acceptable to answer that 3 exchanges are needed when only 2 would be enough, but the opposite would not be acceptable.

If property tests keep failing after that, I might need to restrict them to collections of distinct elements.

[Morwenn]

Back to our two sequences:

std::vector<int> const sequence =    {-13, 24, -26, 10, 19, 20, -17, 11, -30, 31, -13, -4}; // size = 12
std::vector<int> const subsequence = {-13, 24, -26, 10, 19, 20, -17, 11,      31, -13, -4}; // size = 11

Running probe::exc on the original sequence gives the following cycles:

-13 -30 19 -13 24 -26 -17 10 -13
20 -4 31 20
11 11

Running it on the subsequence gives the following cycles:

-13 -26 -13
24 -17 11 19 -4 31 20 10 -13 24

The first and last elements of a sequence are repeated and that's normal. The difference between both can be explained by the fact that -13 appears in a single cycle in the original sequence, and thus contributes as two in this cycle. It appears in two cycles in the second sequence, which explains the difference.

In both cases it looks like 9 exchanges are required to sort the sequence, which means that the heuristic-based algorithm is just wrong. I'm gonna roll it back and check whether it is possible to handle a few additional cases with equivalent elements, notably the $\langle 1, 1, 1, 0, 0 \rangle$ that had me open this issue in the first place.

[Morwenn]

I rolled back the heuristic-based algorithm and we're back to the old conservative one, which correctly handles a few simple cases. I also mentioned the issue of the problem being NP-hard in the face of equivalent elements.

I don't plan to pursue this issue further, I'm closing the issue.