Permutes #1

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

Many 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 & Techniques

Notice 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 Program 

A note about file formats

Suggestions for Further Explorations

We'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.)

1 2
3
4 5 6
7 8 9

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.  

Originally posted:  October 29, 2001

Modified: February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.