Uniform Random Generation of Decomposable Structures Using Floating-Point Arithmetic (original) (raw)

Rapport (Rapport De Recherche) Année : 1997

Résumé

The {\em recursive method\/} formalized by Nijenhuis and Wilf \cite{NiWi78} and systematized by Flajolet, Van Cutsem and Zimmermann \cite{FlZiVa94}, is extended here to floating-point arithmetic. The resulting ADZ method enables one to generate decomposable data structures --- both labelled or unlabelled --- uniformly at random, in expected O(n1+epsilon)O(n^{1+\epsilon})O(n1+epsilon) time and space, after a preprocessing phase of O(n2+epsilon)O(n^{2+\epsilon})O(n2+epsilon) time, which reduces to O(n1+epsilon)O(n^{1+\epsilon})O(n1+epsilon) for context-free grammars.

Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00073447

Soumis le : mercredi 24 mai 2006-12:49:58

Dernière modification le : samedi 7 février 2026-05:07:25

Archivage à long terme le : dimanche 4 avril 2010-23:46:50

Dates et versions

inria-00073447 , version 1 (24-05-2006)

Licence

Identifiants

Citer

Alain Denise, Paul Zimmermann. Uniform Random Generation of Decomposable Structures Using Floating-Point Arithmetic. [Research Report] RR-3242, INRIA. 1997. ⟨inria-00073447⟩

388 Consultations

562 Téléchargements