[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHere's an algorithm developed by J.R. Heap in 1963 which generates permutations of data items. It is quite efficient because it swaps only 2 elements for each one generated. The disadvantage may be that that there is no apparent order in the generated permutations. Search "Heap's algorithm" on Wikipedia for more information. Background & TechniquesOur DelphiforFun website has a "UCombosV2" unit which generates many kinds of
permutations and combinations, but I needed one that was easy to code for
another "start from scratch" project. The Wikipedia article has "pseudocode"
for both recursive and non-recursive implementations of the algorithm. This demo
has two Delphi versions of each; one with inputs as an array of characters and
the other a string of characters. The four versions are
PermuteCharArray_R, PermuteString_R, PermuteCharArray_NR, and
PermuteStringArray_NR. Programmer's NotesHere is the pseudo code for the recursive version of the algorithm: procedure generate(n : integer, A : array of any): The character Delphi version is pretty direct translation of the pseudo code.
I believe that was about it. Recursion (a subroutine calling itself) in general seems like magic. As you tell from the pseudo code examples, it does simpliy implementation in case when the basic procedure must be invoked multiple times to compute the "next" entry. Th simplest example is the recursive routine for computing the "factorial" of an integer. Denoted as N!, the factorial is the product of all integers 1 through N. Here's the routine: function factorial(N:integer):integer; You can uncomment the Showmessage statement in the program's FormCreate procedure to prove that it works! One other Delphi feature used here is the ability to of the define multiple versions of a routine with the same name just so long as the parameter lists are unique. Add the statement Overload after the initial definition line and Delphi will figure out which one based on the parameter list. You'll see it used several times in this program to handle "string" and "Character array" versions performing the same task with the same routine name. A late addition is a VerboseBox check box to to display the pair of characters swapped for each permutation generated. Examining the output shows that the program works from left to right generating all permutations of the first 2, then 3 then 4 characters, etc. In the default ABCD example, the 1st six have all permutations of ABC, the 2nd six have all for ABD, etc. Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |