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

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.3X10¹⁵⁷⁾  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 

Suggestions for Further Explorations

?????????

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

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