An Efficient Algorithm for Generating Necklaces with Fixed Density

Abstract

A k-ary necklace is an equivalence class of k-ary strings under rotation. A necklace of fixed density is a necklace where the number of zeros is fixed. We present a fast, simple, recursive algorithm for generating (i.e., listing) fixed-density k-ary necklaces or aperiodic necklaces. The algorithm is optimal in the sense that it runs in time proportional to the number of necklaces produced.