table of the numbers<\/a> one to hundred to populate the table. The factorial function gets big fast!<\/p>\n0! = 1
\n1! = 1
\n2! = 2
\n3! = 6
\n4! = 24
\n5! = 120
\n6! = 720
\n7! = 5,040
\n8! = 40,320
\n9! = 362,880
\n10! =3,628,800
\n11! = 39,916,800
\n12! = 479,001,600<\/p>\n
Combinations<\/h2>\n
Combinations assume there is a set of (n)<\/code> distinct elements, and you want to get the number of subsets you can pull from this set. There is no concern with exactly what elements go in a particular subset, just the count. The order is not important.<\/p>\nOne common notation for this, though not the only notation, is nCr<\/code> read as Set of (n) things, Choose (r) of them.<\/em> Notice that (0 \u2264 r \u2264 n)<\/code>, and that you can choose an empty set. Given a set, the number of subsets in it is 2n<\/em> ; For example, {a, b, c}<\/em> has subsets {}<\/em>, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}<\/em> for total count of 8.<\/p>\nI\u2019ve never understood the term ‘combination locks’ when the order of the numbers that you put into it is very important. Perhaps traditional mechanical security features were not designed by mathematicians.<\/p>\n
Permutations<\/h2>\n
Permutations also assume there is a set of (n)<\/code> distinct elements, and the goal is to get the number of sequences from this set in any order. However, in this case, the order does matter; (a, b, c)<\/em> is not the same permutation as (c, b, a)<\/em>.<\/p>\nDerangements<\/h2>\n
To be honest, I just think that the term ‘derangement’ is really cool. Given two sequences of the same length and with the same data elements, one is a derangement of the other when the data elements do not appear in the same sequence position in the two sequences. For example, (a, b, c)<\/em> is not a derangement of (c, b, a)<\/em> because the data element ‘b’<\/em> is in the second position in both sequences. Instead, there are two derangements, (c, a, b)<\/em> and (b, c, a)<\/em>.<\/p>\nA derangement can also be called a permutation with no fixed points. The two notations for derangement of (n)<\/code> elements are either !(n)<\/code> or D(n)<\/code>. I find the first one with the leading exclamation point to be a bad choice. It looks too much like a factorial.<\/p>\nThe number of derangements of a set with (n)<\/code> distinct elements is given by the recursive formula : D(n) = (n-1)[D(n-1) + D(n-2)]<\/code>. If you know D(1) = 0<\/code> and D(2) = 1<\/code>, you can generate subsequent values for D(n)<\/code>. Or you would prefer : D(n) = n D(n-1) + (-1)n<\/sup><\/code>?<\/p>\nObviously, the derangements will be fewer in number than the original permutation.<\/p>\n
Derangements of n<\/code> Elements<\/p>\nD(n)
\nD(0) = 1
\nD(1) = 0
\nD(2) = 1
\nD(3) = 2
\nD(4) = 9
\nD(5) = 44
\nD(6) = 265
\nD(7) = 1,854
\nD(8) = 14,833
\nD(9) = 133,496
\nD(10) = 1,334,961
\nD(11) = 14,684,570
\nD(12) = 76,214,841<\/p>\n
Derangements provide a way to make sure that everyone gets a fair shake when making job assignments. Nobody is stuck in the same job from one assignment cycle to the next. The idea is that eventually, all your personnel would be assigned to every job, but you don\u2019t necessarily know in which assignment cycle any employee will get a particular job.<\/p>\n
My favorite use for derangement is when an office does a \u201cSecret Santa\u201d Christmas gift program. If you have never had one of these, the idea is that everyone brings a wrapped gift to work. The gift-giver then picks the name of another employee randomly, and the second employee becomes the recipient. The first rule is that you don\u2019t give a gift to yourself. A second rule is that you\u2019re not supposed to be able to figure out who is the gift giver.<\/p>\n
Gift givers are the set, and the recipients are supposed to be an unpredictable derangement. You try doing this by drawing one name at a time, and very quickly a wind up with a situation where only a few possible derangements are left. So much for maintaining secrecy. To get an idea how this works, look at the prior example, with only three data elements in the original permutation. You really need to pick your derangement all at once.<\/p>\n
A cute trick for doing this in the real world is to put everybody\u2019s name on a card twice, once on the top and once on the bottom. Shuffle the card deck. Cut the cards in half, leaving the top and bottom halves paired. Take the top half-card from the top halves deck and put it on the bottom of the same top halves deck. Now draw the pairs of cards from the decks, assembling the tops and bottoms to make a new card. The result will be a new card deck with an unpredictable derangement.<\/p>\n
Permutations, combinations, and derangements in databases<\/h2>\n
While all these are interesting, a database person is probably going to be more interested in actually generating<\/em> the permutations, combinations, and derangements. The problem is that SQL is not really built for this kind of computation. The sets are in databases are in the form of tables, which all have a fixed number of columns. Databases don\u2019t have arrays, link lists, or other data structures, so it\u2019s faked with tables.<\/p>\nIf all the columns are the same data element, then this is an example of de-normalizing a table with a repeated group. Here\u2019s a simple example for (n = 3)<\/p>\n
CREATE TABLE #Permutations\r\n(c1 INTEGER NOT NULL,\r\n c2 INTEGER NOT NULL,\r\n c3 INTEGER NOT NULL,\r\nPRIMARY KEY (c1, c2, c3),\r\nCONSTRAINT Unique_columns\r\nCHECK (\r\n\t\tc1 NOT IN (c2, c3)\r\n\t\tAND c2 NOT IN (c1, c3)\r\n\t\tAND c3 NOT IN (c1, c2)\r\n\t\t\r\n\t));<\/pre>\nRemember that all tables must have a key. In these cases, the rows that represent a particular set all have to be unique, and so do all of the columns in that row. This means each row is a key.<\/p>\n
The CHECK()<\/code> constraint ensures that all columns are unique with a row. A lot of the ranges of the dimensions, constraints about membership, etc., in other data structures must be explicitly defined in SQL check constraints. This is one of the many reasons that I tell newbies that 80 to 90% of the work in SQL is done in the DDL, not the DML. Think about trying to write constraints into procedural code for 500 application programs; instead of putting it in one CHECK()<\/code> constraint, you must duplicate the same code and magically hope that you get it right in every procedural chunk in your system. And when the rules change, you must go back through those 500 pieces of procedural code and update them. Lots of luck with that.<\/p>\nModeling combinations is easy. Since order doesn\u2019t matter, any simple list of the values will do. That\u2019s a perfect description of a table with one column.<\/p>\n
There are several algorithms for generating permutations. Two of the best known are the Heap algorithm (1963) and the Fike algorithm. Both are recursive and are based on the facts that<\/p>\n
1) There are n! permutations of the set {1, 2, 3, …,}. This let you know how many times you have to cycle through a loop or how deep your recursion has to go.<\/p>\n
2). The next permutation can be generated from the current permutation without fear of duplication.<\/p>\n
Robert Sedgwick (you might know from his textbooks that are widely used) wrote a paper<\/a> on the various methods for generating permutations. He classified them as<\/p>\n1 METHODS BASED ON EXCHANGES<\/strong>
\nRecursive methods
\nAdjacent exchanges
\nFactorial counting
\n“Loopless” algorithms<\/p>\n2 OTHER TYPES OF ALGORITHMS
\n<\/strong>Nested cycling
\nLexicographic algorithms
\nRandom permutation<\/p>\nReferences:<\/h2>\n
https:\/\/en.wikipedia.org\/wiki\/Heap%27s_algorithm<\/p>\n
https:\/\/academic.oup.com\/comjnl\/article\/19\/2\/156\/408726. The Computer Journal, vol 19 Issue 2. pages 156-159<\/p>\n
https:\/\/homepage.math.uiowa.edu\/~goodman\/22m150.dir\/2007\/Permutation%20Generation%20Methods.pdf<\/p>\n
<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Joe Celko explains how several mathematical concepts, combinations, permutations, and derangements, relate to databases.…<\/p>\n","protected":false},"author":96214,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[53,143539],"tags":[5134],"coauthors":[6781],"class_list":["post-94177","post","type-post","status-publish","format-standard","hentry","category-featured","category-theory-and-design","tag-sql-prompt"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/94177","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/96214"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=94177"}],"version-history":[{"count":5,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/94177\/revisions"}],"predecessor-version":[{"id":94184,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/94177\/revisions\/94184"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=94177"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=94177"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=94177"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=94177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}