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

Problem Description

Permutes 2 finishes the job we started in Permutes1. It adds combinations to the permutations from the previous program and it adds the ability to generate permutations and combinations for subsets of objects.  

Background and Description  

Both changes are fairly easy to implement.  The three Permutes1 algorithms  from other texts have been dropped,  mainly because I couldn't figure out how to apply them to permutations of subset of a set.  Only my method was retained and modified.  The number of permutations for R of N objects is the number of ways in which we can select the R objects if order matters.  That number is N*(N-1)*N-2)... (N-R+1).   For example, selecting 2 of 5 objects can be done in 5X4=20 ways.  This can also be written as N! / (N-R)!  (e.g. (5X4X3X2X1) / (3X2X1).

To generate all permutations for R objects from a set of N,  the main change in the Setup routine to calculate the count as described above and to change the upper limit on size from N to R in the calculation routine. 

Combinations

Combinations are  unique subsets of objects, ignoring order.  The number number of 5 card poker hands that can be dealt from a 52 card deck is a combinations problem.  The 120 (i.e. 5!) different arrangements of cards in a hand containing 10,J,Q,K,A of hearts are all the same  in terms of combinations.  This is true of every other hand, so you can see that there a many fewer combinations than permutations of things.   In fact, there are  always 1/R! fewer combinations than permutations, so the total combinations for R of N objects is the number of permutations divided by R!, i.e. N!  /(N-R)! / R!.  For our 2 of 5 example this is 5!/3!/2!=10.  For poker hands the total number is 52!/47!/5!=2,598,960.  

The easiest way to generate combinations is in increasing sequence so that no number is ever smaller than a number on its left. For example in our 2 of 5 example the 10 combinations  are {12, 13, 14, 15, 23, 24, 25, 34, 35, 45}      This is called lexicographic order.

A Combo Unit

This page will also be the home of a Combo unit containing a TComboSet class.  TComboSet encapsulates the ability to generate permutations and combinations of R of N objects.  It was originally written several years ago and is used in many of the program contained in this site.   The original version  evolved slightly over the years: counts that were originally defined of type double are now long integers, int64, type;   The initialization which originally created the object and set the N and R parameters, now assumes that the object already exists, etc.   An initialization section in the Combo unit now creates a instance of TComboset , named Combos, immediately usable by programs including the unit.     

TComboset is easy to use.  Procedure Setup initializes a run with number of objects, N, number to be selected, R, and a Ctype variable (combinations or permutations) indicating which type is be returned.  Function GetNext returns value true if a  combination or permutation has been generated or  false when all have been returned.  Combinations or permutations are returned in  a fixed length global  byte array named Selected.   

For example, what mismatched pairs of socks could Chris create if he has 5 pairs of different colors (Red, Green, Blue, Yellow, and Purple)  lying loose in his drawer?   

procedure TForm1.Button1Click(Sender: TObject);
var s,sockcolors:string;
begin
    combos.setup(2,5,combinations);
    sockcolors:='RGBYP';
    while combos.getnext do
    with combos do
    begin
        s:=sockcolors[selected[1]]+sockcolors[selected[2]];
        listbox1.items.add(s);
    end;
end;

Previously posted programs using TComboSet have been replaced with versions using this version of the unit.  The list identified so far includes:

No functional change to these programs,  just a few minor adjustments to reflect the Combo changes described above. 

Addendum May 24 2004:  At a viewer's request, I added  an option to display permutations or combinations of  character strings as well as numbers to the  program today.  

Running/Exploring the Program 

Suggestions for Further Explorations

I'm sure that there are faster algorithms for creating permutations of subsets than the used in Combo, I just haven't located them yet.    

Done! BigCombos, a unit using the  Big Integers unit to generate permutations and combinations for large numbers is in the works.  

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.