{"id":476,"date":"2013-05-13T21:18:32","date_gmt":"2013-05-14T01:18:32","guid":{"rendered":"http:\/\/learninglover.com\/blog\/?p=476"},"modified":"2013-05-13T21:18:32","modified_gmt":"2013-05-14T01:18:32","slug":"permutation-problems","status":"publish","type":"post","link":"https:\/\/learninglover.com\/blog\/index.php\/2013\/05\/13\/permutation-problems\/","title":{"rendered":"Permutation Problems"},"content":{"rendered":"

I love to play with puzzles. When I was in grade school I would spend hours at a time figuring out ways to solve from things like Tetris, Mindsweeper, Solitare, and Freecell. Later I was introduced to puzzles involving numbers like Sudoku<\/a> and Nonograms<\/a>. <\/p>\n

These puzzles are often interesting in part because there is generally a very large way that things can be arranged, but only a few of these arrangements are correct. Generally a person solving a puzzle will figure out certain things that must be true or cannot be true, which helps in solving the puzzle and reducing the number of possible cases. Initially, though, we are often left with a situation where we have a new puzzle and our only method is to keep trying every possible solution until we start to notice a pattern (or reach a solution). <\/p>\n

For example, consider a Sudoku puzzle. We are given a partially filled in grid and our job is to fill in the remaining cells with the rules that every row, column and marked subgrid must have the numbers 1 – 9 exactly once. One initial attempt at solving such a puzzle could be to attempt to permute the string 1, 2, 3, 4, 5, 6, 7, 8, 9 until we find a solution that fits the first row, then do the same with the second row, and so on and so forth. <\/p>\n

One immediate question is how many ways are there to permute the numbers 1, …, 9? We can answer this by realizing that each permutation is a new string. So for each string that we construct, we have 9 choices for the first element in the string. Then once that element has been chosen, we are not allowed for that element to appear anywhere else. So there are only 8 possible choices for what can go in the second string. Continuing this process, we see that the number of possible permutations we can construct from the string 1, …, 9 is <\/p>\n

9 <\/u> * 8 <\/u> * 7 <\/u> * 6 <\/u> * 5 <\/u> * 4 <\/u> * 3 <\/u> * 2 <\/u> * 1 <\/u> = 362880<\/p>\n

This is a large number of possible strings to generate just to get one row of a Sudoku, so hopefully you’ll be able to notice the pattern before going through this whole set (because once you’ve generated the first row you still have to do the other 8 rows). <\/p>\n

Nonetheless because there is often great value that can be gained by knowing how to permute through all possible solutions, I have written three functions that help with this process: Next_Permutation, Previous_Permutation, and Random_Permutation. <\/p>\n

Before I give these algorithms, I want to highlight two notations on ordering string. A string (a1<\/sub>, a2<\/sub>, …, an<\/sub>) is said to be in lexicographical order (or alphabetical order) if for each i [in] 1, …, n-1, ai<\/sub> [<=] ai+1<\/sub>. Likewise, a string is said to be in reverse lexicographical order if for each i [in] 1, …, n-1, ai<\/sub> [>=] ai+1<\/sub>.<\/p>\n

Next Permutation<\/b><\/p>\n

If the given string is not in reverse lexicographic order, then there exists two elements j1<\/sub> and j2<\/sub> such that j1<\/sub> [<] j2<\/sub> and aj1<\/sub><\/sub> [<] aj2<\/sub><\/sub>.
\n1. The Next_Permutation algorithm first searches for the largest element j1<\/sub><\/i> such that aj1<\/sub><\/sub> [<] aj1<\/sub> + 1<\/sub>. Since we said the string is not in reverse lexicographic order, this j1<\/sub> must exist.
\n2. Once this j1<\/sub> is found, we search for the smallest element aj2<\/sub><\/sub> such that aj2<\/sub><\/sub> [>] aj1<\/sub><\/sub>. Again, since we know that this is true for j1<\/sub> + 1, we know that such a j2<\/sub> must exist.
\n3. We swap the elements aj1<\/sub><\/sub> and aj<\/sub>2<\/sub><\/sub>.
\n4. The elements after j1<\/sub> + 1 are then placed in lexicographic order (i.e. in order such that ai<\/sub> [>=] ai+1<\/sub><\/p>\n

If the given string is in reverse lexicographic order, then we simply reverse the string. <\/p>\n

Previous Permutation<\/b><\/p>\n

If the given string is not in lexicographic order, then there exists two elements j1<\/sub> and j2<\/sub> such that j1<\/sub> [<] j2<\/sub> and aj1<\/sub><\/sub> [>] aj2<\/sub><\/sub>.
\n1. The Previous_Permutation algorithm first searches for the largest element j1<\/sub><\/i> such that aj1<\/sub><\/sub> [>] aj1<\/sub> + 1<\/sub>. Since we said the string is not in reverse lexicographic order, this j1<\/sub> must exist.
\n2. Once this j1<\/sub> is found, we search for the smallest element aj2<\/sub><\/sub> such that aj1<\/sub><\/sub> [>] aj2<\/sub><\/sub>. Again, since we know that this is true for j1<\/sub> + 1, we know that such a j2<\/sub> must exist.
\n3. We swap the elements aj1<\/sub><\/sub> and aj<\/sub>2<\/sub><\/sub>.
\n4. The elements after j1<\/sub> + 1 are then placed in reverse lexicographic order (i.e. in order such that ai<\/sub> [<=] ai+1<\/sub><\/p>\n

If the given string is in lexicographic order, then we simply reverse the string. <\/p>\n

Random Permutation<\/b><\/p>\n

This generates a random string permutation. <\/p>\n

This script can be seen here, set to work on permutations of colors. <\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

I love to play with puzzles. When I was in grade school I would spend hours at a time figuring out ways to solve from things like Tetris, Mindsweeper, Solitare, and Freecell. Later I was introduced to puzzles involving numbers like Sudoku and Nonograms. These puzzles are often interesting in part because there is generally […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-476","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=476"}],"version-history":[{"count":0,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/476\/revisions"}],"wp:attachment":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=476"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}