The problem of exhaustively generating combinatorial objects can currently be applied to many disciplines, such as biology, chemistry, medicine and computer science. A well known approach to the exhaustive generation problem is given by the Gray code scheme for listing n-bit binary numbers in such a way that successive numbers differ in exactly one bit position. In this work, we introduce an exhaustive generation algorithm, which is general for the classes of succession rules considered in [1]. We also show that our algorithm is efficient in an amortized sense; it actually uses only a constant amount of computation per object.

Exhaustive generation of combinatorial objects by ECO / S. BACCHELLI; E. BARCUCCI; E. GRAZZINI; E. PERGOLA. - In: ACTA INFORMATICA. - ISSN 0001-5903. - STAMPA. - 40:(2004), pp. 585-602. [10.1007/s00236-004-0139-x]

Exhaustive generation of combinatorial objects by ECO

BARCUCCI, ELENA;GRAZZINI, ELISABETTA;PERGOLA, ELISA
2004

Abstract

The problem of exhaustively generating combinatorial objects can currently be applied to many disciplines, such as biology, chemistry, medicine and computer science. A well known approach to the exhaustive generation problem is given by the Gray code scheme for listing n-bit binary numbers in such a way that successive numbers differ in exactly one bit position. In this work, we introduce an exhaustive generation algorithm, which is general for the classes of succession rules considered in [1]. We also show that our algorithm is efficient in an amortized sense; it actually uses only a constant amount of computation per object.
2004
40
585
602
S. BACCHELLI; E. BARCUCCI; E. GRAZZINI; E. PERGOLA
File in questo prodotto:
File Dimensione Formato  
Acta 2004.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 192.67 kB
Formato Adobe PDF
192.67 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/250454
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 26
social impact