P42: Enumeration of all $k$-ary necklaces with fixed density

P42: Enumeration of all $k$-ary necklaces with fixed density

Input:

$n$: a length of a necklace, $k$: a number of alphabet size, $d$: a number of nonzero characters.

Output:

All $k$-ary necklaces with fixed density $d$.

Complexity:

$O(1)$ amortized per output and $O(n)$ space.

Comment:

The set of $3$-ary necklace with $2$-density and $4$-length is $N_3(4,2) = \{0011, 0012, 0021, 0022, 0101, 0102, 0202\}$.

Reference:

[Ruskey1999] (Bibtex)