P44: Enumeration of all optimal ladder lotteries

P44: Enumeration of all optimal ladder lotteries
Input:
A permutation.
Output:
All optimal ladder lotteries with satisfying the permutation.
Complexity:
$O(1)$ time per solution on average, $O(n^2)$ space, and $O(n^2)$ time preprocessing.
Comment:
$n$ is the length of the input permutation. We call a ladder lottery is an optimal when the number of horizontal lines in the ladder lottery is minimum. Ladder lotteries are also known as arrangements of pseudolines.
Reference:
[Yamanaka2010] (Bibtex)