\documentclass[12pt]{article} \usepackage{e-jc} %\topmargin -0.425 truein \textheight 9.1 truein \oddsidemargin 0.0 %truein \evensidemargin 0.35 truein %\textheight 8.8 truein %\textwidth 6.5 truein \usepackage{times} \usepackage{amsthm,amsmath,amssymb} \usepackage{latexsym} \usepackage{graphics} \usepackage{color} \usepackage{url} \usepackage{verbatim} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\squishlist}{ \begin{list}{$\bullet$} { \setlength{\itemsep}{0pt} \setlength{\parsep}{3pt} \setlength{\topsep}{3pt} \setlength{\partopsep}{0pt} \setlength{\leftmargin}{2.5em} \setlength{\labelwidth}{1em} \setlength{\labelsep}{0.5em} } } \newcommand{\squishlisttwo}{ \begin{list}{$\triangleright$} { \setlength{\itemsep}{0pt} \setlength{\parsep}{0pt} \setlength{\topsep}{0pt} \setlength{\partopsep}{0pt} \setlength{\leftmargin}{2em} \setlength{\labelwidth}{1.5em} \setlength{\labelsep}{0.5em} } } \newcommand{\squishend}{ \end{list} } {\scriptsize \bibliographystyle{abbrv} \bibliography{references} } %\renewcommand{\baselinestretch}{1.0} \parskip 1.3ex %\parindent 0ex \setlength{\abovecaptionskip}{-3.5pt} \setlength{\belowcaptionskip}{-3.5pt} \title{Stamp Foldings, Semi-meanders, and Open Meanders: Fast Generation Algorithms} \date{\empty} \author{Joe Sawada\thanks{Supported by NSERC.}\\ \small School of Computer Science\\[-0.8ex] \small University of Guelph\\[-0.8ex] \small CANADA\\ [-0.2ex] \small\tt jsawada@uoguelph.ca \and Roy Li \qquad \\ \small School of Computer Science\\[-0.8ex] \small University of Guelph\\[-0.8ex] \small CANADA \\[-0.2ex] \small\tt royli0106@hotmail.com } \date{\dateline{Nov 12, 2010}{May 16, 2012}\\ \small Mathematics Subject Classifications: 68R05, 05A99} \begin{document} \maketitle \begin{abstract} By considering a permutation representation for stamp-foldings and semi-meanders we construct tree-like data structures that will allow us to generate these objects in constant amortized time. Additionally, by maintaining the wind-factor and applying an additional optimization, the algorithm for semi-meanders can be modified to produce the fastest known algorithm to generate open meanders. % to extend the order of a given meander, semi-meander, or stamp folding in constant time. Then using this data structure, we develop a constant amortized time algorithm to generate all semi-meanders of order $n$. By maintaining the wind-factor for semi-meanders and applying an additional optimization, the algorithm can be modified to produce the fastest known algorithm to generate meanders. Finally, by handling an additional special case, the semi-meander algorithm can be modified to generate all stamp foldings of order $n$ in constant amortized time. \end{abstract} \textbf{Keywords:} Stamp folding, semi-meander, meander, CAT algorithm, permutation \section{Introduction} \label{sec:intro} An \emph{open meander} can be described by a geographic analogy of a river starting from the north-west and meandering back and forth across an infinite horizontal road. The river never intersects itself and it can flow freely to the east. The \emph{order} of an open meander is the number of times the river intersects or crosses the road. For example, an open meander of order 6 is shown in Figure \ref{fig:examples}(a). A \emph{semi-meander} is a slight generalization of an open meander where one of the end points is allowed to be \emph{wound} inside the river. An example of a semi-meander, that is not a meander is shown in Figure \ref{fig:examples}(b). %By defining the \emph{wind-factor} \cite{diFrancesco} of a semi-meander to be the minimal number of crossing required to extend a semi-meander into an open meander, then we see that open meanders are precisely the semi-meanders with wind-factor 0. If we generalize a step further, and allow both ends of the river to be wound up inside itself, then we obtain a \emph{stamp folding}. An analogy is to consider a folding of a linear strip of $n$ stamps into a single pile, where the perforations between the stamps are assumed to be infinitely elastic. An example of a stamp folding that is not a semi-meander is shown in Figure~\ref{fig:examples}(c). Observe that each labeled crossing represents a stamp. As shown in the Figure \ref{fig:examples}, each of these three objects can be represented by a permutation; however not all permutations represent even the most general of these objects - the stamp foldings. For example, the permutation 1423, would require the strip of stamps (or river) to intersect itself. \begin{figure}[t] \begin{center} \resizebox{6.35in}{!}{\includegraphics{meander_stamp.pdf}} \end{center} \caption{\footnotesize (a) An open meander of order 6. (b) A semi-meander of order 6. (c) A stamp folding of order 7.} \label{fig:examples} \end{figure} The focus of this paper is to develop efficient algorithms to exhaustively list stamp foldings, semi-meanders and open meanders of order $n$. For a history on combinatorial generation algorithms consult Knuth's recent addition to his series \emph{The Art of Computer Programming}~\cite{knuth}. Stamp foldings were first discussed in \cite{koehler, touchard}, and algorithms for generating stamp foldings were considered in Scott Lausch's Master's thesis~\cite{lausch}. An implementation of the latter algorithm is used by the ``Combinatorial Object Server'' at {\texttt http://www.theory.csc.uvic.ca/} in the permutation section. A FORTRAN algorithm to generate all semi-meanders is outlined in the appendix of \cite{diFrancesco}, but no analysis is provided. An explicit algorithm for generating meanders has been given by Di Francesco et al \cite{diFrancesco} with complexity proportional to the Catalan numbers ($c_n \approx 4^n$). Franz and Earnshaw's \cite{franz} algorithm also appears to have an asymptotic running time that is greater than the number of meanders being generated (no implementation details or analysis is provided). The fastest known algorithm is given by Bobier and Sawada \cite{bobier}. Although a rigorous analysis is not provided, the implementation of the algorithm is very simple. For each of these three objects we can consider equivalences under various actions. For semi-meanders, if one end is uniquely determined to be allowed to wind inside the curve, we can consider equivalence under reversal to obtain \emph{symmetric semi-meanders}. For stamp foldings, if we consider the stamps to be unlabeled without regard for the orientation of the stamps, then we obtain \emph{unlabeled stamp foldings}. For example the permutation 1342 is equivalent to 4213 by relabeling the stamps. If we consider the reversal of each folding we may also obtain two different permutations; in this case we also obtain 2431 and 3124 as illustrated below. %The foldings from this example are illustrated in Figure \ref{fig:equiv}. % %\begin{figure}[h] \begin{center} \resizebox{6.35in}{!}{\includegraphics{unlabaled.pdf}} \end{center} % \caption{\footnotesize An equivalence class of unlabeled stamp foldings: $\{1342, 4213, 2431, 3124\}$.} % \label{fig:equiv} %\end{figure} % Note that each equivalence class will consist of either 2 or 4 permutations. An example of a class that contains only two permutations is $\{1234, 4321\}$. Similarly we can obtain \emph{symmetric meanders} by considering the same actions. Enumeration sequences for each of these 6 objects are given in the table below for $n$ up to 25. Each sequence is labeled with its corresponding sequence number in Sloane's Encyclopedia of Integer Sequences~\cite{sloane}. % %\begin{table}[h] %\label{tab:enum} \scriptsize \begin{center} \begin{tabular}{|r|r|r|r|r|r|r|} \hline & A000136 & A001011 & A000682 & A000560 & A005316 & A077055 \\ $n$ & Stamp Foldings & Unlabled Stamps & Semi-meanders & Symmetric Semis& Open Meanders & Symmetric Meanders \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 6 & 2 & 4 & 2 & 2 & 1 \\ 4 & 16 & 5 & 10 & 5 & 3 & 2 \\ 5 & 50 & 14 & 24 & 12 & 8 & 3 \\ 6 & 144 & 38 & 66 & 33 & 14 & 8 \\ 7 & 462 & 120 & 174 & 87 & 42 & 13 \\ 8 & 1392 & 353 & 504 & 252 & 81 & 42 \\ 9 & 4536 & 1148 & 1406 & 703 & 262 & 72 \\ 10 & 14060 & 3527 & 4210 & 2105 & 538 & 273 \\ 11 & 46310 & 11622 & 12198 & 6099 & 1828 & 475 \\ 12 & 146376 & 36627 & 37378 & 18689 & 3926 & 1970 \\ 13 & 485914 & 121622 & 111278 & 55639 & 13820 & 3506 \\ 14 & 1557892 & 389560 & 346846 & 173423 & 30694 & 15368 \\ 15 & 5202690 & 1301140 & 1053874 & 526937 & 110954 & 27888 \\ 16 & 16861984 & 4215748 & 3328188 & 1664094 & 252939 & 126510 \\ 17 & 56579196 & 13976335 & 10274466 & 5137233 & 933458 & 233809 \\ 18 & 184940388 & 46235800 & 32786630 & 16393315 & 2172830 & 1086546 \\ 19 & 622945970 & 155741571 & 102511418 & 51255709 & 8152860 & 2039564 \\ 20 & 2050228360 & 512559185 & 329903058 & 164951529 & 19304190 & 9652364 \\ 21 & 6927964218 & 1732007938 & 1042277722 & 521138861 & 73424650 & 18360296 \\ 22 & 22930109884 & 5732533570 & 3377919260 & 1688959630 & 176343390 & 88172609 \\ 23 & 77692142980 & 19423092113 & 10765024432 & 5382512216 & 678390116 & 169610371 \\ 24 & 258360586368 & 64590165281 & 35095839848 & 17547919924 & 1649008456 & 824506191 \\ 25 & 877395996200 & 219349187968 & 112670468128 & 56335234064 & 6405031050 & 1601297937 \\ \hline \end{tabular} \end{center} \normalsize %\caption{\footnotesize Enumeration sequences for a number of related objects up to $n=25$.} %\end{table} \bigskip \noindent The main results of this paper are as follows: \squishlisttwo \item A constant amortized time algorithm to generate stamp foldings, \item A constant amortized time algorithm to generate semi-meanders, \item The fastest known algorithm to generate open meanders. \squishend Additionally, these algorithms can be modified to obtain: \squishlisttwo \item A $O(n)$ amortized time algorithm to generate unlabeled stamp foldings, \item A constant amortized time algorithm to generate symmetric semi-meanders, \item A $O(n)$ amortized time algorithm to generate symmetric open meanders. \squishend For each algorithm, we use a permutation to represent each object as illustrated in Figure \ref{fig:examples}. An alternate permutation representation has been considered in \cite{hoffmann}. The key to each algorithm is a special tree-like data structure whose nodes contain a pair of doubly linked lists. By focussing on a specific current node, we can determine all the valid intervals to extend the order of a given object in constant time. Once the order is extended, the data structure can also be updated in constant time. In Section \ref{sec:semi} we begin by outlining this data structure for semi-meanders. Stamp foldings are slightly more complicated and are detailed in Section \ref{sec:stamp}. Then in Section \ref{sec:meander}, by maintaining the \emph{wind-factor} for semi-meanders we obtain an efficient algorithm to generate open-meanders. This algorithm is analyzed and compared experimentally with the previously fastest known algorithm to exhaustively list open-meanders \cite{bobier}. The paper concludes with a summary in Section \ref{sec:summary}. %The purpose of this paper is to present efficient generation algorithms to exhaustively list each of the previously mentioned objects. Each object is %represented using a permutation and appropriate data structures are required to ensure the efficiency of the algorithms. The primary %result is a Constant Amortized Time (CAT) algorithm to generate stamp foldings. Along the way we obtain CAT algorithms for semi-meanders %and symmetric semi-meanders. Additionally, we obtain the fastest known algorithm to generate open meanders. Unlabeled stamp %foldings and symmetric meanders can be generated in $O(n)$ amortized time. %In this paper we focus on the problem of efficiently listing open meanders, semi-meanders, and stamp-foldings. The goal is algorithms that run in constant amortized time. When constructing such an algorithm, choosing a representation is an important step. In \cite{bobier}, a character string representation is applied where an alphabet of size 4 represents the four different ways a river can cross the road. %In this paper, we will use a permutation representation to construct a data structure representation for each of the objects. Then using this data structure we outline a constant amortized time algorithm to generate (symmetric) semi-meanders in Section \ref{sec:semi}. By restricting the wind-factor to be 0 and applying an optimization, we obtain a fast algorithm to generate (symmetric) open meanders in Section \ref{sec:meander}. %In Section \ref{sec:stamp} the semi-meander algorithm is again modified to generate all (unlabeled) stamp foldings of order $n$ in constant amortized time. %Meanders have been studied in various contexts, including the %map-folding problem~\cite{lunnon}, stamp-folding problem~\cite{koehler,diFrancesco,touchard} and in relation to Jordan curves~\cite{bacher, reeds}, with literature dating back %to Poincar\'{e}'s work on differential geometry~\cite{poincar}. The %enumeration of meanders was shown to be equivalent to ``simple %alternating transit mazes'' of depth $n$~\cite{arnold}, and to the %enumeration of ovals of planar algebraic curves (Hilbert's 16$^{th}$ %problem)~\cite{touchard}. Meanders have also been linked to applications in polymer physics \cite{diFrancesco2} and the classification of 3-manifolds \cite{ko}. Some other relatives of meanders include %semi-meanders \cite{diFrancesco, diFrancesco2} and open meandric systems \cite{bobier, sawada}. %, and Motzkin words \cite{pana}. %By joining the endpoints of an open meander of odd order $2n-1$ we obtain a \emph{closed meander} of order $n$ (with $2n$ crossings). %A (closed) \emph{meander} or order $n$ is a self-avoiding curve that crosses a line in the plane %at $2n$ places. %The meandric number $M_n$ is the number of closed meanders up to smooth transformations of the curve. A long standing open problem is to obtain a closed formula expression for $M_n$. In the place of such a closed formula, many enumerative properties have been discovered \cite{barraud, diFrancesco2, laCroix} and the asymptotics have been widely studied \cite{albert, diFrancesco3, jensen, lando}; %currently the bound on the growth rate of closed meanders is estimated to be about 12.3. Others have %constructed exact enumeration algorithms \cite{bobier, diFrancesco, franz, jensen}. %To date, the fastest enumeration method is due to Jensen \cite{jensen} using a transfer matrix approach that does not actually generate every closed meander, but still has an exponential growth rate %of about 2.5. Using this algorithm the values for $M_n$ have been computed up to $n=24$ with the limiting factor of the algorithm being memory and not time. The algorithm can also be modified %to enumerate both open meanders and semi-meanders. %{\bf A000136} Number of ways of folding a strip of n labeled stamps. %1, 2, 6, 16, 50, 144, 462, 1392, 4536, 14060, 46310, 146376, 485914, 1557892, 5202690, %16861984, 56579196, 184940388, 622945970, 2050228360, 6927964218, 22930109884, 77692142980, 258360586368, 877395996200, %2929432171328, 9968202968958, 33396290888520, 113837957337750 %{\bf A000682} Semimeanders: number of ways a semi-infinite directed curve can cross a straight line n times. % 1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874, 3328188, 10274466, 32786630, 102511418, 329903058, 1042277722, 3377919260, 10765024432, 35095839848, 112670468128, 369192702554, 1192724674590, 3925446804750 % {\bf A000560} Number of ways of folding a strip of n labeled stamps. % 1, 2, 5, 12, 33, 87, 252, 703, 2105, 6099, 18689, 55639, 173423, 526937, 1664094, 5137233, 16393315, 51255709, 164951529, 521138861, 1688959630, 5382512216, 17547919924, 56335234064, 184596351277, 596362337295, 1962723402375 % {\bf A005316} Meandric numbers: number of ways a river can cross a road n times. % 1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954, 252939, 933458, 2172830, 8152860, 19304190, 73424650, 176343390, 678390116, 1649008456, 6405031050, 15730575554, 61606881612, 152663683494, 602188541928, 1503962954930, % {\bf A005315} Closed meandric numbers (or meanders): ways a loop can cross a road 2n times. %1, 1, 2, 8, 42, 262, 1828, 13820, 110954, 933458, 8152860, 73424650, 678390116, %{\bf A001011} Number of ways to fold a strip of n blank stamps. %1, 1, 2, 5, 14, 38, 120, 353, 1148, 3527, 11622, 36627, 121622, 389560, 1301140, 4215748, 13976335, 46235800, 155741571, 512559185, 1732007938, 5732533570, 19423092113, 64590165281, 219349187968, 732358098471 %{\bf A001010} Number of symmetric foldings of a strip of n stamps. %1, 2, 2, 4, 6, 8, 18, 20, 56, 48, 178, 132, 574, 348, 1870, 1008, 6144, 2812, 20314, 8420, 67534, 24396, 225472, 74756, \section{Generating semi-meanders and stamp foldings} \label{sec:semi} In this section we begin by describing an algorithm to exhaustively list all semi-meanders and symmetric semi-meanders of order $n$, since they are the easiest to handle using the permutation representation. The key to making the algorithm run in constant amortized time is the maintenance of a tree of special nodes. Then, by applying a subtle tweak to this data structure, we outline a constant amortized time algorithm for stamp foldings. \subsection{Semi-meanders} The basic idea behind our algorithm is to extend a semi-meander of order $t$ represented by a permutation $P$ to a semi-meander of order $t{+}1$ by considering all \emph{valid} intervals to extend the semi-meander curve. For example, Figure~\ref{fig:meander}(a) below illustrates a semi-meander of order 9 along with its corresponding permutation representation. The valid intervals to extend the semi-meander through are (3,2), (1,9), (9,8) and (7,4) respectively. %Since it may be possible to insert the value to the beginning or end of the permutation, We consider the permutation to be prefixed with a `0' and suffixed with a `$-$', so that every interval has a clearly defined start and end value. From our example, this means that $(0,3)$ would be the leftmost interval and $(4,-)$ would be the rightmost interval. \begin{figure}[h] \begin{center} \resizebox{5.42in}{!}{\includegraphics{meander_merge.pdf}} \end{center} \caption{\footnotesize (a) A semi-meander of order 9 and its permutation representation. (b) The node tree for the semi-meander in (a). (c) The node tree obtained by extending the semi-meander in (a) to cross the interval (7,4).} \label{fig:meander} \end{figure} \normalsize Given a permutation representing a semi-meander of order $t$, our goal is to efficiently determine which of the $t+1$ intervals can be used for the next crossing. If these intervals are available in a list, then we can use the simple algorithm \textsf{Gen}($t$) in Figure \ref{fig:gen} to generate all semi-meanders of order $n$. The permutation $P$ is initialized to have one crossing and the initial call is \textsf{Gen}(2). For this first recursive call, the $LIST$ will consist of the two intervals $(0,1)$ and $(1,-)$. The permutation itself can be updated in constant time if it is represented as a doubly linked list with pointers to each element. The function \textsf{Process}($P$) is a generic function that may perform some action on the current semi-meander $P$. \begin{figure} \begin{center} \small \begin{tabbing} 12345\=12345\=12345\=12345\=12345\=12345\=12345\=12343 \kill \> \> {\bf procedure} \textsf{Gen} ($t$) \\ \> \> \> {\bf if} ($t>n$) {\bf then} \textsf{Process}($P$) \\ \> \> \> {\bf else} \\ \> \> \> \> $LIST := $ list of valid intervals to extend the semi-meander \\ \> \> \> \> {\bf for each} interval $I \in LIST$ {\bf do}\\ \> \> \> \> \> insert $t$ into permutation $P$ depending on $I$ \\ \> \> \> \> \> \textsf{Gen}($t{+}1$) \\ \> \> \> \> \> remove $t$ from $P$\\ \> \> {\bf end} \\ \end{tabbing} \caption{\footnotesize Algorithm \textsf{Gen}$(t)$, to list semi-meanders of order $n$.} \label{fig:gen} \end{center} \end{figure} In order to efficiently obtain and update such a list of intervals, it is useful to split the list into two doubly linked lists $L$ and $R$ such that $L$ (respectively $R$) contains all valid intervals to the left (right) of the current crossing. For example, if the current permutation $P$ is $321985674$ as illustrated in Figure \ref{fig:meander}(a), then $L = \langle (3,2), (1,9) \rangle$ and $R = \langle (9,8), (7,4) \rangle$. The lists are doubly linked so that the addition or deletion of an interval can be done in constant time. We call the data structure containing these two lists a \emph{node}. If $X$ is a node, then we let $L_X$ denote its left list and let $R_X$ denote its right list. If we consider what happens when we extend a semi-meander by crossing through an interval $I$, then it becomes apparent that we need to know which intervals become valid in addition to the new intervals that have just been created. For example, if we extend the semi-meander in Figure \ref{fig:meander}(a) by crossing the interval (7,4) then in addition to the new intervals $(7,10)$ and $(10,4)$, the next crossing would also be able to cross interval (5,6) to the left but nothing else to the right. This leads to building a \emph{tree of nodes} where each interval points to a unique node in the tree and where each interval appears in exactly one node. As an example, the tree of nodes correponding to the semi-meander in Figure \ref{fig:meander}(a) is shown in part (b) where the \emph{current node} labeled $X$ is in bold. %The wind-factor for the semi-meander is represented by the depth of the current node; in this case %the wind-factor is 1. To incorporate the tree of nodes data structure to the basic algorithm \textsf{Gen}($t$): \squishlist \small \item pass the current node $X$ as a parameter to each recusive call, \item set $LIST$ to the concatenation of $L_X$ and $R_X$, \item let $Y$ represent the node pointed to by the current interval $I=(i,j)$, and \item add a function \textsf{Update}($X, Y, I)$ to update the tree of nodes data structure and the permutation $P$. \squishend The challenge that remains is how to efficiently implement the function \textsf{Update}($X,Y,I$). Observe that as the interval $I$ is crossed by the semi-meander, it will be replaced with 2 new intervals in $Y$: $I_1=(i,t)$ and $I_2=(t,j)$. It is not difficult to see that $I_1$ should be added to the end of $L_Y$ and that $I_2$ will be inserted to the front of $R_Y$. Once $I$ is removed from $X$, the remaining intervals of $X$ get split into 2 nodes $X_1$ and $X_2$ such that $X_1$ contains the intervals accessible by crossing $I_1$ and $X_2$ contains the intervals accessible by crossing $I_2$. Once these nodes are created, we set $I_1$ to point to $X_1$ and $I_2$ to point to $X_2$. Precisely how the node $X$ is split into $X_1$ and $X_2$ depends on whether $I$ belongs to $L_X$ or $R_X$. If the intervals in the list containing $I$ are $i_1, i_2, \ldots, i_k$, where $i_c$ denotes the interval $I$ being crossed, then the following table describes how to construct $X_1$ and $X_2$: %is described as follows: %\begin{table}[t] \begin{center} \small \begin{tabular}{|l|l|} \hline \ \ \ \ \ \ \ \ \ $I \in L_X$ & \ \ \ \ \ \ \ \ \ $I \in R_X$ \\ \hline \hline $L_{X_1} = i_1, \ldots , i_{c-1}$ & $L_{X_1} = i_1, \ldots , i_{c-1}$ \\ $R_{X_1} = R_X$ & $R_{X_1} = $ null \\ \hline $L_{X_2} = $ null & $L_{X_2} = L_X$ \\ $R_{X_2} = i_{c+1}, \ldots , i_{k}$ & $R_{X_2} = i_{c+1}, \ldots , i_{k}$ \\ \hline \end{tabular} \end{center} %\caption{ \small Rules for splitting the current node $X$ into $X_1$ and $X_2$ depending on which list the current %interval $I=i_c$ is in.} %\label{tab:rules} %\end{table} %in Table \ref{tab:rules}. %Notice that the split depends on whether $I$ belongs to $L_X$ or $R_X$. %For each case assume the intervals in the list are $i_1, i_2, \ldots, i_k$, where $i_c$ denotes the interval $I$ %being crossed. Each of these assignments can be implemented in constant time by maintaining pointers to the start and end of each interval list. To summarize, the function \textsf{Update}($X,Y,I$) does the following: \small \squishlist \item insert the new interval $I_1 = (i,t)$ to the end of $L_Y$, \item insert the new interval $I_2 = (t,j)$ to the front of $R_Y$, \item remove interval $I$ from $X$, \item split $X$ into two new nodes $X_1$ and $X_2$ %with lists as described in Table \ref{tab:rules} \item set $I_1$ to point to $X_1$ and set $I_2$ to point to $X_2$. \squishend \normalsize As an example of the steps involved in an update, Figure \ref{fig:meander}(c) shows the result of how the node tree from Figure \ref{fig:meander}(b) gets updated when the interval (7,4) (from $R_X$) is crossed. Observe in the figure that the new intervals added to $Y$ point to nodes labeled $X_1$ and $X_2$. By applying the tree of nodes data structure, the resulting algorithm \textsf{GenSemi}($t,X$) is shown in Figure \ref{fig:gen2}. The procedure \textsf{Restore}() undoes the changes made in \textsf{Update}($X,Y,I$). Both functions can be implemented to run in constant time. To initialize the algorithm an initial node $X$ is created with $L_X = \langle (0,1) \rangle$ and $R_x = \langle (1,-) \rangle$. The initial intervals point to nodes with empty interval lists. The initial call is \textsf{GenSemi}(2, $X$). %A straightforward analysis in Section \ref{sec:anal} shows that the algorithm runs in constant amortized time. \begin{figure} \begin{center} \small \begin{tabbing} 12345\=12345\=12345\=12345\=12345\=12345\=12345\=12343 \kill \> \> {\bf procedure} \textsf{Update}($X$, $Y$, $I$) \\ \> \> \> insert new intervals $I_1 := (i,t)$ and $I_2 := (t,j)$ into $Y$ \\ \> \> \> remove $I=(i,j)$ from $X$ \\ \> \> \> split $X$ into $X_1$ and $X_2$ \\ \> \> \> point $I_1$ to $X_1$ \\ \> \> \> point $I_2$ to $X_2$ \\ \> \> \> update $P$ \\ \> \> {\bf end} \\ \> \\ \> \> {\bf procedure} \textsf{GenSemi} ($t, X$) \\ \> \> \> {\bf if} ($t>n$) {\bf then} \textsf{Process}($P$) \\ \> \> \> {\bf else} \\ \> \> \> \> {\bf for each} interval $I=(i,j) \in L_X, R_X$ {\bf do}\\ \> \> \> \> \> $Y := $ node pointed to by $I$ \\ \> \> \> \> \> \textsf{Update}($X$, $Y$, $I$) \\ \> \> \> \> \> \textsf{GenSemi}($t{+}1$, $Y$) \\ \> \> \> \> \> \textsf{Restore}() \\ \> \> {\bf end} \\ \end{tabbing} \caption{\footnotesize Algorithm \textsf{GenSemi}$(t, X)$, to list semi-meanders of order $n$.} \label{fig:gen2} \end{center} \end{figure} To analyze this algorithm, observe that each recursive call is the result of a constant amount of work. Thus, the total amount of work done by the algorithm is proportional to the number of recursive calls in the computation tree. Since the number of semi-meanders generated is equal to the number of leaves in the computation tree, an amortized analysis can be performed by considering the ratio of the total number of nodes in the computation tree to the number of leaves. If this ratio is bounded by a constant then the algorithm will run in constant amortized time, i.e., the total work done divided by the number of objects generated is bounded by a constant. Since there are no dead ends in this algorithm, every recursive call will lead to an semi-meander being generated. Also, there are always at least two possible ways to extend a semi-meander of order $i$ to one of order $i+1$: i.e., each internal node has at least 2 children. Thus, the number of leaves will be greater than the number of internal nodes which implies that the ratio is constant. \begin{theorem} Semi-meanders of order $n$ can be generated in constant amortized time. \end{theorem} \subsubsection{Symmetric semi-meanders} By considering reflective symmetry about the first crossing we obtain symmetric semi-meanders. To generate symmetric semi-meanders using the algorithm in \textsf{GenSemi}($t,X$), we force the second crossing to be to the left (or equivalently to the right) of the first crossing. This can be implemented in constant time by skipping the intervals in the right list when $t=2$. Alternatively, the semi-meander can be initialized to have two crossings. \begin{corollary} Symmetric semi-meanders of order $n$ can be generated in constant amortized time. \end{corollary} \subsection{Stamp Foldings} \label{sec:stamp} Recall that a stamp folding is a generalization of a semi-meander where both ends are allowed to wind inside the curve (river, strip of stamps). To generate stamp foldings, we can apply the semi-meander algorithm \textsf{GenSemi}($t,X$) with a slight change to the data structures. In particular, for stamp foldings the two intervals $(0,x)$ and $(y,-)$ will always belong to the same node $X$ and will both point to the same node $Y$. This means we no longer have a \emph{tree} of nodes, which makes the algorithm slightly more complicated when one of the intervals $(0,x)$ or $(y,-)$ is crossed. As an illustration, the node structures for a series of stamp foldings in Figure \ref{fig:stamp}. \begin{figure}[t] \begin{center} \resizebox{4.61in}{!}{\includegraphics{stamp_merge.pdf}} \end{center} \caption{\footnotesize (a) A stamp folding of order 7 and its corresponding data structure representation. (b) The changes after extending the stamp folding in (a) by crossing (5,7). (c) The changes after extending the stamp folding in (b) by crossing (0,3). } \label{fig:stamp} \end{figure} Since an interval $I=(0,x)$ is special, consider what happens just before such an interval is crossed (a similar analysis applies to $(y,-)$). Assume that the interval $I$ points to the node $Y$. In the case of semi-meanders, all valid intervals will be in the right list $R_Y$ and the left list $L_Y$ will be empty. However, for stamp-foldings, if $Y$ was created by crossing through an interval of the form $(y,-)$ then all available intervals will be in the left list $L_Y$ and the right list $R_Y$ will be empty. Since there are pointers to the front of each list, this can be checked in constant time. Thus after we cross $I$, if the left list $L_Y$ is non-empty then we set $R_Y=L_Y$ and set $L_Y$ to be empty. The only remaining modification is to move the interval of the form $(y,-)$ from $X$ to the end of $R_Y$. This can also be done in constant time since we maintain pointers to the end of each list. In order to convert the algorithm \textsf{GenSemi}($t,X$) into one that generates all stamp foldings, the following operations must be added to the function \textsf{Update}($X,Y,I$): \squishlist \item If crossing an interval $I$ in node $X$ of the form $(0,x)$ then \squishlisttwo \item if $L_Y$ is not empty assign $R_Y=L_Y$ and set $L_Y$ to be empty, \item move the interval $(y,-)$ which is the last interval in $R_X$ to the end of $R_Y$ and point it to node $X_1$. \squishend \item If crossing an interval $I$ in node $X$ of the form $(y,-)$ then \squishlisttwo \item if $R_Y$ is not empty assign $L_Y=R_Y$ and set $R_Y$ to be empty, \item move the interval $(0,x)$ which is the first interval in $L_X$ to the front of $L_Y$ and point it to node $X_2$. \squishend \squishend The function \textsf{Restore}() must undo these operations. The analysis for stamp foldings is the same as for semi-meanders since at each recursive call there are at least two ways to extend the current permutation. \begin{theorem} Stamp foldings of order $n$ can be generated in constant amortized time. \end{theorem} \subsubsection{Unlabeled stamp foldings} Recall from Section \ref{sec:intro} that if we consider the stamps to be unlabeled and disregard the orientation of each stamp folding, we obtain an unlabeled stamp folding. Each equivalence class has at most 4 permutations and we let the lexicographically smallest permutation be the canonical representative. Unfortunately, to determine whether a given permutation is in canonical form is not a trivial matter like it was for symmetric semi-meanders. Thus it remains an open problem to generate unlabeled stamp foldings in constant amortized time. By performing a simple linear time check on each permutation against the 4 possible symmetries we obtain the following theorem. \begin{theorem} Unlabeled stamp foldings of order $n$ can be generated in $O(n)$ amortized time. \end{theorem} \section{The wind-factor and open meanders} \label{sec:unwind} The \emph{wind-factor} \cite{diFrancesco} of a semi-meander is the smallest number of additional crossings required to extend the semi-meander into an open meander. Thus, meanders are precisely the semi-meanders with wind-factor 0. For example, the wind-factor of the semi-meander in Figure \ref{fig:meander}(a) is 1 and it also corresponds to the depth of the current node in its tree of nodes. As another example, the wind-facor of the semi-meander in Figure \ref{fig:examples}(b) is 2. We consider the wind-factor for two reasons. First it may be of interest to list all semi-meanders with a given wind-factor. Second, it is important to maintain if we want to efficiently modify the semi-meander algorithm to generate all open meanders. We begin this section by outlining how to modify the semi-meander algorithm \textsf{GenSemi}($t,X$) so it maintains the wind-factor. Then we discuss how it can be applied to efficiently generate meanders. \subsection{Maintaining the wind-factor} In order to generate all semi-meanders with a given wind-factor $w$, we must maintain the current wind-factor at each step of the algorithm \textsf{GenSemi}($t,X)$. In order to efficiently maintain this information, we need to know the unique interval that can be crossed to reduce the wind-factor if $w>0$ or to maintain the wind-factor if $w=0$ . We call such an interval the \emph{unwinding interval} and for a node $X$ we denote its unwinding interval by $U_X$. If $w>0$, then every node in the path up the tree from the current node will have an unwinding interval associated with it. For example, in Figure \ref{fig:meander}(a-b), the unwinding interval for the current node labeled $X$ is (1,9). The node pointed to by this interval will have wind-factor $w=0$ and if it becomes the current node, the unique interval that maintains the wind-factor is $(4,-)$. If we add a pointer to the unwinding interval in the node data structure, then we can determine if a given interval corresponds to the unwinding interval in constant time. To efficiently maintain the unwinding intervals it is important to know which list it is in: the Left or the Right. For a given node $X$ let $S_X \in \{$L,R$\}$ denote the list that the unwinding interval belongs to. If we add the current wind-factor $w$ as a parameter to each recursive call, then we can maintain the wind-factor in constant time as follows: if the current interval corresponds to the unwinding interval then we decrement the wind-factor if $w>0$ and leave it unchanged if $w=0$; otherwise we increment the wind-factor. The only challenge that remains is to update the unwinding intervals when a new crossing is added. To simplify the discussion, let the function \textsf{SetUnwind}($X, I, s$) set the unwinding interval $U_X=I$ and its corresponding list $S_X=s$. There are several cases to consider; however, by maintaining a boolean to remember if the unwinding interval has been visited when iterating through the interval lists, each case can be performed in constant time and added to the function \textsf{Update}($X,Y,I$) as follows: \squishlist \item If $I=U_X$ when $w>0$: no update required. \item If $I=U_X$ when $w=0$: call \textsf{SetUnwind}($Y, I_2,$ R). \item If $I\ne U_X$ and $I \in L_X$: \squishlisttwo \item If $U_X \in L_X$ and comes after $I$ call \textsf{SetUnwind}($Y, I_2,$ R) and \textsf{SetUnwind}($X_2, U_X,$R). \item Otherwise call \textsf{SetUnwind}($Y, I_1,$ L) and \textsf{SetUnwind}($X_1, U_X, S_X$). \squishend \item If $I\ne U_X$ and $I \in R_X$: \squishlisttwo \item If $U_X \in R_X$ and comes after $I$ call \textsf{SetUnwind}($Y, I_2,$ R) and \textsf{SetUnwind}($X_2, U_X, S_X$). \item Otherwise call \textsf{SetUnwind}($Y, I_1,$ L) and \textsf{SetUnwind}($X_1, U_X,$ L). \squishend \squishend These correctness of these updates can easily be observed by considering a few sample semi-meanders like the one in Figure \ref{fig:meander}(a). Applying these extra operations allows us to generate all semi-meanders of order $n$ with a given wind-factor $w$. As a summary, to maintain the wind-factor efficiently the node data structure is as follows: \squishlist \item $L_X$: a doubly linked list of valid intervals to the left of the current crossing ordered from left to right, \item $R_X$: a doubly linked list of valid intervals to the right of the current crossing ordered from left to right, \item $U_X$: a pointer to the unwinding interval if it exists, \item $S_X \in \{$L,R$\}$: a character indicating which list the unwinding interval is in if it exists. \squishend \bigskip \subsection{Generating Open Meanders} \label{sec:meander} To generate open meanders, we can simply apply the semi-meander algorithm that maintains the wind-factor and then output only those semi-meanders with wind-factor 0. Such an algorithm would be far from efficient since it effectively generates all semi-meanders. However by applying the following optimization we obtain a much more efficient algorithm. The basic idea is to consider a semi-meander with wind-factor $w$ and order $n-w$. For such a semi-meander there there is no point in winding any further, since it will never produce an open meander of order $n$. Thus, in this situation, we only produce a recursive call for the interval corresponding to the unwinding interval. Specifically, the optimization is as follows: \medskip \begin{observation} If $w$ is the wind-factor of a semi-meander of order $t-1$ and $n-t \leq w$, then the only way the semi-meander can be extended into an open meander of order $n$ is by unwinding. \end{observation} \medskip Pseudocode that applies this optimization to generate open meanders is given by \textsf{GenMeander}($t,X,w$) shown in Figure \ref{fig:genmeander}. The initialization is the same as with semi-meanders with the wind-factor $w$ initially set to 0. It is assumed that the function \textsf{Update}($X,Y,I$) updates the unwinding intervals as outlined in the previous subsection and that the function \textsf{Restore} undoes this action. \begin{figure}[t] \begin{center} \small \begin{tabbing} 12345\=12345\=12345\=12345\=12345\=12345\=12345\=12343 \kill \> \> {\bf procedure} \textsf{GenMeander} ($t, X, w$) \\ \> \> \> {\bf if} ($t>n$) {\bf then} \textsf{Process}($P$) \\ \> \> \> {\bf else} \\ \> \> \> \> {\bf if} ($n-t \leq w$) {\bf then} \\ \> \> \> \> \> $Y := $ node pointed to by $U_X$ \\ \> \> \> \> \> \textsf{Update}($X,Y, U_X$) \\ \> \> \> \> \> \textsf{GenMeander}($t{+}1$, $Y$, $w-1$) \\ \> \> \> \> \> \textsf{Restore}()\\ \> \> \> \> {\bf else} \\ \> \> \> \> \> {\bf for each} interval $I \in L_X, R_X$ {\bf do}\\ \> \> \> \> \> \> $Y := $ node pointed to by $I$ \\ \> \> \> \> \> \> \textsf{Update}($X,Y,I$) \\ \> \> \> \> \> \> {\bf if} ($I = U_X$) {\bf then} \textsf{GenMeander}($t{+}1$, $Y$, max($0,w-1$)) \\ \> \> \> \> \> \> {\bf else} \textsf{GenMeander}($t{+}1$, $Y$, $w+1$) \\ \> \> \> \> \> \> \textsf{Restore}()\\ \> \> {\bf end} \\ \end{tabbing} \caption{\footnotesize Algorithm \textsf{GenMeadner}$(t, X, w)$, to list open meanders of order $n$.} \label{fig:genmeander} \end{center} \end{figure} The analysis for algorithm \textsf{GenMeander}($t,X,w$) is a challenge because of the introduction of degree one nodes in the computation tree when applying the optimization. Each such degree one node will correspond to a semi-meander of order $n-i$ with a wind-factor of $i$ for some $i>0$. Let $Comp(n)$ denote the number of nodes in the computation tree to generate open meanders of order $n$. We partition the computation tree into sets of nodes based on the order of the node and the wind-factor. Let $S(i, j)$ denote the number of semi-meanders or order $i$ with a wind-factor of $j$. Since the wind-factor of a node with order $i$ will never exceed $n-i$ (from the \newpage \noindent algorithm's optimization), we obtain the following expression for $Comp(n)$: \[ Comp(n) = \sum_{i=1}^n \sum_{j=0}^{min(i-1, n-i)} S(i, j). \] As an illustration, we consider $Comp(7)$: \begin{eqnarray*} Comp(7) & = & S(1,0) + \\ & & S(2,0) + S(2,1) + \\ & & S(3,0) + S(3,1) + S(3,2) + \\ & & S(4,0) + S(4,1) + S(4,2) + S(4,3) + \\ & & S(5,0) + S(5,1) + S(5,2) + \\ & & S(6,0) + S(6,1) + \\ & & S(7,0). \end{eqnarray*} Note that $S(i,0)$ counts the number of open meanders of order $i$. To prove that the generation algorithm for open meanders runs in constant amortized time we must show that there exists some constant $c$ such that $$\frac{Comp(n)}{S(n,0)} \leq c. $$ \newpage \noindent Empirically, for $n$ up to 27 this ratio for the algorithm \textsf{GenMeander}($t,X,w$) is given in the following table: \begin{center} \begin{tabular}{|r|r||r|r|} \hline $n$ & $\frac{Comp(n)}{S(n,0)}$ & $n$ & $\frac{Comp(n)}{S(n,0)}$ \\ \hline 4 & 3.00000 & 5 & 2.87500 \\ 6 & 3.14286 & 7 & 2.92857 \\ 8 & 3.13580 & 9 & 2.94275 \\ 10 & 3.13197 & 11 & 2.96007 \\ 12 & 3.13831 & 13 & 2.97923 \\ 14 & 3.14882 & 15 & 2.99745 \\ 16 & 3.16008 & 17 & 3.01381 \\ 18 & 3.17084 & 19 & 3.02824 \\ 20 & 3.18072 & 21 & 3.04092 \\ 22 & 3.18965 & 23 & 3.05207 \\ 24 & 3.19769 & 25 & 3.06194 \\ 26 & 3.20492 & 27 & 3.07070 \\ \hline %28 & 3.??? & 29 & 3.??? \\ \hline \end{tabular} \end{center} % Even though the ratio is growing, it does not rule out the possibility that it is bounded by a constant. What is required is the ability to bound $S(i,j)$ recursively. \begin{lemma} For $i>1:$ \squishlist \item[(a)] $S(i,0) = S(i-1,0) + S(i-1,1)$, \item[(b)] $S(i,j) \geq S(i-1, j+1) + S(i-1,j-1)$ for $j>0$. \squishend \end{lemma} \textsc{Proof:} For (a) consider the first $i{-}1$ crossings for any semi-meander of order $i$ and wind-factor 0. Either the first $i{-}1$ crossings will have wind factor 1 or 0. In either case, there is exactly one way to extend such semi-meanders into ones with wind-factor 0. For part (b), observe that each semi-meander of order $i{-}1$ and wind factor $j{+}1$ can be extended uniquely into a semi-meander of order $i$ and wind factor $j$ (via the unwinding interval). For a semi-meander of order $i{-}1$ and wind factor $j{-}1$, there may be many ways to extend it into one with wind factor $j$ by adding one more crossing, thus giving the simple bound. \hfill $\Box$ The second bound for $j>0$ can actually be improved to \[S(i,j) \geq S(i-1, j+1) + \sum_{k=0}^{\lfloor i/2 \rfloor-1} S(i-1-2k, j-1)\] by considering unique extensions of semi-meanders of order $i-1-2k$ with wind factor $j-1$ into semi-meanders of order $i$ and wind factor $j$. Unfortunately, even tighter bounds seem to be required to prove the conjecture that the generation algorithm for open meanders runs in constant amortized time. Since we do not have a proof of such a claim, we prove the very loose upper bound of a $O(n)$ amortized time algorithm. By considering the diagonals of $Comp(n)$ moving from the bottom left to the top right, we can re-express $Comp(n)$ as follows: \[ Comp(n) = \sum_{i=1}^n \sum_{j=0}^{\lceil \frac{i}{2} \rceil -1} S(i-j, j). \] Since $S(i,j) > S(i-1, j+1)$ we get the bound: \begin{eqnarray*} Comp(n) & \leq & \sum_{i=1}^n i \cdot S(i, 0) \\ & \leq & n \cdot \sum_{i=1}^n S(i, 0) \\ & \leq & cn\cdot S(n, 0), \end{eqnarray*} where $c$ is a constant since open meanders grow exponentially. \begin{theorem} Open meanders of order $n$ can be generated in $O(n)$ amortized time. \label{thm:meander} \end{theorem} Using a 2.2 GHz Opteron processor, Table \ref{tab:compare} compares the running time of our algorithm \textsf{GenMeander}($t,X,w$) for open meanders with the fastest previously known algorithm from \cite{bobier}. Observe that for $n=29$ that our new algorithm finds all open meander in about 31.8 hours compared to 46.1 hours for the algorithm in \cite{bobier}. \begin{table}[h] \begin{center} \small \begin{tabular}{|r|r|r||r|r|r|} \hline $n$ & \textsf{GenMeander}($t,X,w$) & Algorithm from~\cite{bobier} & $n$ & \textsf{GenMeander}($t,X,w$) & Algorithm from~\cite{bobier} \\ \hline 20 & 4 \ \ & 5 \ \ & 21 & 14 \ \ & 20 \ \ \\ 22 & 35 \ \ & 43 \ \ & 23 & 127 \ \ & 186 \ \ \\ 24 & 325 \ \ & 430 \ \ & 25 & 1214 \ \ & 1877 \ \ \\ 26 & 3139 \ \ & 4022 \ \ & 27 & 11700 \ \ & 16575 \ \ \\ 28 & 30480 \ \ & 38358 \ \ & 29 & 114414 \ \ & 165987 \ \ \\ \hline \hline \end{tabular} \end{center} \caption{\footnotesize Comparison of running time in seconds for two open meander generation algorithms.} \label{tab:compare} \end{table} \subsubsection{Symmetric Open Meanders} \label{sec:sym_meander} Recall from Section \ref{sec:intro} that if we consider the equivalence classes of open meanders under the operations of relabeling and reversal, we obtain symmetric meanders. If we let the lexicographically smallest element be the canonical representative of each equivalence class then the following tests can be performed on each generated open meander to determine if it corresponds to its canonical representative: \squishlist \item make sure that 1 appears before $n$ in the permutation, and \item test that the permutation is lexicographically smaller than its relabeled reversal: each value $i$ from the original permutation is replaced with $n-i+1$ and the result is considered in reverse. \squishend These tests can easily be performed in $O(n)$ time after each open meander has been generated. Thus from Theorem \ref{thm:meander} we obtain the following result. \begin{corollary} Symmetric open meanders of order $n$ can be generated in $O(n)$ amortized time. \end{corollary} %One approach is to show that each diagonal is growing exponentially from right to left. %In other words we want to show that: %\[ c \cdot S(i,0) \geq \sum_{j=0}^{\lceil \frac{i}{2} \rceil -1} S(i-j, j) \] %\begin{lemma} %$S(i,j) \geq c \cdot S(i-1, j+1)$ %\end{lemma} \section{Summary} \label{sec:summary} In this paper we have constructed a new data structure representation for semi-meanders, meanders and stamp foldings and applied the data structure to develop efficient algorithms to exhaustively list: \squishlist \item semi-meanders and symmetric semi-meanders in $O(1)$ amortized time, \item stamp foldings in $O(1)$ amortized time, \item unlabeled stamp foldings in $O(n)$ amortized time. \item open meanders in $O(n)$ amortized time, and \item symmetric open meanders in $O(n)$ amortized time, \squishend The algorithms have been implemented in C and are available for download at: \\ \small \url{http://www.socs.uoguelph.ca/~sawada/programs.html}. \normalsize It remains an open problem to determine whether or not the meander algorithm provided in this paper runs in constant amortized time. This can be answered if the right recursive bounds can placed on semi-meanders with a given wind-factor. Another open problem is to improve the running time for unlabeled stamp foldings. Finally, does there exist a Gray code for any of these objects? %------------------------------------------------------------------------- \begin{thebibliography}{77} \footnotesize %\bibitem{albert2004} M. Albert and M.S. Paterson, \emph{Bounds for the growth rate of %meander numbers}, in Proceedings of the 16th Annual International %Conference on Formal Power Series and Algebraic Combinatorics, %University of British Columbia, (2004) pp. 39-47. %\bibitem{albert} M.H. Albert, M.S. Paterson, \emph{Bounds for the growth rate %of meander numbers}, Journal of Combinatorial Theory, Series A 112 %(2005), pp. 250-262. %\bibitem{arnold} V.I. Arnold, \emph{The branched covering of CP2 $\rightarrow$ S4, hyperbolicity and projective topology}, %Siberian Math. J. 29, (1988), pp. 717-726 (translated from Sibirskii %Matematicheskii Zhurnal 29:(36) (1988)). %\bibitem{bacher} R. Bacher, \emph{Meander Algebras}, prepublication de l'Institut %Fourier 478, (1999). %\bibitem{bacherEmail} R. Bacher, (private communication), 2006. %\bibitem{Bleher} P. Bleher, A.R, Random Matrix Models and Their Applications. %\bibitem{barraud} %J. Barraud, A. Panayotopoulos and P. Tsikouras, \emph{Properties of closed meanders}, %Ars Combinatoria 67 (2003), 189-197. \bibitem{bobier} B. Bobier, J. Sawada, \emph{A fast algorithm to generate open meandric sequences and meanders}, Transactions on Algorithms, Vol. 6 No. 2 (2010) 12 pages. \bibitem{diFrancesco} P. Di Francesco, O. Golinelli and E. Guitter, \emph{Meanders: a direct enumeration approach}, Nuc. Phys. B 482, (1996), pp. 497-535. %\bibitem{diFrancesco2} P. Di Francesco, O. Golinelli and E. Guitter, \emph{Meander, Folding, and Arch Statistics}, Mathl. Comput. Modelling 26:(9), (1997), pp. 97-147. %\bibitem{diFrancesco3} P. Di Francesco, O. Golinelli and E. Guitter, \emph{Meanders: exact asymptotics}, Nuc. Phys. B 570, (2000), pp. 699-712. %\bibitem{dorn} F. Dorn, E. Penninkx, H. Bodlaender, and F.V. Fomin, \emph{Efficient %exact algorithms on planar graphs: Exploiting sphere cut branch %decompositions}, in Proceedings of the 13th Annual European %Symposium on Algorithms (ESA 2005), vol. 3669 of LNCS, Springer, %Berlin, (2005), pp. 95-106. \bibitem{franz} R. Franz and B. Earnshaw, \emph{A constructive enumeration of meanders}, Annals of Combinatorics 6:(1) (2002), pp. 7-17. \bibitem{hoffmann} K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. Tarjan, \emph{Sorting Jordan sequences in linear time using level-linked search trees}, Information and Control, 68 (1986), pp. 170-184. %\bibitem{jensen} I. Jensen, \emph{A transfer matrix approach to the enumeration of %plane meanders}, J. Phys. A 33:(24) (2000), pp. 5953-5963. \bibitem{knuth} D. E. Knuth, The Art of Computer Programming, Volume 4: Generating All Trees; History of Combinationatorial Generation,, Fascicle 4, Addison-Wesley, February 2006, 150 pages. \bibitem{ko} K.H. Ko and L. Smolisky, \emph{A combinatorial matrix in 3-manifold theory}, Pacific J. Math. 149 (1991) pp. 3190336. \bibitem{koehler} J. E. Koehler, \emph{Folding a strip of stamps}, Journal of Combinatorial Theory, 5 (1968), pp. 135-152. %\bibitem{laCroix} M.A. La Croix, \emph{Approaches to the Enumerative Theory of %Meanders}, Master's Essay, University of Waterloo, Canada, (2003). \bibitem{lando} S. K. Lando and A. K. Zvonkin, \emph{Plane and projective meanders}, Theoretical Computer Science 11:(2) (1993), pp. 117-144. \bibitem{lausch} S. Lausch, \emph{Generating Some Restricted Classes of Permutations}, Master's Thesis, University of Victoria, Canada, 1999. %\bibitem{sawada} R. Li and J. Sawada, \emph{Gray codes for reflectable languages}, % Information Processing Letters, Vol. 209 No. 5 (2009) 296-300. %\bibitem{lunnon} W. Lunnon, \emph{A mapfolding problem}, Math. of Computation 22 %(1968), pp. 193-199. %\bibitem{pana} %A. Panayotopoulos and P. Tsikouras, \emph{Meanders and Motzkin words}, J. Integer Seq. 7 (2004) Article 04.1.2, 10 pages. %\bibitem{poincar} H. Poincar\'{e}, \emph{Sur un theorem de geometrie}, Rend. Circ. Mat. Palermo 33 (1912). %\bibitem{reeds} J. Reeds and L. Shepp, \emph{An upper bound on the meander constant}, %preprint (1999). \bibitem{sloane} N. Sloane, \emph{The on-line encyclopedia of integer sequences,} \url{http://oeis.org/}, IDs: A000136, A001011, A000682, A000560, A005316, A077055, (2009). \bibitem{touchard} J. Touchard, \emph{Contributions \`{a} l'\'{e}tude du probl\`{e}me des timbres postes}, Canad. J. Math., 2 (1950), pp. 385-398. %\bibitem{tsang} J. Tsang, personal communication, November 2008. %\end{enumerate} \end{thebibliography} \begin{comment} \begin{center} {\bf APPENDIX: CODE} \end{center} \scriptsize \begin{verbatim} #include #define MAX(a,b) (a > b) ? a : b #define MAX_ORDER 99 typedef struct List { struct Interval *head, *tail; } List; typedef struct Node { struct List L, R; struct Interval *unwind; char side; } Node; typedef struct Interval { int v1, v2; struct Interval *prev, *next, *prev_perm, *next_perm; Node* node_ptr; } Interval; //-------------------------------------------------------------------------------- // GLOBAL VARIABLES int n, a[MAX_ORDER], total=0, MEANDER=0, SEMI=0, STAMP=0, UNLABELED=0, SYM_SEMI=0; Interval interval[MAX_ORDER], *perm_head; Node node[MAX_ORDER]; //-------------------------------------------------------------------------------- void Print() { int j=0, one=0; Interval *I; I=perm_head; while(I != NULL) { a[++j] = I->v2; if (a[j] == 1) one = 1; else if (UNLABELED && a[j] == n && one == 0) return; I = I->next_perm; } for (j=1; j<=n; j++) { if (a[j] < n - a[n-j+1] + 1) break; if (UNLABELED && a[j] > n - a[n-j+1] + 1) return; } for (j=1; j<=n; j++) printf("%d ", a[j]); printf("\n"); total++; } //-------------------------------------------------------------------------------- void InsertInterval(Interval *I, List *L, int v1, int v2, Interval *P, Interval *N, Node* N_ptr) { if (P != NULL) P->next = I; else L->head = I; if (N != NULL) N->prev = I; else L->tail = I; I->v1 = v1; I->v2 = v2; I->prev = P; I->next = N; I->node_ptr = N_ptr; } void RemoveInterval(Interval *I, List *L) { Interval *P, *N; P = I->prev; N = I->next; if (N == NULL) L->tail = P; else N->prev = NULL; if (P == NULL) L->head = N; else P->next = NULL; } void MoveInterval(Interval *I, List *L1, List *L2, Interval *P, Interval *N, Node* N_ptr) { RemoveInterval(I, L1); InsertInterval(I, L2, I->v1, I->v2, P, N, N_ptr); } //-------------------------------------------------------------------------------- void SetUnwind(Node* Z, Interval *unwind, int side) { Z->unwind = unwind; Z->side = side; } void SetNodeLists(Node* Z, Interval *l_head, Interval *l_tail, Interval *r_head, Interval *r_tail) { if (l_head == NULL || l_tail == NULL) l_head = l_tail = NULL; if (r_head == NULL || r_tail == NULL) r_head = r_tail = NULL; Z->L.head = l_head; Z->L.tail = l_tail; Z->R.head = r_head; Z->R.tail= r_tail; } //-------------------------------------------------------------------------------- void UpdatePerm(int t, Interval* I) { Interval *P, *N, *I1, *I2; I1 = &interval[2*t-1]; I2 = &interval[2*t]; P = I->prev_perm; N = I->next_perm; I1->prev_perm = P; I1->next_perm = I2; I2->prev_perm = I1; I2->next_perm = N; if (P != NULL) P->next_perm = I1; else perm_head = I1; if (N != NULL) N->prev_perm = I2; } void RestorePerm(Interval *I) { Interval *P, *N; P = I->prev_perm; N = I->next_perm; if (P != NULL) P->next_perm = I; else perm_head = I; if (N != NULL) N->prev_perm = I; } //-------------------------------------------------------------------------------- void Gen(int t, Node* X, int w) { Node *Y, *X1, *X2; Interval *I, *I1, *I2, *P, *N, *old_unwind; int unwind_visited, side; char old_side; if (t > n) Print(); else { // NEW NODES AND INTERVALS X1 = &node[2*t-1]; X2 = &node[2*t]; I1 = &interval[2*t-1]; I2 = &interval[2*t]; I = X->L.head; // OPTIMIZATION FOR MEANDERS if (MEANDER && n-t <= w) I = X->unwind; // VISIT LIST L (side=1), THEN LIST R (side=2) FROM NODE X for (side=1; side<=2; side++) { unwind_visited = 0; while (I != NULL) { N = I->next; P = I->prev; Y = I->node_ptr; old_unwind = Y->unwind; old_side = Y->side; SetUnwind(X1, NULL, '-'); SetUnwind(X2, NULL, '-'); // UPDATE NEXT NODE Y and CREATE 2 NEW NODES X1 and X2 if (side == 1) { if (STAMP && I->v1 == 0) { if (Y->L.head != NULL) SetNodeLists(Y, NULL, NULL, Y->L.head, Y->L.tail); MoveInterval(X->R.tail, &X->R, &Y->R, Y->R.tail, NULL, X1); } else if (X->unwind == I) unwind_visited = 1; else if (unwind_visited == 1 || X->side == 'r') { SetUnwind(Y, I1, 'l'); SetUnwind(X1, X->unwind, X->side); } else { SetUnwind(Y, I2, 'r'); SetUnwind(X2, X->unwind, 'r'); } SetNodeLists(X1, X->L.head, P, X->R.head, X->R.tail); SetNodeLists(X2, NULL, NULL, N, X->L.tail); } else { if (STAMP && I->v2 == MAX_VAL) { if (Y->R.head != NULL) SetNodeLists(Y, Y->R.head, Y->R.tail, NULL, NULL); MoveInterval(X->L.head, &X->L, &Y->L, NULL, Y->L.head, X2); } else if (X->unwind == I) { unwind_visited = 1; if ((MEANDER || SEMI) && w == 0) SetUnwind(Y, I2, 'r'); } else if (unwind_visited == 1) { SetUnwind(Y, I1, 'l'); SetUnwind(X1, X->unwind, 'l'); } else { SetUnwind(Y, I2, 'r'); SetUnwind(X2, X->unwind, X->side); } SetNodeLists(X1, X->R.head, P, NULL, NULL); SetNodeLists(X2, X->L.head, X->L.tail, N, X->R.tail); } // INSERT NEW INTERVALS InsertInterval(I1, &Y->L, I->v1, t, Y->L.tail, NULL, X1); InsertInterval(I2, &Y->R, t, I->v2, NULL, Y->R.head, X2); // REMOVE CURRENT INTERVAL if (N != NULL) N->prev = NULL; if (P != NULL) P->next = NULL; // UPDATE THE PERMUTATION UpdatePerm(t,I); // MAKE RECURSIVE CALLS if (STAMP && (I->v1 == 0 || I->v2 == MAX_VAL) Gen(t+1, Y, 0); else if (X->unwind == I) Gen(t+1, Y, MAX(0,w-1)); else Gen(t+1, Y, w+1); // RESTORE DATA STRUCTURES RestorePerm(I); if (N != NULL) N->prev = I; if (P != NULL) P->next = I; RemoveInterval(I1, &Y->L); RemoveInterval(I2, &Y->R); SetUnwind(Y, old_unwind, old_side); if (STAMP && I->v1 == 0) MoveInterval(Y->R.tail, &Y->R, &X->R, X->R.tail, NULL, Y); if (STAMP && I->v2 == MAX_VAL) MoveInterval(Y->L.head, &Y->L, &X->L, NULL, X->L.head, Y); I = N; // NEXT INTERVAL if (MEANDER && n-t <= w) return; } if (SYM_SEMI && t == 2) return; I = X->R.head; } } } //-------------------------------------------------------------------------------- int main(int argc, char *argv[]) { int i, type; if (argc !=3) { printf("Usage: a.out n type\n"); return; } n = atoi(argv[1]); type = atoi(argv[2]); if (type == 1) MEANDER = 1; // SLOANE A005316 if (type == 2) SEMI = 1; // SLOANE A000682 if (type == 3) STAMP = 1; // SLOANE A000136 if (type == 4) UNLABELED = STAMP = 1; // SLOANE A001011 if (type == 5) SYM_SEMI = 1; // SLOANE A000560 // INITIALIZE NODES for (i=0; i<=2*n; i++) { node[i].L.head = node[i].L.tail = NULL; node[i].R.head = node[i].R.tail = NULL; node[i].unwind = NULL; node[i].side = '-'; } SetUnwind(&node[0], &interval[2], 'r'); InsertInterval(&interval[1], &node[0].L, 0, 1, NULL, NULL, &node[2]); InsertInterval(&interval[2], &node[0].R, 1, MAX_ORDER, NULL, NULL, &node[1]); perm_head = &interval[1]; interval[1].prev_perm = NULL; interval[1].next_perm = &interval[2]; interval[2].prev_perm = &interval[1]; interval[2].next_perm = NULL; Gen(2, &node[0], 0); printf("Total = %d\n", total); } \end{verbatim} \end{comment} \end{document}