Uniform random generation of decomposable structures using floating-point arithmetic

The recursive method formalized by Nijenhuis and Wilf (1998) and systematiz ed by Flajolet, Van Cutsem and Zimmermann (1994), is extended here to float ing-point arithmetic. The resulting ADZ method enables one to generate deco mposable data structures - both labelled or unlabelled - uniformly at rando m, in expected O(n(1+epsilon)) time and space, after a preprocessing phase of O(n(2+epsilon)) time, which reduces to O(n(1+epsilon)) for context-free grammars. (C) 1999 Elsevier Science B.V. All rights reserved.