This is great! permutations / combinations / factorial(100) w values more than uint64 limit

[emailx45]

Firstly, thanks to:

Gary Darby All rights reserved (for uso non-Commercial, of course)

Created: January 18, 2003 and Modified: July 29, 2017

With lib you can to know Whats the FACTORIAL(100) showed as a String without error because it use Array of Byte to store and calculate the values more than UInt64 (2^63-1)

If needs create combinations for example, lottery games, up to 100 elements its great for you.

C 6,60 = 50.063.860 combinations or
P 60,60 = 8.320.987.112.741.390.144.276.341.183.223.364.380.754.172.606.361.245.952.449.277.696.409.600.000.000.000.000 permutations.

Do you know to read this last number?

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

[HIDE="5"]
(Requires one time download of DFF Library source DFFLibV02 or later)

http://www.delphiforfun.org/Programs/Download/BigCombosSource.zip

LIB v1.5 (last)
http://www.delphiforfun.org/Programs/Library/Downloads/DFFLibV15.zip
[/HIDE]

 

[emailx45]

Copyright © 2000-2017, Gary Darby All rights reserved

What about to know the resulted to FACTORIAL(999) ?

Does anybody know to read one numeric value with 2500 digits? try it

402,387,260,077,093,773,543,702,433,923,003,985,719,374,864,210,
714,632,543,799,910,429,938,512,398,629,020,592,044,208,486,
969,404,800,479,988,610,197,196,058,631,666,872,994,808,558,
901,323,829,669,944,590,997,424,504,087,073,759,918,823,627,
727,188,732,519,779,505,950,995,276,120,874,975,462,497,043,
601,418,278,094,646,496,291,056,393,887,437,886,487,337,119,
181,045,825,783,647,849,977,012,476,632,889,835,955,735,432,
513,185,323,958,463,075,557,409,114,262,417,474,349,347,553,
428,646,576,611,667,797,396,668,820,291,207,379,143,853,719,
588,249,808,126,867,838,374,559,731,746,136,085,379,534,524,
221,586,593,201,928,090,878,297,308,431,392,844,403,281,231,
558,611,036,976,801,357,304,216,168,747,609,675,871,348,312,
025,478,589,320,767,169,132,448,426,236,131,412,508,780,208,
000,261,683,151,027,341,827,977,704,784,635,868,170,164,365,
024,153,691,398,281,264,810,213,092,761,244,896,359,928,705,
114,964,975,419,909,342,221,566,832,572,080,821,333,186,116,
811,553,615,836,546,984,046,708,975,602,900,950,537,616,475,
847,728,421,889,679,646,244,945,160,765,353,408,198,901,385,
442,487,984,959,953,319,101,723,355,556,602,139,450,399,736,
280,750,137,837,615,307,127,761,926,849,034,352,625,200,015,
888,535,147,331,611,702,103,968,175,921,510,907,788,019,393,
178,114,194,545,257,223,865,541,461,062,892,187,960,223,838,
971,476,088,506,276,862,967,146,674,697,562,911,234,082,439,
208,160,153,780,889,893,964,518,263,243,671,616,762,179,168,
909,779,911,903,754,031,274,622,289,988,005,195,444,414,282,
012,187,361,745,992,642,956,581,746,628,302,955,570,299,024,
324,153,181,617,210,465,832,036,786,906,117,260,158,783,520,
751,516,284,225,540,265,170,483,304,226,143,974,286,933,061,
690,897,968,482,590,125,458,327,168,226,458,066,526,769,958,
652,682,272,807,075,781,391,858,178,889,652,208,164,348,344,
825,993,266,043,367,660,176,999,612,831,860,788,386,150,279,
465,955,131,156,552,036,093,988,180,612,138,558,600,301,435,
694,527,224,206,344,631,797,460,594,682,573,103,790,084,024,
432,438,465,657,245,014,402,821,885,252,470,935,190,620,929,
023,136,493,273,497,565,513,958,720,559,654,228,749,774,011,
413,346,962,715,422,845,862,377,387,538,230,483,865,688,976,
461,927,383,814,900,140,767,310,446,640,259,899,490,222,221,
765,904,339,901,886,018,566,526,485,061,799,702,356,193,897,
017,860,040,811,889,729,918,311,021,171,229,845,901,641,921,
068,884,387,121,855,646,124,960,798,722,908,519,296,819,372,
388,642,614,839,657,382,291,123,125,024,186,649,353,143,970,
137,428,531,926,649,875,337,218,940,694,281,434,118,520,158,
014,123,344,828,015,051,399,694,290,153,483,077,644,569,099,
073,152,433,278,288,269,864,602,789,864,321,139,083,506,217,
095,002,597,389,863,554,277,196,742,822,248,757,586,765,752,
344,220,207,573,630,569,498,825,087,968,928,162,753,848,863,
396,909,959,826,280,956,121,450,994,871,701,244,516,461,260,
379,029,309,120,889,086,942,028,510,640,182,154,399,457,156,
805,941,872,748,998,094,254,742,173,582,401,063,677,404,595,
741,785,160,829,230,135,358,081,840,096,996,372,524,230,560,
855,903,700,624,271,243,416,909,004,153,690,105,933,983,835,
777,939,410,970,027,753,472,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000


Problem Description
Here's a program to calculate really large factorials - up to 999! which contains more than 2500 digits! Probably not very practical, but it is a good exercise simulating pencil and paper long multiplication.

Background & Techniques
For any integer N, N factorial, usually written N!, is the product of all integers from 1 through N. So 3!=1*2*3=6, 10!=1*2*3*4*5*6*7*8*9*10=3,628,800. As you can see, N! increases very rapidly with increasing N.

Delphi integer types occupy 32 bits, long integer, denoted as int64, occupy 64 bits. The max value of these types is 231-1 and 263-1, large enough to contain only 15! and 20! respectively.

BigFactorials overcomes this size limitation by multiplying almost the way we would do it with pencil and paper. Numbers are kept as an array of bytes, each byte representing one digit. The array is dynamic, so sizes can be changed as required. As a result, the number of digits in the result is limited only by the amount of memory available and the time you are willing to wait. I've limited the maximum input integer here to 999 here just to keep calculation times to 1 or 2 seconds.

When the user presses the "Compute " button we call the the Factorial procedure with the input value. A loop running from 2 to N is executed, each time through we'll multiply the previous answer by the loop control variable I.

The digits in the number are kept with the units digit on the left and the high order digit on the right. This puts any leading zeros at the end of the array where they are easier to trim. The mod and div functions are used to get the units and carry part of each intermediate result. M1 and m2 are the two multiplicand arrays, result is array where the product is being accumulated. Shift is j-1, the amount we are shifting over for the jth digit. Again, just like long multiplication except we are shifting further left each time instead of further right. Here is the key code inside of a loop on j and k.

c:=m2[j]*m1[k]; {multiply the jth digit of m2 by the kth digit of m1}
result[k+shift]:=result[k+shift]+ c mod 10; {add in the units part}
result[k+shift+1]:=result[k+shift+1]+ c div 10; {add in the carry part}



Running/Exploring the Program

[HIDE="5"]http://www.delphiforfun.org/Programs/Download/BigFactorialsSource.zip [/HIDE]



Suggestions for Further Explorations

For numbers much higher than 999!, I would search for more efficient techniques.

It would also be a good idea to add a Stop button and periodically call application.processmessages inside the multiply loop if the max number is increased. (See the article on maintaining responsiveness in Delphi techniques section for more information.)

The code could be written to work just like manual long multiplication - I'm not sure of the effect on efficiency, but the code would probably be easier to follow.

I mentioned that factorial values increase very rapidly as N increases. There are mathematical measures of this rate of growth. For example kN (e.g. 2N or 10N) are said to grow exponentially (as the exponent I suppose). How does the growth of N! compare to kN ? One clue is that 23! is 23 digits long. Coincidentally, this also is approximately the number of kilometers across the known universe.