#+TITLE: Cyclic poetry
#+AUTHOR: Dylan Holmes
#+DATE: 2017/May/29
#+SETUPFILE: ../../logical/org/template-export-setup-2.org
#+INCLUDE: ../../logical/org/template-include.org
#+BIND: org-html-postamble ""
#+OPTIONS: title:nil toc:nil
# Sestinas and cyclic permutations
# Cyclic poetry
# #+TITLE: Sestinas and cyclic permutations
# #+toc: 2
Certain fixed-verse poetic forms have a beautiful mathematical
structure to them. This article is about the repetitive structure of
the /sestina/, a thirty-nine line form in which certain words reappear
throughout in different combinations. Consider this example by
Elizabeth Bishop:
#+BEGIN_VERSE
*Sestina*, Elizabeth Bishop.
September rain falls on the house.
In the failing light, the old grandmother
sits in the kitchen with the child
beside the Little Marvel Stove,
reading the jokes from the almanac,
laughing and talking to hide her tears.
She thinks that her equinoctial tears
and the rain that beats on the roof of the house
were both foretold by the almanac,
but only known to a grandmother.
The iron kettle sings on the stove.
She cuts some bread and says to the child,
It's time for tea now; but the child
is watching the teakettle's small hard tears
dance like mad on the hot black stove,
the way the rain must dance on the house.
Tidying up, the old grandmother
hangs up the clever almanac
on its string. Birdlike, the almanac
hovers half open above the child,
hovers above the old grandmother
and her teacup full of dark brown tears.
She shivers and says she thinks the house
feels chilly, and puts more wood in the stove.
It was to be, says the Marvel Stove.
I know what I know, says the almanac.
With crayons the child draws a rigid house
and a winding pathway. Then the child
puts in a man with buttons like tears
and shows it proudly to the grandmother.
But secretly, while the grandmother
busies herself about the stove,
the little moons fall down like tears
from between the pages of the almanac
into the flower bed the child
has carefully placed in the front of the house.
Time to plant tears, says the almanac.
The grandmother sings to the marvelous stove
and the child draws another inscrutable house.
#+END_VERSE
** The cyclic structure
As you can see, the form of the sestina relies on an inventory of six
chosen words at the end of each line---in this poem, the words are
1. house
2. grandmother
3. child
4. stove
5. almanac
6. tears
A sestina contains six stanzas of six lines each. The six chosen words
appear in a different order at the end of the lines in each stanza;
they are /permuted/. In particular, the order is:
#+BEGIN_QUOTE
ABCDEF, FAEBDC, CFDABE, ECBFAD, DEACFB, BDFECA
#+END_QUOTE
As it turns out, the repeated reorderings form a particularly elegant
mathematical pattern: not only are they permuations, but they arise
from repeated applications of a single /cyclic permutation/.
A cyclic permutation can be described in several ways. One way is to
describe the trajectory of all the parts;
$$1\rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow
6 \rightarrow 1$$
which here means that with each application of the cyclic permutation,
the first word becomes the second, the second becomes the fourth, the
fourth becomes the fifth, etc. To determine the order of the next
stanza, simply apply this rearrangement rule to the words as they are
ordered in your current stanza.
Another way is to describe the cyclic permutation as a permutation
matrix \(P\):
\(\, \begin{bmatrix}
\cdot&\cdot&\cdot&\cdot&\cdot&1\\
1&\cdot&\cdot&\cdot&\cdot&\cdot\\
\cdot&\cdot&\cdot&\cdot&1&\cdot\\
\cdot&1&\cdot&\cdot&\cdot&\cdot\\
\cdot&\cdot&\cdot&1&\cdot&\cdot\\
\cdot&\cdot&1&\cdot&\cdot&\cdot\\
\end{bmatrix}^k\begin{bmatrix}
\text{house}\\
\text{grandmother}\\
\text{child}\\
\text{stove}\\
\text{almanac}\\
\text{tears}\\
\end{bmatrix}
\)
Representing the transformation as the matrix \(P\) has three nice
properties: first, rows of the matrix (top to bottom) correspond to
lines in the stanza, and columns (left to right) correspond to
words. Hence, to know what word should be in line $i$ of the next
stanza, you look at row $i$ and see which column $j$ has a 1 in
it. Second, this row/column interpretation applies to the /powers/ of
this matrix, too; the successive powers of this matrix tell you where
the original words go in subsequent stanzas. The first stanza is
\(k=0\) and so on for \(k=0,1,2,3,4,5\). Third, if you multiply
\(P^k\) by the vector of words as shown here, you will get a vector
with the words in the appropriate order for the \(k\)th stanza (again,
where \(k\) starts at \(k=0\)).
Another representation is to use a stacked /two-line representation/,
where you list the numbers in their original order and then write the
destination of each number beneath it:
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6\\
2 & 4 & 6 & 5 & 3 & 1\\
\end{pmatrix}
Swapping the order of these top-bottom pairs, you can write an
equivalent two-line representation of the permutation which more
clearly shows the cyclic structure. (In this arrangement, the bottom
of each entry matches the top of the next entry):
\begin{pmatrix}
1&2&4&\color{red} 5&3&6 \\
2&4&\color{red}5&3&6&1 \\
\end{pmatrix}
** Properties of cyclic permutations
Each of these representations has its own advantages. The trajectory
notation helps you see that a word will return to its original
position after exactly six movements---to see this, just trace what
happens to any one entry as you move it successively. (Hence the
reason why there are exactly six stanzas in a sestina; if we continued
the pattern to a seventh stanza, we'd arrive at the original order
which we've seen before.)
The permutation matrix \(P\) is useful because it captures the spatial
arrangement of poetic lines in order from top to bottom on paper,
making it easier to quickly look up which word goes in each line in
order. You can read the rows to see what word you should put in each
line, or read the columns to see in which line each word goes. You can
also clearly see that the reordering is a permutation, because there
is exactly one 1 in each row and in each column. Moreover, you can see
the "telescoping" structure of the rearrangement: the first two lines
of the next stanza will consist of the outermost lines of the current
stanza; the next two will be the almost-outermost lines; the final two
will consist of the two innermost lines.
# rather than emphasizing
# where the words go next (word-focused), it emphasizes what word you
# should put in each line (line-focused).
** The half-stanza
After six different combinations expressed in six stanzas, the
sestina's cycle is complete. Afterwards, the sestina concludes with a
"half-stanza", consisting of three lines with two of the keywords per
line.
As you can see with reference to the poem above, if the keywords were
originally written in order 123456, in the final half-stanza, they
appear in the order: 65/24/31.
We can write another matrix to express the order in which words occur
in the stanza:
\begin{bmatrix}
\cdot&\cdot&\cdot&\cdot&\cdot&1\\
\cdot&\cdot&\cdot&\cdot&1&\cdot\\
\cdot&1&\cdot&\cdot&\cdot&\cdot\\
\cdot&\cdot&\cdot&1&\cdot&\cdot\\
\cdot&\cdot&1&\cdot&\cdot&\cdot\\
1&\cdot&\cdot&\cdot&\cdot&\cdot\\
\end{bmatrix}
Though as far as I have found, this order is arbitrary and has no
special connection to the sestina permutation.
** The sestina form is a uniquely special permutation
You can think of the sestina as one member of a family of different
poetic forms, each based on a different cyclic permutation. For
example, you could make a variant kind of sestina using the
permutation \(1\rightarrow 2\rightarrow 3 \rightarrow 4 \rightarrow 5
\rightarrow 6 \rightarrow 1\) instead.
This raises the question: how unique is the standard sestina form?
Well, there are \(n!\) choices of permutation for a list of \(n\)
words. As for specifically /cyclic/ permutations, there are only
\((n-1)!\) of them[fn::You can see this in at least two ways. First,
imagine taking an arbitrary permutation and putting arrows in between
the elements as we did with the trajectory representation, for
example: \(2\rightarrow 4\rightarrow 1 \rightarrow 3\rightarrow
2\). This makes any permutation into a cyclic permutation. But because
in a cyclic representation, it doesn't matter which element you list
/first/, the permutations 2413, 4132, 1324, and 3241 all refer to the
same cyclic permutation. There are in general \(n\) starting points
for a cycle of \(n\) elements, all of which result in the same cyclic
permutation. So we divide out the duplicates by dividing by
\(n\). Another strategy is to argue recursively: if you have a cycle
of \(n\) elements, you can make a cycle of \(n+1\) elements by
inserting \(n+1\) anywhere into the cycle. There are \(n\) choices of
insertion point and each results in a different \(n+1\) cycle. The
base case is that for two elements, there is only one cyclic
permutation. ].
# Most of these permutations are not cyclic, however; for
# example, \(1\rightarrow 3 \rightarrow 4 \rightarrow 1,\; 2\rightarrow
# 5 \rightarrow 2\) is a non-cyclic permutation of five elements. To
# count the number of /cyclic/ permutations for \(n\) elements, we can
# reason recursively as follows:
# 1. A set of /two/ elements has exactly one cyclic permutation.
# 2. If you have a cyclic permutation of \(n\) elements, you can make a
# cycle for $\(n+1\) elements by inserting the number \(n+1\)
# anywhere in the cycle. There are \(n\) choices of insertion point
# in a cycle of \(n\) elements, and each insertion possibility makes
# a unique cycle.
# 3. So letting \(C_n\) represent the number
For a sestina, this means that there are \(5! = 120\) possible
permutations, each one of which gives its own variant sestina form.
However, as the matrix representation reveals, the standard sestina
form has a "telescoping" effect, where the outermost lines of the
previous stanza become the first two lines of the next stanza,
etc. This pattern, shown in the image below, is unique among all
permutations, at least with respect to the following defining traits:
1. The permutation is a "spiral"[fn::One way of defining this is that
the line numbers of the words that appear next to each other after
the permutation all add up to the same sum, 7. For example, after
one reordering, 123456 becomes 615243. 6+1 = 5+2 = 4+3.)], as shown
in the picture.
2. The permutation puts each word in a new place; no word keeps its
old position. [fn::This rules out other spirals such as 123456
becoming 16-25-34.]
3. The permutation moves from outside to inside. (Instead of 123456
becoming 435261).
# unique among all permutations (except for what I consider to be
# minor variations, such as deciding whether the last line comes
# first.)
#+CAPTION: [[https://en.wikipedia.org/wiki/Sestina#/media/File:Sestina_system_alt.svg][This inscrutable image]], borrowed from Wikipedia, shows the unique spiral nature of the standard sestina permutation. The vertical direction denotes the words in their original order 1,2,3,4,5,6; the filled black circles (1st, 2nd, 3rd) denote what order those words will be visited in the next stanza. In particular, following the spiral shows that in the next stanza, Word 6 is read first, then Word 1, then Word 5, then Word 2, etc.
[[../600px-Sestina_system_alt.svg.png]]
Brackets or parentheses are another way of representing this spiral
permutation process. If the six symbols below represent the six chosen
keywords of your sestina, then the transformation looks visually like:
#+BEGIN_HTML
[({})] → ][ )( }{
#+END_HTML
We can generalize this pattern to any number of keywords
(corresponding to an equal number of stanzas). I like to call these
the *cyclic spiral fixed verse forms*. Though I don't have a concise
way to express this pattern mathematically, I can express it fairly
succinctly as a LISP-like (Clojure) subroutine:
#+BEGIN_SRC clojure
(defn next-stanza [wordlist]
(if (< (count wordlist) 2)
wordlist
(concat [(last wordlist) (first wordlist)]
(recur (butlast (rest wordlist))))))
#+END_SRC
In detail: to reorder the words for the next round, start with the
list of words in their current order and an empty list of words for
their new order. Until you run out of words in the old list, take off
the last and first words. Write those words down on the new list.
# Of course, when the number of lines is odd, there will be a keyword
# exactly in the middle of the list. This word will not ever change
# position in subsequent stanzas, and so an odd-length sestina is a sort
# of degenerate case.
** Any-length sestinas and automata
# \(\begin{pmatrix}1&2&3&4&\ldots&n-3&n-2&n-1&n\\\end{pmatrix}\)
I note in passing a connection to automata theory. I had thought that
the parenthesis-like matching of this spiral pattern would make it
possible to use a kind of pushdown transducer to read in a list of
words and print them out in the proper sestina order. However, I don't
believe that this is possible for pushdown automata. Instead, here is
a different result: considering your sestina keywords to be part of an
alphabet \(\Sigma\), there is a /linear bounded transducer/ [fn:: A
linear bounded automaton (LBA) is a machine slightly more powerful
than a pushdown automaton and slightly less powerful than a Turing
machine: rather than an infinite amount of writeable tape, an LBA has
only an amount of tape proportional to the size of the input. Also, a
general note: any kind of automaton (Turing machine, pushdown
automaton, finite state machine) can be made into a /transducer/ by
equipping it with the ability to print symbols to a second, write-only
tape.] which reads the word and prints out the sestina rearrangement:
#+BEGIN_QUOTE
*Linear bounded transducer algorithm for performing sestina
permutations*
First, let's assume a convention about the input format and starting
state. The input is written onto a tape, with out-of-bounds symbols ■
in the two cells on either side of the input. The tape head begins at
the first input symbol.
1. Move tape head right.
2. If ■ is /not/ in the current cell, go to 1.
3. Move tape head left.
4. If ■ is in the current cell, halt.
5. Print the contents of the current cell.
6. Overwrite the current cell with ■.
7. Move tape head left.
8. If ■ is /not/ in the current cell, go to 7.
9. Move tape head right.
10. If ■ is in the current cell, halt.
11. Print the contents of the current cell.
12. Overwrite the current cell with ■.
13. Go to 1.
#+END_QUOTE
To confirm that this algorithm works, I have provided Python code for
simulating linear bounded transducers (including this one as an
example).
#+BEGIN_SRC python -i
stop = None # the "out of bounds" symbol
verbose_output = False
### DEFINING LINEAR BOUNDED AUTOMATA
### (they are like Turing machines with finite tape)
def read_cell(state) :
return state["tape_contents"][state["head"]]
def write_cell(state, symbol) :
state["tape_contents"][state["head"]] = symbol
def move_left(state) :
state["head"]-=1
def move_right(state) :
state["head"]+=1
def writeout(state, symbol) :
state["print"] += [symbol]
def writeout_current_cell(state) :
writeout(read_cell(state))
def halt(state) :
return -1
def LBA_initial_state(word) :
return {"tape_contents" :
[stop]*2 + list(word) + [stop]*2,
"head" : 1,
"print" : []}
def lba_process_instructions(state, instructions) :
## an "instruction" is a function that takes in the LBA's current
## state and which returns the instruction number to jump to
## next. If no number is provided, proceeds to the next
## instruction.
instruction_ptr = 0
while 1 :
if verbose_output :
print "ln "+str(instruction_ptr)+".\t current state:\t", state["tape_contents"]
ret = instructions[instruction_ptr](state)
if ret is None :
instruction_ptr += 1
elif ret == -1 :
return state["print"]
else :
instruction_ptr = ret
if instruction_ptr >= len(instructions) or instruction_ptr < 0 :
return "OUT OF BOUNDS EXCEPTION"
def lba_sestina(word) :
state = LBA_initial_state(word)
instructions = [
move_right,
lambda s : 0 if read_cell(s) != stop else None,
move_left,
lambda s : halt(s) if read_cell(s) == stop else None,
lambda s: writeout(s, read_cell(s)),
lambda s: write_cell(s, stop),
move_left,
lambda s : 6 if read_cell(s) != stop else None,
move_right,
lambda s : halt(s) if read_cell(s) == stop else None,
lambda s: writeout(s, read_cell(s)),
lambda s: write_cell(s, stop),
lambda s: 0
]
return lba_process_instructions(state, instructions)
bishop_words = ['house','grandmother','child','stove','almanac','tears']
w = bishop_words # alternatively, uncomment the next line
# w = "123456"
for i in range(6) :
print list(w)
w = lba_sestina(w)
#+END_SRC
# Instead, here is
# a different result: given that your sestina keywords are symbols in an
# alphabet \(\Sigma\), there is a /logarithmic-space/ transduction
# algorithm for printing out the words in their permuted order.
# 1. Initialize LEFT-BOUND, RIGHT-BOUND = 0
# 2. Until RIGHT-BOUND points to an empty input tape cell, increment
# RIGHT-BOUND.
# 3. Decrement RIGHT-BOUND.
# 4. If LEFT-BOUND > RIGHT-BOUND, halt. (Loop termination condition)
# 5. If LEFT-BOUND = RIGHT-BOUND, print the symbol at LEFT-BOUND then halt.
# 6. Print the symbol at RIGHT-BOUND. Print the symbol at LEFT-BOUND.
# 7. Increment LEFT-BOUND. Decrement RIGHT-BOUND.
# 8. Goto step 4.
