PART2K.BAS
January 2000 by Marc Kummel aka Treebeard.
Contact mkummel@rain.org, http://www.rain.org/~mkummel/
What is PART2K.BAS?
--------------------
PART2K is a BASIC program to find partitions of a number N into all parts,
possibly unique, that add up to that sum, with the optional constraints that
all partitions have just M parts and that all parts be <= P. I wrote this
program to solve a problem that arises with with magic squares and other
recreational math stumpers:
What are all the ways in which m different numbers can add up to n,
without regard to order?
Partitioning is a bit like factoring in that it decomposes a number, but it
uses addition rather than multiplication. This was a fun programming
challenge that uses recursive functions.
There are several different partition functions that PART2K can solve:
P(n) gives the number of ways of writing the number n as a sum
of positive integers without regard to order.
Q(n) gives the number of ways of writing the number n as a sum
of unique positive integers without regard to order.
P(n,m) gives the number of ways of writing the number n as a sum
of m positive integers without regard to order.
Q(n,m) gives the number of ways of writing the number n as a sum
of m unique positive integers without regard to order.
It's also possible to add the constraint to any of these functions that no
number be greater than p.
For example, consider the 11 partitions of 6:
(1) 6 = 6
(2) = 5 + 1
(3) = 4 + 2
(4) = 4 + 1 + 1
(5) = 3 + 3
(6) = 3 + 2 + 1
(7) = 3 + 1 + 1 + 1
(8) = 2 + 2 + 2
(9) = 2 + 2 + 1 + 1
(10) = 2 + 1 + 1 + 1 + 1
(11) = 1 + 1 + 1 + 1 + 1 + 1
From this partitioning, we see that:
P(6) = 11 {1 .. 11} (all partitions)
Q(6) = 4 {1, 2, 3, 6} (all partitions with unique numbers)
P(6,2) = 3 {2, 3, 5} (all partitions into 2 numbers)
Q(6,2) = 2 {2, 3} (all partitions into 2 unique numbers)
This is easy with small numbers, but P() and Q() are eponential functions
that grow large fast!
P(1000) = 24,061,467,864,032,622,473,692,149,727,991 (2.4 x 10^31)
My program uses the BASIC currancy data type to keep the exact count, so the
upper limit is about 9.2 x 10^14. Big, but not big enough for the P(2000)
problem I originally wanted to solve. On the other hand, my program doesn't
just count partitions, it actually finds them, and time is a factor. There
are faster ways to just get the count that I would like to implement.
For more info on Partition functions, check out my Millenium Magic stumper
at . There's advanced
discussion of the math at Eric Weisstein's World of Mathematics site at
.
Using PART2K.BAS
-----------------
PART2K is a simple DOS program. Run it in DOS, or a Command session in
Windows. There are several options that can be set from the command line,
or interactively if the program is started without parameters (which I
recommend).
Usage: PART2K [n m [p] [/q] [/swc?] [/d[x]] [/f[name.ext]]
Options:
n = The positive integer N to partition,
[m] = with the constraint that partitions have just M parts, and
[p] = with the additional constraint that no part be > P.
[/q] = Find only partitions into unique parts Q(n).
[/d] = Process multiple partitions with step value x.
[/s] = Show partitions on screen as found.
[/w] = Show working count on screen.
[/c] = Add partition count to compilation file.
[/f] = Write all partitions to , could be huge!
[/?] = This help.
The /d and /c options are useful together to partition many numbers and save
the counts into a tab delimited file for import into a spreadsheet program.
Use the /f option to save the actual partitions, but the file might be huge!
Pressing should stop the program while it is working, but you may have
to wait a while for it to take effect. It's faster if you turn off the
display options.
The Files:
-----------
I wrote this program to solve a stumper. You'll have to study the source
code for more info. I wrote it using MS Basic PDS v7.10. It will need
some work in QBasic or Quick Basic.
PART2K.EXE DOS executible to partition a number
PART2Knn.BAS BASIC source code
NUMPPART.DAT Compilation file to store results with /c option
README.TXT This file
TBVAULT.TXT Treebeard's Basic Vault info
Conditions:
------------
This program and source code are yours to use and modify as you will, but
they are offered as freeware with no warranty whatsoever. Give me credit,
but do not distribute any changes under my name, or attribute such changes
to me in any way. You're on your own!
If you find this program or code useful, then let me know what you do with
it, as a courtesy to a fellow programmer who still hacks for fun and glory.
Any suggestions or comments will be much appreciated.
Send comments and fixes to:
Marc Kummel aka Treebeard
mkummel@rain.org
http://www.rain.org/~mkummel/
http://www.treebeard.org/
For more interesting Basic software with source code, check out Treebeard's
Basic Vault at .