[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionMany problems that we want to solve depend on looking at all permutations (arrangements) of a set of integers to see which help solve the problem. In this program we'll write some code to generate all possible arrangements So, for example, if the user says "show me all permutations of the first 3 integers", we'll display "[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]" Background & TechniquesNotice that there were 6 permutations of 3 things. Without formally proving it, we'll take advantage of the fact that for N things there are n factorial (N!) possible arrangements. (N! is the product of all integers from 1 to N.) We ended up with 2 versions of the code to generate permutations, each with its own button. The first, from Robert Sedgewick's book Algorithms, is short (25 lines of code) but I don't really understand how it works. If anyone wants to post a plain English explanation, I'll try to understand it. My code is longer, 60 lines, but I can explain it. Also it generates permutations in increasing order (called lexicographic order), while Sedgewick's does not. Here's the algorithm stated informally. (1) Generate an initial permutation by listing the integers 1 through N. For the 2nd and succeeding permutations, we're going generate each permutation from the previous one this way: (2) find the number furthest to the right which can be increased without exceeding the max number and without duplicating a number already appearing to its left. When found, (3) increase that value and (4) fill in all positions to the right with the lowest possible unused values. If we can't find any number in step 2, we're done. For example, if we're permuting 4 things and are given [1,3,4,2] we want to generate the next, we check 2 - it can't be increased because 3 and 4 have already been used to its left. Check 4 - already at max, check 3 - can be incremented because 4 doesn't appear to its left. So we have 14xx. The rule for completing the permutation is to use the lowest unused number in each position moving from left to right. So for the last 2 positions, we'll insert a 2 and and a 3 and end up with [1,4,2,3]. The next is [1,4,3,2], then [2,1,3,4], [2,1,4,3], etc. (Postscript: There is actually a 3rd permutation generator included in the program. The third is also lexicographic and shorter than mine, but again, more difficult to understand.) Addendum: April 22, 2002: I just added a 4th permutation generator based on a a paper & C code by Jeffrey Johnson (SEPA algorithm) (http://www.cs.byuh.edu/~johnsonj/permute/soda_submit.html Note: this link is broken and probably gone - what a shame!). It is the same algorithm as the Sawada procedure previously posted, but getter documented, so you can understand what is going on. Still magic, but understandable magic. This NextPermute function is fast, concise, and requires no initialization. It will be by standard from now on when all permutations of a set of things is required. Running/Exploring the ProgramA note about file formats
Suggestions for Further ExplorationsWe'll be using this routine in many other puzzles that can be solved by trial and error. For example we can solve a 3X3 magic square by generating all possible arrangements of the integers 1 - 9 and assuming the 1st 3 digits are the first row, the next 3 the second row, and the last 3 the 3rd row. (A magic square is one where numbers in each row, column and two main diagonals all add to the same number.)
So if we generate all arrangements and find one where the sums of all the rows and columns and the two main diagonals add to the same number, we have a solution. Since 9! is only 360,000 or so, we should be able to find all solutions quickly. You can modify this program to find all 3X3 magic squares if you want to. Compare the sums of the first 3 digits of each permutation with the second 3, the third 3, etc. Just add another button and list the solutions in the listbox instead of all permutations. I wouldn't try it for 4X4 magic squares since 16! is a very large number indeed. The AlphaMetics program uses a version of this Permutes1 program converted to a function in a separate unit. This will make it easier to generate permutations wherever we need them. There's also a Permutes 2 program, here or planned which adds the ability to generate combinations as well as permutations and to select K of N objects to permute or combine.
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |