Big Combos & Permutations

[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.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

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

Search DelphiForFun.org only

 

 

Problem Description

Big Combos uses the Big Integers unit to compute permutations and combinations for numbers far beyond the 64 bit limit of normal  integer arithmetic.   Since listing billions of results will not normally be very useful, Big Combos also allows you to specify   "Show Mth" to see a specific permutation or combination.    Handy if you need to know the 10 billionth permutation of the letters of the alphabet, for example. 

Background & Techniques

The previously posted Permutes2 computes permutations and combinations of up to 10 items.  The 10 item limitation was imposed to insure that results stayed well  within the range of 64 bit integer arithmetic.   In order to extend this to 100 items, we need a way to handle very large numbers.  The Big Integer unit is not very fast or sophisticated but it will do the job even though the larger numbers will take a few seconds to compute.     For example, there are  93, 326, 215, 443, 944, 152, 681, 699, 238, 856, 266, 700, 490, 715, 968, 264, 381, 621, 468, 592, 963, 895, 217, 599, 993, 229,915, 608, 941, 463, 976, 156, 518, 286, 253, 697, 920, 827, 223, 758, 251, 185, 210, 916, 864, 000, 000, 000, 000, 000, 000, 000, 000 (~9.3X10157)  permutations of 100 items which should be a enough  for practical purposes!   

Of more potential interest than listing the results is the ability to compute a specific permutation or combination assuming they are generated in lexicographic order.   So I may be the first to report that 10 billionth  "word" in an alphabetical list of 26 letter words which contain all letters is "abcdefghijklnuyswpxzvorqtm", still pretty close to the top of the list!

From a programming viewpoint, the generation of permutations and combinations is a straightforward adaptation of the Permutes2 code.  The "Show Mth Combination" was adapted from Fortran code written by John Burkardt based on algorithms from  Combinatorial Algorithms,  Donald Kreher and Douglas Simpson, CRC Press, 1998.

The "Show Mth Permutation" code was written recently and uses the observation that permutations in lexicographic order have very predictable subsequences that grow shorter as we move from left to right across the permutation.  

The final interesting programming task was to properly  display  permutation/combination  counts in the CCountLbl label at the bottom of the screen.  Even with the word wrap property set to true, text will only wrap when a space character is encountered.   Procedure Showcount  uses the TextWidth function of the labels canvas to insert spaces into long number strings so that they will wrap when required.  

Addendum July 21, 2006:  I added a button  today to write results to  a text file in response an (impractical) request to increase the screen display to 500,000 results.

Addendum October 17, 2009:  A small update in incorporate DPI scaling into the program so that the count of total results can be displayed properly when text sizes are rescaled.  I also modified the count to display in scientific as well as integer format.   

Running/Exploring the Program 

bulletDownload source  (Requires one time download of DFF Library source DFFLibV02 or later)
bulletDownload current DFF Library Source (DFFLibV15 )
bulletDownload  executable

Suggestions for Further Explorations

?????????

 

Created: January 18, 2003

Modified: July 29, 2017

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