--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/content/blog/2015/12/permutation-patterns.html Thu Dec 10 19:53:35 2015 +0000
@@ -0,0 +1,349 @@
+ {% extends "_post.html" %}
+
+ {% load mathjax %}
+
+ {% hyde
+ title: "What the Hell are Permutation Patterns?"
+ snip: "A short introduction."
+ created: 2015-12-10 19:55:00
+ %}
+
+ {% block article %}
+
+I'm currently in the Mathematical Programming class at Reykjavík University and
+we're working with permutations and patterns. They're really simple to
+understand once they're explained to you, but after searching around online
+I haven't found a nice explanation for humans, so here you go.
+
+None of this is new research, I just want to summarize things so other people
+can understand it without having to shovel through the internet trying to piece
+together a bunch of terse definitions. All of this is covered in more detail on
+Wikipedia, as well as in [Combinatorics of Permutations][book] by Miklós Bóna
+(and many other places).
+
+[book]: http://www.amazon.com/dp/1439850518/?tag=stelos-20
+
+[TOC]
+
+## Permutations (Non-Mathy)
+
+If you've used permutations in a programming language you can probably skip this
+section.
+
+If you're interested in programming and/or math you've probably heard the term
+"permutations" before. It's typically explained to be something like "different
+ways to order a collection of objects".
+
+The key word here is "order" -- permutations are all about ordering.
+
+### Basics
+
+Let's look at an example. If you have a list of three cats:
+
+* Scruffy
+* Boots
+* Patches
+
+How many different ways can you list them out? Order matters, and you're also
+not allowed to repeat a cat (no cloning here).
+
+ 1 2 3 4 5 6
+ Scruffy Scruffy Patches Patches Boots Boots
+ Boots Patches Scruffy Boots Scruffy Patches
+ Patches Boots Boots Scruffy Patches Scruffy
+
+
+So there are six permutations. Simple enough. Let's think about the edge
+cases. How many ways can you permute one cat? Just one:
+
+ 1
+ Scruffy
+
+Something a bit tougher: how many ways can you permute *zero* cats? This seems
+a bit weird, but if you phrase it as "how many ways can you order a list of zero
+objects" you can convince yourself the answer is one as well (the single
+permutation is "the empty list").
+
+We don't want to have to count out the number of permutations by hand every
+time, so it would be nice to have a formula. If we have a list of *n* things,
+how many different permutations can we come up with?
+
+We can start by filling the first slot with any item we want, so we have \\(n\\)
+options. Then for each of those choices we pick something to go in the next
+slot from the \\(n - 1\\) things that are left. We can keep going all the way
+down until we're at the last slot, by which point we've only got one thing left,
+so we get:
+
+{% filter mathjax %}
+ (n)(n - 1)(n - 2)...(1)
+{% endfilter %}
+
+Which is just the [factorial][] of \\(n\\). For our three cats we have:
+
+{% filter mathjax %}
+ (3)(3 - 1)(3 - 2) = 3 \cdot 2 \cdot 1 = 6
+{% endfilter %}
+
+So now we know that:
+
+{% filter mathjax %}
+ \operatorname{number-of-permutations}(\mathit{items}) =
+ \mathit{items}!
+{% endfilter %}
+
+[factorial]: https://en.wikipedia.org/wiki/Factorial
+
+### Restricting Slots
+
+Things start to get more interesting when we start to restrict the number of
+slots. For example, we can ask "how many different lists of three items can we
+take from a group of five items?"
+
+I'm going to stop using cat names now because it's getting painful to type, so
+let's just use letters. Our five items will be:
+
+ a, b, c, d, e
+
+How many different three-length lists can we produce?
+
+ (a, b, c) (a, b, d) (a, b, e) (a, c, b) (a, c, d) (a, c, e)
+ (a, d, b) (a, d, c) (a, d, e) (a, e, b) (a, e, c) (a, e, d)
+
+ (b, a, c) (b, a, d) (b, a, e) (b, c, a) (b, c, d) (b, c, e)
+ (b, d, a) (b, d, c) (b, d, e) (b, e, a) (b, e, c) (b, e, d)
+
+ (c, a, b) (c, a, d) (c, a, e) (c, b, a) (c, b, d) (c, b, e)
+ (c, d, a) (c, d, b) (c, d, e) (c, e, a) (c, e, b) (c, e, d)
+
+ (d, a, b) (d, a, c) (d, a, e) (d, b, a) (d, b, c) (d, b, e)
+ (d, c, a) (d, c, b) (d, c, e) (d, e, a) (d, e, b) (d, e, c)
+
+ (e, a, b) (e, a, c) (e, a, d) (e, b, a) (e, b, c) (e, b, d)
+ (e, c, a) (e, c, b) (e, c, d) (e, d, a) (e, d, b) (e, d, c)
+
+You can see how working with numerical formulas would be a lot nicer than
+listing all those out by hand and counting them. The formula to tell us the
+number is:
+
+{% filter mathjax %}
+ \operatorname{number-of-permutations}(\mathit{items}, \mathit{slots}) =
+ \frac
+ {\mathit{items}!}
+ {(\mathit{items} - \mathit{slots})!}
+{% endfilter %}
+
+So in this example we have:
+
+{% filter mathjax %}
+ \frac
+ {\mathit{items}!}
+ {(\mathit{items} - \mathit{slots})!}
+ =
+ \frac{5!}{(5 - 3)!} =
+ \frac{5!}{2!} =
+ \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} =
+ \frac{120}{2} =
+ 60
+{% endfilter %}
+
+Which is correct (feel free to count them by hand if you're skeptical).
+
+This formula continues to work when the number slots is equal to the number of
+elements (like in our cat example). If \\(n = slots = items\\) then:
+
+{% filter mathjax %}
+ \frac
+ {\mathit{items}!}
+ {(\mathit{items} - \mathit{slots})!}
+ =
+ \frac
+ {\mathit{n}!}
+ {(\mathit{n} - \mathit{n})!}
+ =
+ \frac
+ {\mathit{n}!}
+ {0!}
+ =
+ \frac
+ {\mathit{n}!}
+ {1}
+ =
+ \mathit{n}!
+{% endfilter %}
+
+Remember that \\(0!\\) is 1, not 0 as you might first expect. Feel free to plug
+in the edge cases we talked about before (zero- and one-length permutations) and
+make sure they work.
+
+## Permutations (Mathy)
+
+That was a pretty standard introduction to permutations, and it's about as far
+as most basic programming/math books go at first (they'll also talk about
+"combinations", which are something else that we don't care about right now).
+But if we want to start looking at permutations more closely we need to add
+a few additional rules.
+
+So far we've been talking about permutations of arbitrary objects, like cats,
+letters, or playing cards. From here on out we're going to restrict ourselves
+a bit more: we'll only consider lists of positive integers. This is important
+because integers can be compared. We can't say that Scruffy is "less than" or
+"greater than" Boots, but we *can* say that 15 is less than 16.
+
+Notice that we're not including the number zero. When we say "show me all
+standard permutations of length 3" we mean:
+
+ 1 2 3
+ 1 3 2
+ 2 1 3
+ 2 3 1
+ 3 1 1
+ 3 2 1
+
+Sorry programmers, permutation people like to count from one.
+
+You'll notice that I wrote out the permutations above each on their own line,
+with the numbers just listed out. This is called "one-line notation".
+Sometimes people drop the spaces in between the numbers (e.g. `1 2 3` becomes
+`123`) if all the numbers are single digits and they feel like being annoying.
+
+There's also a "two-line notation" that we won't use here, check out the
+Wikipedia page at the end of the post for more.
+
+### Standard/Classical Permutations
+
+Another term we'll use is "standard permutations" or "classical patterns" (don't
+worry about the word "patterns" too much yet). This just means they contain all
+the numbers 1 to \\(n\\) with no missing numbers. So `3 2 4 1` is a standard
+permutation (of length 4), but `1 902 23232 5` is not.
+
+### Subwords/Subsequences
+
+One more bit of terminology before we get to the meat of the post. A "subword"
+of a permutation is all the different lists we can get by dropping none, some,
+or all of the items, *without changing the order*. For example, the sublists of
+`9 3 1 4` are:
+
+ dropping no items
+ (9 3 1 4)
+
+ dropping one item
+ ( 3 1 4)
+ (9 1 4)
+ (9 3 4)
+ (9 3 1 )
+
+ dropping two items
+ ( 1 4)
+ (9 4)
+ (9 3 )
+ ( 3 4)
+ (9 1 )
+ ( 3 1 )
+
+ dropping three items
+ (9 )
+ ( 3 )
+ ( 1 )
+ ( 4)
+
+ dropping four items
+ ( )
+
+You will also hear these called "subsequences", but this is way too confusing
+because `subsequence` in a programming language almost always means
+a *consecutive* portion of a list, so I'm going to stick with "subwords".
+
+## Permutation Patterns
+
+Hold onto your hats, things are about to get intense.
+
+We say that one permutation X **contains** another permutation Y if one of the
+subwords of X has **the same length and relative order** as Y. I know that's
+confusing and not at all clear, so let's take an example.
+
+Let X be the permutation `1 4 3 2`. Let Y be `1 2`. Does X contain Y?
+
+If we look at Y's elements, we see that it starts with the lowest element and
+then goes to the highest element. Is there some subword of X, of length 2, that
+does the same thing? Sure: `1 4` is a subword of X, has length 2, and starts at
+the lowest element then goes to the highest.
+
+Note that our subword has a `4` in it, but Y only has `1` and `2`. This is the
+most confusing part about permutation patterns: we don't care about the actual
+numbers themselves -- we only care about the relationships between the numbers.
+
+Another example. Let X be `1 4 3 2`. Let Y be `2 1`. Does X contain Y? Try
+this one on your own before reading on.
+
+Y is still two elements long, but now it starts at the highest element and goes
+the lowest. The subword we used in the last example (`1 4`) doesn't work here,
+because it starts low and goes high (the opposite of what we want). But `4 3`
+is another subword of X, and that *does* match, so X does contain Y. Note that
+`4 2` would also fit here (remember: subwords don't have to be consecutive!).
+
+Let's try something more interesting. Let X still be `1 4 3 2`, but let's make
+Y `1 2 3`. Does X contain Y?
+
+This one is a little trickier. The order of Y is that it starts at the lowest
+element, then it goes to the middle one, then finally it goes to the highest
+element. Let's look at the subwords of X that are length 3:
+
+ 1 4 3
+ 1 4 2
+ 1 3 2
+ 4 3 2
+
+Do any of those have the same relative ordering as Y? No! None of them start
+at the lowest, go to the middle, then go to the highest. So this time X does
+not contain Y, so we say that X **avoids** Y.
+
+## So What?
+
+So now that we know what "X contains Y" and "X avoids Y" mean, what can we use
+this stuff for? I'm not an expert, but I can give you a few examples to whet
+your apetite.
+
+Consider a permutation X that avoids `2 1`. What might X look like?
+
+Well the empty permutation and any permutation with only one element certainly
+avoid `2 1` (they don't have any subwords of the correct length at all). What
+about longer ones?
+
+If X avoids `2 1`, then for any two elements in it, the leftmost element must be
+smaller than the rightmost one (otherwise it would *contain* `2 1`). This means
+that all the elements must be getting bigger as you go to the right, or to put
+it another way: the permutation must be in sorted order!
+
+Similarly, if X avoids `1 2` then it must be in *reverse* sorted order. Poke at
+this for a minute and convince yourself it must be true. Make sure to consider
+edge cases like the empty permutation and single-element permutations.
+
+Another example comes from Knuth: if a permutation contains `2 3 1` it cannot be
+sorted by a stack in a single pass. Remember: the numbers in the matching
+subword don't have to be consecutive, and they don't have to match the exact
+numerals, only the relative order matters. `66 1 99 2 33` contains `2 3 1`
+because the subword `66 99 33` has the same relative order (and so `66 1 99
+2 33` cannot be sorted by a stack in a single pass). This is probably not
+intuitively obvious, so for further explanation check out Wikipedia, or [this
+paper][paper] coincidentally by my professor, or even Knuth's [book][taocp]
+itself.
+
+[paper]: http://www.dmtcs.org/pdfpapers/dmAR0153.pdf
+[taocp]: http://www.amazon.com/dp/0201896834/?tag=stelos-20
+
+## Further Information
+
+This was a really quick introduction. I glossed over a bunch of things (like
+defining a permutation as a mapping of elements of a set to themselves, the
+identity permutation, etc). If you want to dive in more, you can check out
+Wikipedia:
+
+* [Permutations](https://en.wikipedia.org/wiki/Permutation)
+* [Permutation Patterns](https://en.wikipedia.org/wiki/Permutation_pattern)
+
+Or go all-in and grab a copy of [Combinatorics of Permutations][book].
+
+I'm also planning on doing another post like this about mesh patterns, which are
+a slightly more general/powerful version of these basic patterns.
+
+ {% endblock article %}