String / Necklace (Bibtex)

P401: Enumeration of all $k$-color necklaces with $n$ beads

Input:

Integers $k$ and $n$.

Output:

All $k$-color necklaces with $n$ beads

Complexity:

Comment:

Reference:

[Fredricksen1978a] (Bibtex)

P360: Enumeration of all necklaces of length $n$ with two colors

Input:

An integer $n$.

Output:

All necklaces of length $n$ with two colors.

Complexity:

Comment:

Reference:

[Fredricksen1986b] (Bibtex)

P41: Enumeration of all $k$-ary necklaces

Input:

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

Output:

All $k$-ary necklaces with length $n$.

Complexity:

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

Comment:

A $k$-ary necklace is an equivalence class of k-ary strings under rotation.

Reference:

[Ruskey1992] (Bibtex)

P328: Enumeration of all $n$-bit necklaces with fixed density $d$

Input:

Two integer $n$ and $d$.

Output:

All $n$-bit necklaces with fixed density $d$.

Complexity:

$O(nN)$ total time and $O(n)$ space.

Comment:

$N$ is the number of solutions. A density of a $n$-bit necklace $T$ is $d$ if $T$ has $d$ ones.

Reference:

[Wang1996] (Bibtex)

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)

P303: Enumeration of all strings of some family

Input:

Output:

Complexity:

Constant amortized time per solution.

Comment:

This algorithm can list not only all necklaces but also all strings in other some family with CAT.

Reference:

[Cattell2000] (Bibtex)

P293: Enumeration of all $k$-ary necklaces with fixed content of length $n$

Input:

Two integer $k$ and $n$, and a content.

Output:

All $k$-ary necklaces with fixed content of length $n$.

Complexity:

Constant amortized time per solution.

Comment:

Reference:

[Sawada2003a] (Bibtex)