# HG changeset patch # User Steve Losh # Date 1449777215 0 # Node ID 47f9b4b91599ad48adc9a646f6963305ba0eedad # Parent c5f5f1d86f24197bf334aaf9d77b53f3f714a3b8 Permutation patterns diff -r c5f5f1d86f24 -r 47f9b4b91599 content/blog/2015/12/permutation-patterns.html --- /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 %} diff -r c5f5f1d86f24 -r 47f9b4b91599 custom/__init__.py diff -r c5f5f1d86f24 -r 47f9b4b91599 custom/templatetags/__init__.py diff -r c5f5f1d86f24 -r 47f9b4b91599 custom/templatetags/mathjax.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/custom/templatetags/mathjax.py Thu Dec 10 19:53:35 2015 +0000 @@ -0,0 +1,9 @@ +from django import template + +register = template.Library() + + +def mathjax(value): + return "
$$ " + value + " $$
" + +register.filter('mathjax', mathjax) diff -r c5f5f1d86f24 -r 47f9b4b91599 settings.py --- a/settings.py Mon Nov 30 16:09:10 2015 +0000 +++ b/settings.py Thu Dec 10 19:53:35 2015 +0000 @@ -111,4 +111,5 @@ INSTALLED_APPS = ( 'hydeengine', 'django.contrib.webdesign', + 'custom', )