Ryser's algorithm can be implemented in linear time
(Thank you to Joost Batenburg, who reminded me that the sorting preprocessing
can be done using bucket sort.)
It is not hard to see that Ryser's algorithm can in fact be implemented
in time O(n). First order decreasingly the
column sum vector c in time O(n) using bucket
sort. Then Ryser's algorithm places first rn pebbles
in row n, then rn-1 pebbles in row n-1
and so on. Each pebble is placed in the column with the largest remaining
sum, and if we have to choose between several columns with maximal remaining
sums, we choose the rightmost.
By doing so, we maintain the property that the columns are also ordered
in decreasing remaining sums. We claim that for every row there are
at most two disjoint column intervals, containing all the pebbles. Therefore
there is a compact representation of this canonical realization. If
the sums were initially not ordered, the representation contains a column
permutation in addition to the interval list.
Suppose we have columns a>b such that [1,a] have maximal
remaining sum, and [a+1,b] the second maximal remaining sum. Let
p be the number of pebbles to be placed in this row. Then if p<=a
the pebbles are in columns [a-p+1,a], if a<p<=b then
the pebbles are in the columns [1,a] union [b-p-a+1,b] and finally
if p>b then there is no realization.
Small Example
row sums: 13 12 11 11 11 10 10 10 10 10 10 9 9 8 6 6 5 5
column sums: 12 12 11 11 11 10 10 10 9 9 9 9 9 9 8 8 8 7 6 5
canonical realization:
Large example
row sums: 70 65 60 60 60 ...
column sums: 64 62 61 60 60 ...
canonical realization:
This
is how the examples were produced.