Paul Zimmermann, University of Paderborn and {\sc Inria}-Lorraine

Uniform random generation for the powerset construction

An algorithm for the uniform random generation of the powerset construction is presented, completing the calculus developed in previous works with Flajolet and van Cutsem. Given a combinatorial class $I$, known by a counting procedure and an unranking procedure (or simply a random generation procedure), this algorithm provides similar procedures for $P=\hbox{powerset}(I)$. For most combinatorial structures, each random powerset of size $n$ is produced in $O(n \log n)$ arithmetic operations in the worst case, after $O(n^2)$ coefficients have been computed.