Broken relations between measures of presortedness

I decided to upgrade the probes/relations.cpp test with RapidCheck as an experiment, because property-based testing felt like the proper tool for that job. Unfortunately it was a bit too quick to find issues:

          Start  459: relations between measures of presortedness
 459/1252 Test  #459: relations between measures of presortedness ............................................................................................................***Failed    0.25 sec
Filters: "relations between measures of presortedness"
Randomness seeded to: 373856
Using configuration: seed=1750367150

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main-tests.exe is a Catch2 v3.8.1 host application.
Run with -? for options

-------------------------------------------------------------------------------
relations between measures of presortedness
  Exc(X) + 1 ≤ Ham(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................

D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
  Falsifiable after 1 tests

std::tuple<std::vector<int>>:
  ([])

Returned false

-------------------------------------------------------------------------------
relations between measures of presortedness
  2 sqrt(Enc(X)) + 1 ≤ Inv(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................

D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
  Falsifiable after 1 tests

std::tuple<std::vector<int>>:
  ([])

Returned false

-------------------------------------------------------------------------------
relations between measures of presortedness
  2 Enc(X) ≤ Exc(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................

D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
  Falsifiable after 6 tests and 1 shrink

std::tuple<std::vector<int>>:
  ([-2, 0, -1])

Returned false

-------------------------------------------------------------------------------
relations between measures of presortedness
  Inv(X) + Exc(X) ≤ Spear(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................

D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
  Falsifiable after 9 tests and 2 shrinks

std::tuple<std::vector<int>>:
  ([-1, -1, -2])

Returned false

===============================================================================
test cases:  1 |  0 passed | 1 failed
assertions: 26 | 22 passed | 4 failed

That's quite a few failing relations to analyze and fix:

  • Exc(X) + 1 ≤ Ham(X) with an empty sequence
  • 2 sqrt(Enc(X)) + 1 ≤ Inv(X) with an empty sequence
  • 2 Enc(X) ≤ Exc(X) with sequence (-2, 0, 1)
  • Inv(X) + Exc(X) ≤ Spear(X) with sequence (-1, -1, -2)