  In plenty of data analysis tasks, a basic and time-consuming process is to
produce a large number of solutions and feed them into downstream processing.
Various enumeration algorithms have been developed for this purpose. An
enumeration algorithm produces all solutions of a problem instance without
repetition. To be a statistically meaningful representation of the solution
space, solutions are required to be enumerated in uniformly random order. This
paper studies a set of self-reducible NP-problems in three hierarchies, where
the problems are polynomially countable ($Sr_{NP}^{FP}$), admit FPTAS
($Sr_{NP}^{FPTAS}$), and admit FPRAS ($Sr_{NP}^{FPRAS}$), respectively. The
trivial algorithm based on a (almost) uniform generator is in fact inefficient.
We provide a new insight that the (almost) uniform generator is not the end of
the story. More efficient algorithmic frameworks are proposed to enumerate
solutions in uniformly random order for problems in these three hierarchies.
(1) For problems in $Sr_{NP}^{FP}$, we show a random-order enumeration
algorithm with polynomial delay (PDREnum); (2) For problems in
$Sr_{NP}^{FPTAS}$, we show a Las Vegas random-order enumeration algorithm with
expected polynomial delay (PDLVREnum); (3) For problems in $Sr_{NP}^{FPRAS}$,
we devise a fully polynomial delay Atlantic City random-order enumeration
algorithm with expected delay polynomial in the input size and the given error
probability $\delta$ (FPACREnum), which has a probability of at least
$1-\delta$ becoming a Las Vegas random-order enumeration algorithm. Finally, to
further improve the efficiency of the random-order enumeration algorithms,
based on the master/slave paradigm, we present a parallelization with
1.5-optimal enumeration delay and running time, along with the theoretical
analysis.
