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)