6533b870fe1ef96bd12d0434

RESEARCH PRODUCT

A Loopless Generation of Bitstrings without p Consecutive Ones

Vincent Vajnovszki

subject

CombinatoricsGray codeSet (abstract data type)Discrete mathematicssymbols.namesakeCode (set theory)Fibonacci numberBinary treeIntegersymbolsOrder (group theory)Hamiltonian pathMathematics

description

Let F n (p) be the set of all n-length bitstrings such that there are no p consecutive ls. F n (p) is counted with the pth order Fibonacci numbers and it may be regarded as the subsets of {1, 2,…, n} without p consecutive elements and bitstrings in F n (p) code a particular class of trees or compositions of an integer. In this paper we give a Gray code for F n (p) which can be implemented in a recursive generating algorithm, and finally in a loopless generating algorithm.

yearjournalcountryeditionlanguage
2001-01-01
https://doi.org/10.1007/978-1-4471-0717-0_19