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.