% !TEX root = kFKM.tex

In~\cite{DBLP:journals/jal/CattellRSSM00}, Cattell et al.~present a recursive necklace generation framework to generate prenecklaces, Lyndon words and necklaces of $\TUPLES{n}{k}$ in constant amortized time per symbol using $O(n)$ space. 
The basic idea is to recursively extend a prenecklace $\alpha = a_1 a_2 \cdots a_{t-1}$ to a length $t$ prenecklace in all possible ways. 
This is done efficiently by maintaining a variable $p$ which is the length of the longest prefix of $\alpha$  that is a Lyndon word. 
This algorithm can easily be adapted to construct $\FKM{\mathbf{S}}$ by concatenating the aperiodic prefixes of necklaces in $\mathbf{S} \in \CLASS{n}{k}$. %where $R$ is the rotations of $k$-suffix necklace set $N$. 
Let $\mathbf{P}(\mathbf{S})$ denote the set of prenecklaces in $\mathbf{S}$, and $\mathbf{P}$ denote the set of strings that can be extended to an element in $\mathbf{S}$. 
Pseudocode of the necklace concatenation algorithm is given in Algorithm~\ref{alg:decode}. 
 
\begin{algorithm}[t]                     
\caption{The generalized FKM construction for universal cycles of $\mathbf{S} \in \CLASS{n}{k}$.}          
\label{alg:decode} 
\small
        
\begin{algorithmic} [1]                   

\Procedure{FKM}{$t,p$}

\If{$t>n$} 
	\If{$n \text{ mod } p = 0$} \Call{Print}{$a_1a_2 \cdots a_p$}  \EndIf
\Else
	\For{$a_t$ {\bf from} $a_{t-p}$ {\bf to} $k$}	
		\If{$a_{t-p} = a_t$ {\bf and} $a_1 a_2 \cdots a_t \in \mathbf{P}$}  \Call{FKM}{$t+1, p$}  
		\ElsIf{$a_{t-p} < a_t$ {\bf and} $a_1 a_2 \cdots a_t \in \mathbf{P}$} \Call{FKM}{$t+1, t$}
		\EndIf
	\EndFor
\EndIf
\EndProcedure

\end{algorithmic}
\end{algorithm}



%The algorithm generates $\FKM{\mathbf{S}}$ in constant amortized time using $O(n)$ space if the membership tester of $\mathbf{P}(\mathbf{S})$ can be completed in constant amortized time using $O(n)$ space. 
%For example, the universal cycle for the rotations of necklaces~\cite{Ruskey_Wang1} and necklaces with weight at least $w$~\cite{lexi-smallest} can be generated in constant amortized time per bit using $O(n)$ space under this necklace concatenation framework. 

\begin{theorem} \label{thm:FKM-CAT}
The algorithm \emph{FKM} generates universal cycles for $\mathbf{S} \in \CLASS{n}{k}$ in constant amortized time per symbol using $O(n)$ space if \begin{enumerate}[label=\roman*)]
\item $n |\mathbf{P}(\mathbf{S})|$ is directly proportional to $|\mathbf{S}|$; and
\item the membership tester for $\mathbf{P}$ can be completed in constant amortized time using $O(n)$ space. 
\end{enumerate}
\end{theorem}
\begin{proof}
The algorithm \emph{FKM} generates each length $n$ prenecklace in $\mathbf{P}(\mathbf{S})$. 
Since there is no dead end in the algorithm \emph{FKM}, the number of recursive calls is bounded by $n |\mathbf{P}(\mathbf{S})|$.
Further, each recursive call of the algorithm \emph{FKM} runs in constant amortized time using $O(n)$ space if the membership tester for $\mathbf{P}$ can be completed in constant time per symbol using $O(n)$ space.
The algorithm thus generates universal cycles for $\mathbf{S}$ in constant amortized time per symbol using $O(n)$ space if it satisfies the two conditions.
\end{proof}

%Many combinatorial objects in $\CLASS{n}{k}$ satisfy these 2 conditions. 
For example, the following sets have their membership testers for $\mathbf{P}$ run in constant time and $n  |\mathbf{P}(\mathbf{S})|$ directly proportional to $|\mathbf{S}|$~\cite{Ruskey_Wang1,Forb2000,lexi-smallest}:
\begin{enumerate}[label=\roman*)]
\item $\TUPLES{n}{k}$; 
\item subsets of $\TUPLES{n}{2}$ with sum at least $s$;
\item subsets of $\TUPLES{n}{2}$ with at least $\ell_k$ copies of $k$;
\item subsets of $\TUPLES{n}{2}$ with at most $u_i$ copies of $i \in \{1, 2, \ldots, k-1\}$; 
\item subsets of $\TUPLES{n}{k}$ that circularly avoid substring $\beta \in \{1, 2, \ldots, k-1\}^{*}$; 
\item subsets of $\TUPLES{n}{k}$ that not equal to rotations of periodic necklace $\beta$; and
\item the union and intersection of any of the above sets,
\end{enumerate}

Thus their universal cycles can be generated in constant amortized time per symbol using $O(n)$ space. 
