(defun breaking (N)
(find-acc (list N) 0))
(defun find-acc (l acc)
(cond ((null l) nil)
((> (car l) 1)
(let ((new (append (nreverse (deal (1+ acc) (1- (car
l))))
(cons (1- (car l)) (rest l)))))
(progn
(print new)
(find-acc new 0))))
(t (find-acc (rest l) (1+ acc)))))
(defun deal (acc lmt)
(if (> acc lmt) (cons lmt (deal (- acc lmt) lmt))
(list acc)))
The recursive solution is streightforward but it won't work for nothing
but small numbers , something like 20 or 30 max .
Unfortunately i don't have an implementation in my office computer to
make an iterative solution .
Will try through allegro prompt , if i have some spare time later ,
else you have to wait till tomorrow.
>>The recursive solution is streightforward but it won't work for
nothing
>>but small numbers , something like 20 or 30 max .
Actually it works till 60 (Corman Lisp) but try using arrays ,
for a N number array size will be N elements , 7 = 1 1 1 1 1 1 1
longest breaking .Some declaration could be also usefull (fixnum).
BTW let the newb write it , he might even learn something.
·············@hotmail.com wrote:
>>>The recursive solution is streightforward but it won't work for
>
> nothing
>
>>>but small numbers , something like 20 or 30 max .
>
> Actually it works till 60 (Corman Lisp) but try using arrays ,
> for a N number array size will be N elements , 7 = 1 1 1 1 1 1 1
> longest breaking .Some declaration could be also usefull (fixnum).
> BTW let the newb write it , he might even learn something.
>
I'm using Corman Lisp 2.51, and I can't make it work for 60: I get a
message "... you have entered the garbage collector recursively ...".
Which version are you using ?
Thanks
Joseph
In article <·······················@g47g2000cwa.googlegroups.com>,
"fireblade" <········@YAHOO.COM> wrote:
> (defun breaking (N)
> (find-acc (list N) 0))
> (defun find-acc (l acc)
> (cond ((null l) nil)
> ((> (car l) 1)
> (let ((new (append (nreverse (deal (1+ acc) (1- (car
> l))))
> (cons (1- (car l)) (rest l)))))
> (progn
> (print new)
> (find-acc new 0))))
> (t (find-acc (rest l) (1+ acc)))))
> (defun deal (acc lmt)
> (if (> acc lmt) (cons lmt (deal (- acc lmt) lmt))
> (list acc)))
>
> The recursive solution is streightforward but it won't work for nothing
> but small numbers , something like 20 or 30 max .
> Unfortunately i don't have an implementation in my office computer to
> make an iterative solution .
> Will try through allegro prompt , if i have some spare time later ,
> else you have to wait till tomorrow.
Just in case anyone lurking has come away with the impression that this
problem really is this complicated, here's a simpler solution:
(defun partition (n &optional p)
(if (< n 1)
(print p)
(loop for i from 1 to n do
(partition (- n i) (cons i p)))))
Fixing this so that it doesn't produce duplicate partitions is left as
an exercise, but requires only a very minor change (a dozen characters
or so) to the code.
N.B. This code works just fine for large integers (up to the stack
depth of your Lisp implementation). But it runs for a long, long time
:-)
rg
Ron Garret wrote:
>
> Just in case anyone lurking has come away with the impression that
this
> problem really is this complicated, here's a simpler solution:
>
> (defun partition (n &optional p)
> (if (< n 1)
> (print p)
> (loop for i from 1 to n do
> (partition (- n i) (cons i p)))))
>
> Fixing this so that it doesn't produce duplicate partitions is left
as
> an exercise, but requires only a very minor change (a dozen
characters
> or so) to the code.
>
> N.B. This code works just fine for large integers (up to the stack
> depth of your Lisp implementation). But it runs for a long, long
time
> :-)
>
Frankly, I would love to see how you a) sort each partition into
descending order, b) filter out single-number partitions, and c)
accumulate previously generated partitions to keep track of what's
already printed, all in a dozen characters or so.
Here's the solution I came up with:
(defun make-build-list (i)
#'(lambda (x)
(cond ((consp x) (cons i x))
;((null x) (list i)) ;currently unnecessary
((= 0 x) (list i))
(t (list i x)))))
(defun list-addings (n &optional (max (- n 1)))
(if (= n 0) '(0)
(let ((acc ()))
(do ((i (min n max) (- i 1)))
((<= i 0) acc)
(setf acc (append acc (map 'list
(make-build-list i)
(list-addings (- n i) i))))))))
...invoke with (list-addings N) to start.
And, once again, with caching:
(let ((results (make-array '(100 100) :initial-element nil)))
(defun list-addings-cached (n &optional (max (- n 1)))
(if (null (aref results n max))
(setf (aref results n max)
(if (= n 0) '(0)
(let ((acc ()))
(do ((i (min n max) (- i 1)))
((<= i 0) acc)
(setf acc (append acc (map 'list
(make-build-list i)
(list-addings-cached (- n i) i)))))))))
(aref results n max))
)
The cached version explodes a lot more slowly as the starting number
increases - 60 takes about 11 seconds on my machine, and 70 took about
45 seconds. (72 => 60 secs, 74 => 80 secs, 76 => 108 secs, 80 => my
machine started thrashing and I had to kill the process) To contrast,
running yours (Ron's) for 20 takes over a minute on my machine - mine
does 20 in 0.05 seconds.
I'm only up to chapter 10 in ACL, so I could very easily still have
horrible inefficiencies in this code. Plus, a smarter caching system
could be used so as not to kill swap space and provide a more flexible
upper bound on partitionable numbers.
--David Brandt
In article <·······················@o13g2000cwo.googlegroups.com>,
"wildwood" <············@gmail.com> wrote:
> Ron Garret wrote:
> >
> > Just in case anyone lurking has come away with the impression that
> this
> > problem really is this complicated, here's a simpler solution:
> >
> > (defun partition (n &optional p)
> > (if (< n 1)
> > (print p)
> > (loop for i from 1 to n do
> > (partition (- n i) (cons i p)))))
> >
> > Fixing this so that it doesn't produce duplicate partitions is left
> as
> > an exercise, but requires only a very minor change (a dozen
> characters
> > or so) to the code.
> >
> > N.B. This code works just fine for large integers (up to the stack
> > depth of your Lisp implementation). But it runs for a long, long
> time
> > :-)
> >
>
> Frankly, I would love to see how you a) sort each partition into
> descending order, b) filter out single-number partitions, and c)
> accumulate previously generated partitions to keep track of what's
> already printed, all in a dozen characters or so.
Well, (b) is easy:
(defun partition (n &optional p)
(if (< n 1)
(if (> (length p) 1) (print p))
(loop for i from 1 to n do
(partition (- n i) (cons i p)))))
If you care about efficiency this can be optimized:
(defun partition (n &optional p)
(if (< n 1)
(if (cdr p) (print p))
...
If you're actually collecting the results instead of just printing them
it gets even easier to get rid of the degenerate case:
(defun partition (n &optional p (collector #'print))
(if (< n 1)
(funcall collector p)
(loop for i from 1 to n do
(partition (- n i) (cons i p) collector))))
(defun partition-list (n)
(let ((result nil))
(partition n nil (lambda (p) (push p result)))
(cdr result)))
Personally, I like to use the (non-standard) ITERATE macro for cases
like this. Iterate is like Scheme's named LET:
(defmacro iterate (name args &rest body)
`(labels ((,name ,(mapcar #'car args) ,@body))
(,name ,@(mapcar #'cadr args))))
(defun partition-list (n)
(let ( (result nil) )
(iterate p ((n n) (p nil))
(if (< n 1)
(push p result)
(loop ...)))
(cdr result)))
> To contrast,
> running yours (Ron's) for 20 takes over a minute on my machine - mine
> does 20 in 0.05 seconds.
Yes, but you have to compare apples and apples. The solution I posted
does I/O and a lot of unnecessary work generating duplicate cases.
The most straightforward way of getting rid of the duplicates is by
brute force:
(remove-duplicates (mapcar (lambda (n) (sort n '<) n) (parition-list ...
but that is, of course, horribly inefficient. A better solution is to
observe that partition-list generates all of the possible permutations
of a partition, including a properly sorted one. Sorting and removing
duplicates therefore gives the same result as simply removing all the
partitions that are not already properly sorted:
(remove-if-not #'sorted (parition-list ...
Writing "sorted" is left as an exercise.
This is still very inefficient because we're still doing all the work of
generating the duplicate solutions. The best solution is to avoid
generating unsorted partitions in the first place. Hopefully that is
now enough of a clue that you can figure out the rest on your own.
My final solution runs about 25% faster than yours on a direct
apples-to-apples comparison :-)
rg
In article <·······························@news.gha.chartermi.net>,
Ron Garret <·········@flownet.com> wrote:
> Personally, I like to use the (non-standard) ITERATE macro for cases
> like this. Iterate is like Scheme's named LET:
>
> (defmacro iterate (name args &rest body)
> `(labels ((,name ,(mapcar #'car args) ,@body))
> (,name ,@(mapcar #'cadr args))))
>
> (defun partition-list (n)
> (let ( (result nil) )
> (iterate p ((n n) (p nil))
> (if (< n 1)
> (push p result)
> (loop ...)))
> (cdr result)))
Oops, bad choice of names there, using p for both a variable and a local
function name. This code will work (thanks to CL's dual function-value
namespace) but it's bad from a pedantic point of view. I should have
written something like:
(iterate partition-loop ((n n) (p nil))
...
(loop for for i from 1 to n do
(partition-loop ...
rg
·············@yahoo.com wrote:
> I won HP pavilion, thank you everybody.
> I allmost got disqualified because
> of lisp but my program was shortest ,
> and it worked with largest numbers.
>
Post your solution, I would like to see what
you wrote.
Wade
·············@yahoo.com writes:
> I won HP pavilion, thank you everybody.
> I allmost got disqualified because
> of lisp but my program was shortest ,
> and it worked with largest numbers.
A happy lisp customer. Let him grow a manager and remember the lesson!
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
Pascal Bourguignon wrote:
> ·············@yahoo.com writes:
> > I won HP pavilion, thank you everybody.
> > I allmost got disqualified because
> > of lisp but my program was shortest ,
> > and it worked with largest numbers.
>
> A happy lisp customer. Let him grow a manager and remember the
lesson!
Enjoy your desktop Edgar you really earned it.
http://www.hp.com/hpinfo/newsroom/press_kits/2003/pcs/images/514.jpg
Ron Garret wrote:
>
> My final solution runs about 25% faster than yours on a direct
> apples-to-apples comparison :-)
>
> rg
Would that be close to...
(defmacro iterate (name args &rest body)
`(labels ((,name ,(mapcar #'car args) ,@body))
(,name ,@(mapcar #'cadr args))))
(defun partition-list (n)
(let ((result nil))
(iterate par ((n n) (p nil))
(if (< n 1)
(push p result)
(loop for i from (or (car p) 1) to n do
(par (- n i) (cons i p)))))
(cdr result)))
I can't get it to run as fast as mine (in a pure apple-apple
comparison), so I figure I missed an optimization or two.
This list is so awesome. Just working to understand what people are
talking about, looking up the usages I don't understand, and the
exercises in the book seem sooo much easier now...
Thanks, Ron.
--David Brandt
In article <························@f14g2000cwb.googlegroups.com>,
"wildwood" <············@gmail.com> wrote:
> Ron Garret wrote:
> >
> > My final solution runs about 25% faster than yours on a direct
> > apples-to-apples comparison :-)
> >
> > rg
>
> Would that be close to...
>
> (defmacro iterate (name args &rest body)
> `(labels ((,name ,(mapcar #'car args) ,@body))
> (,name ,@(mapcar #'cadr args))))
>
> (defun partition-list (n)
> (let ((result nil))
> (iterate par ((n n) (p nil))
> (if (< n 1)
> (push p result)
> (loop for i from (or (car p) 1) to n do
> (par (- n i) (cons i p)))))
> (cdr result)))
That's it! Good job! (I implemented it slightly differently, but yours
is actually cleaner than mine :-)
There is an additional optimization possible that allows you to
eliminate the OR: you can pre-generate all the possible first elements
so you don't have to check if they exist:
(defun part7 (n)
(let ((result nil))
(loop for j from 1 to n do
(iterate par ((n (- n j)) (p (list j)))
(if (< n 1)
(push p result)
(loop for i from (car p) to n do
(par (- n i) (cons i p))))))
(cdr result)))
but the speedup from that is pretty minimal and probably not worth the
extra code complexity.
> I can't get it to run as fast as mine (in a pure apple-apple
> comparison), so I figure I missed an optimization or two.
I doubt you're doing a real apples-to-apples comparison. Your solution
does a lot of unnecessary consing (because you're calling APPEND). In
my tests yours runs more than an order of magnitude slower than mine in
MCL 3.0:
? (time (length (list-addings 30)))
(LENGTH (LIST-ADDINGS 30)) took 244 milliseconds (0.244 seconds) to run.
Of that, 1 milliseconds (0.001 seconds) were spent in The Cooperative
Multitasking Experience.
160 milliseconds (0.160 seconds) was spent in GC.
2,468,272 bytes of memory allocated.
5603
? (time (length (part7 30)))
(LENGTH (PART7 30)) took 21 milliseconds (0.021 seconds) to run.
Of that, 14 milliseconds (0.014 seconds) was spent in GC.
273,864 bytes of memory allocated.
5603
?
> This list is so awesome. Just working to understand what people are
> talking about, looking up the usages I don't understand, and the
> exercises in the book seem sooo much easier now...
>
> Thanks, Ron.
You bet.
rg
On 2005-05-20, fireblade <········@YAHOO.COM> wrote:
> Just wondering is there any formula to
> calculate exact number of partitions without
> generating them ?
>
Yes. There is a recurrence due to Euler and a remarkable formula
due to Hardy and Ramanujan.
The recurrence is p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+ ...
That is, p(n)=sum (-1)^(j+1) p(n-3/2 j^2 -j/2 ) where j ranges over non-zero
integers.
The Hardy-Ramanujan-Rademacher formula is here:
http://www.math.uwaterloo.ca/~dmjackso/CO630/ptnform1.pdf
> The cached version explodes a lot more slowly as the starting number
> increases - 60 takes about 11 seconds on my machine, and 70 took
about
> 45 seconds. (72 => 60 secs, 74 => 80 secs, 76 => 108 secs, 80 => my
> machine started thrashing and I had to kill the process) To
contrast,
> running yours (Ron's) for 20 takes over a minute on my machine - mine
> does 20 in 0.05 seconds.
My copy of Abramowitz & Stegun claims
p(20) (number of partitions for n=20) is 627
p(60) is 966,467
p(70) is 4,087,968
p(76) is 9,289,091
p(80) is 15,796,476
one would exceed the capacity of a 32-bit machine to store the
resulting list in memory somewhere before
p(128) = 4,351,078,600
and exceed the capacity of a 64-bit machine somewhere before
p(418) = 20,170,183,018,805,933,659 (2e19 = 2^64.12...)
This quantity reportedly goes asymptotically as
(/ (exp (* pi (sqrt (* n 2/3))))
(* 4 n (sqrt 3)))
although the error still seems relatively large (2%) at n=500.
Wade Humeniuk wrote:
> ··············@hotmail.com wrote:
> >
> > one would exceed the capacity of a 32-bit machine to store the
> > resulting list in memory somewhere before
> >
> > p(128) = 4,351,078,600
> >
> > and exceed the capacity of a 64-bit machine somewhere before
> >
> > p(418) = 20,170,183,018,805,933,659 (2e19 = 2^64.12...)
> >
>
> This is only if you store the results as a flat (unshared) lists. As
> a tree, with shared structure and caching -- the algorithm below
easily
> calcs&stores p(500), with 63099 entries in the cache.
> (original p(500) calculation is well under a minute).
...
>
> CL-USER 28 > (time (progn (setf breaks (breaks 500)) t))
> Timing the evaluation of (PROGN (SETF BREAKS (BREAKS 500)) T)
>
> CL-USER 29 > *break-cache*
> #<EQUAL Hash Table{63099} 2134CE24>
You've hit on a very clever storage scheme; I haven't read Knuth's
fascicle in enough detail to know if it is one that he mentions or not.
However, I notice you didn't include the result of
(write-breaks 500)
in your post :-)
··············@hotmail.com wrote:
> However, I notice you didn't include the result of
>
> (write-breaks 500)
>
> in your post :-)
>
Luckily I can hit the break button in the LW listener if
I type it in by mistake. :) p(60) takes ~30sec to print,
p(500) may take longer than the life of the universe.
I also have a version of the code which does not create any
permanent storage at all, it just prints the results, so in theory
it can do even larger N's. Just run it and let it go until
the end of time.
Wade
Here is just-the-printing version:
;; WRITE-STRING is faster than WRITE, so Caching string values of
;; (<= 0 n <=1024)
(defvar *print-cache*
(let ((array (make-array 1024))) ;careful of print-cache limits
(loop for i from 0 below 1024
do (setf (aref array i) (format nil "~A " i)))
array))
(defun write-break-numbers (n)
(declare (optimize (speed 3) (safety 0)))
(assert (< n 1024))
(let ((breaks (make-array n :fill-pointer 0))
(print-cache *print-cache*))
(declare (type simple-vector breaks print-cache))
(labels ((write-breaks (tail-value &optional (repeats 1))
(loop for n across breaks do (write-string (aref print-cache n)))
(loop repeat repeats
with string = (aref print-cache tail-value)
do (write-string string))
(terpri))
(write-break-partition (n break)
(cond
((= break 1) (write-breaks 1 n))
((= break n) (write-breaks n))
(t
(let ((rem (- n break)))
(vector-push break breaks)
(loop for i from (min break rem) downto 1 do (write-break-partition
rem i))
(vector-pop breaks))))))
(declare (inline write-breaks))
(loop for break from n downto 1
do (write-break-partition n break)))))
CL-USER 24 > (test-write 60 "breaks-60.txt")
Timing the evaluation of (WRITE-BREAK-NUMBERS N)
user time = 7.420
system time = 0.180
Elapsed time = 0:00:08
Allocation = 96712 bytes standard / 2574 bytes conses
0 Page faults
NIL
···············@hotmail.com" <············@gmail.com> writes:
> My copy of Abramowitz & Stegun claims
>
> p(20) (number of partitions for n=20) is 627
> p(60) is 966,467
> p(70) is 4,087,968
> p(76) is 9,289,091
> p(80) is 15,796,476
>
> one would exceed the capacity of a 32-bit machine to store the
> resulting list in memory somewhere before
>
> p(128) = 4,351,078,600
>
> and exceed the capacity of a 64-bit machine somewhere before
>
> p(418) = 20,170,183,018,805,933,659 (2e19 = 2^64.12...)
>
> This quantity reportedly goes asymptotically as
>
> (/ (exp (* pi (sqrt (* n 2/3))))
> (* 4 n (sqrt 3)))
>
> although the error still seems relatively large (2%) at n=500.
Wanna know p(1000) precisely? This is easy (and relatively fast) to
calculate:
; Evaluation took:
; 6.87f0 seconds of real time
; 6.09f0 seconds of user run time
; 0.27f0 seconds of system run time
; 4,107,607,622 CPU cycles
; [Run times include 3.76f0 seconds GC run time]
; 0 page faults and
; 91,708,584 bytes consed.
;
Partition(1000)=24061467864032622473692149727991
Exercise (extremely instructive): How is this done?
Hint: SICP.
Nicolas.
+ "basqi" <··················@yahoo.com>:
| Don't post your homework assignments here
| there is a big chance that your teacher is here
The way to post homework assignments:
1. State clearly up front that it is homework.
2. Present your work, as far as you got,
and ask for criticism or suggestions.
(BTW, aren't these "breakings" usually called partitions?)
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
"The Theory of Partitions," by George E. Andrews
http://www.amazon.com/exec/obidos/tg/detail/-/052163766X/qid=1116325571/sr=1-1/ref=sr_1_1/002-4128712-7767206?v=glance&s=books
Well done fireblade you just bought him a brand
new PC , and the kid who deserves it gets nil.
BTW Mr Edgar why did you post this in
comp.lang.lisp when there is other nice
groups such :
comp.lang.java
comp.lang.c++.moderated
comp.lang.python etc etc etc ?
If this was about homework maybe , just maybe i could
understand but this is outrageous.
So you wanna win with code written by someone else.
Unless your parents forgeth to tell you that's called cheating .
And if they commission you , and they will ( maybe not now ,
but someday they certainly will) you are marked for life.
Do you wanna trade your conscience for a new box ?
Once a cheater allways a cheater.
···············@lycos.com wrote:
> If this was about homework maybe , just maybe i could
> understand but this is outrageous.
> So you wanna win with code written by someone else.
> Unless your parents forgeth to tell you that's called cheating .
> And if they commission you , and they will ( maybe not now ,
> but someday they certainly will) you are marked for life.
> Do you wanna trade your conscience for a new box ?
> Once a cheater allways a cheater.
Einstein's entertaining criticism comes to mind:
"Our whole educational system suffers from this evil. An exaggerated
competitive attitude is inculcated into the student, who is trained to
worship acquisitive success as a preparation for his future career."
http://www.monthlyreview.org/598einst.htm
Our budding businessman made some elementary mistakes, which is *OK*
since he's learning.
For one thing, keep your businessplan quiet! You're gonna get all sorts
of whiners homing in on your hard-won opportunity. Expect to pay
someone $5 to write well-commented code for you, so you can acquire the
$400 PC. Don't call it a bribe, it's a fair wage! Paying someone to
write Lisp is rare and should be encouraged. Of course, it's best you
came here first to try scoring a freebie.
Don't let these long-haired complainers get to you. The point is you do
work for a payoff, and having a business model is a perfectly sensible
path. If it were supposed to be enjoyable, there'd be a risk of someone
getting pregnant!
http://pentaside.org/article/understanding-power-on-education.html
···············@lycos.com writes:
> If this was about homework maybe , just maybe i could
> understand but this is outrageous.
> So you wanna win with code written by someone else.
> Unless your parents forgeth to tell you that's called cheating .
> And if they commission you , and they will ( maybe not now ,
> but someday they certainly will) you are marked for life.
> Do you wanna trade your conscience for a new box ?
> Once a cheater allways a cheater.
On the other hand, I would not bother. Most of these contests are
rigged. At least all of these contests I participated in were rigged.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
Pascal Bourguignon <···@informatimago.com> writes:
> On the other hand, I would not bother. Most of these contests are
> rigged. At least all of these contests I participated in were rigged.
Yeah, I never won either. ;-)
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
No excuses. No apologies. Just do it.
--- Erik Naggum
·············@hotmail.com
>Well done fireblade you just bought him a brand
>new PC , and the kid who deserves it gets nil.
Oh relax he won't get anything with 2 minute throw away
unless he make it to work with large numbers by himself,
(correct me if i'm wrong but you're the one who explained him
how to do that,no? ) ,in that case i think he deserves the pc
Of course unless there's someone better.
And if there's no kid in the school who can code such simple
thing , than nobody deserves the PC , so our pal is as good as
anybody else.
Of course there is a chance that contest is framed so it doesn't
matter what he'll enclose.
Tayssir John Gabbour
> Expect to pay someone $5 to write well-commented code for you, so you
can
> acquire the $400 PC.
Come on $5 for a $400 .that's only 1.25% .Even in Macedonia pays
better.
David Steuber wrote:
> Pascal Bourguignon <···@informatimago.com> writes:
>
> > On the other hand, I would not bother. Most of these contests are
> > rigged. At least all of these contests I participated in were
rigged.
>
> Yeah, I never won either. ;-)
I won an amiga in 88 , still my favourite and only desktop
i own at home. Carl Sassenrath is a genious .
I'm curios about his REBOL language , wish i could have some
spare time to try it.
fireblade wrote:
> Tayssir John Gabbour writes:
> > Expect to pay someone $5 to write well-commented code for you, so
you
> can
> > acquire the $400 PC.
> Come on $5 for a $400 .that's only 1.25% .Even in Macedonia pays
> better.
$5 for 2 minutes makes $150 per hour .
(* $150-per-hour 8h-per-day 5days-per-week 50week-a-year) makes
300,000 a year .
You're cheap as Ferrari buddy.
fireblade wrote:
> Tayssir John Gabbour
> > Expect to pay someone $5 to write well-commented code for you, so
> > you can acquire the $400 PC.
>
> Come on $5 for a $400 .that's only 1.25% .Even in Macedonia pays
> better.
Just to make sure, my post was an absurd diversion on my part. ;) I
mean, is this "cheating" so important that people should post
criticisms every-single-time? Perhaps it's just a fine opportunity for
someone to solve a puzzle and for others to look.
And I cited two fancy scientists who seem to observe something
monstrous about a system which trains people to work towards acquiring
artificial rewards.
But perhaps forums get overrun with these posts if people don't get
angry, and anyway I haven't devoted much thought to this issue.
David Steuber <·····@david-steuber.com> writes:
> Pascal Bourguignon <···@informatimago.com> writes:
>
>> On the other hand, I would not bother. Most of these contests are
>> rigged. At least all of these contests I participated in were rigged.
>
> Yeah, I never won either. ;-)
Ah, but I *did* won (at least once), and the organizer recognized it,
but they still gave the price to someone else.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
·············@yahoo.com wrote:
> But it's not a homework , it's a school coding contest.
> The prize is a PC for the best programm .
So where's my PC :) ?
·············@yahoo.com writes:
> But it's not a homework , it's a school coding contest.
> The prize is a PC for the best programm .
Cool! What's the submission address?
Christophe
·············@yahoo.com writes:
> Could someone post code that prints all
> breakings of a number entered.
Yes, I am confident that someone could.
How about you?
·············@yahoo.com wrote:
> Could someone post code that prints all
> breakings of a number entered.
> like
> 1 = 1
> 2 = 2
> 1 1
> 3 = 3
> 2 1
> 1 1 1
> 4 = 4
> 3 1
> 2 2
> 2 1 1
> 1 1 1 1
The mathematical term for this calculation is "partitions." (see
http://mathworld.wolfram.com/Partition.html) To be more specific, you
apparently are referring to "unrestricted partitions" because the
addends can repeat.
Knuth discusses the generation of partitions in the forthcoming Volume
4 of The Art of Computer Programming: (see
http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz )
·············@yahoo.com wrote:
> Could someone post code that prints all
> breakings of a number entered.
> like
> 1 = 1
> 2 = 2
> 1 1
> 3 = 3
> 2 1
> 1 1 1
> 4 = 4
> 3 1
> 2 2
> 2 1 1
> 3 1
>
A few things that may help you:
The partition of a number n is easy to calculate -- just add 1 to the
partition of n - 1, 2 to the partition of n - 2, etc. This should be
trivial to code in Lisp.
If you use that algorithm, you'll need to be able to remove duplicates.
The easiest way to do that efficiently will be to prevent dupes from
ever occurring. If you choose some canonical form (say biggest number
to smallest number), it will be easy to make sure you only generate
partitions in that form.
The next optimization to do would be to remove the redundant
calculations of the partition of n - x. The partition of n - x will be
needed to calculate Partition( n - x + 1 ), Partition( n - x + 2 ), ...
Partition( n ). If you remember the previous calculations, this will be
a huge speed improvement.
You could also go about solving this in a completely different way, that
does not require saving all of the previous Partitions. This will
consume a lot less memory, but you'll need to figure out what state to
save when calculating the "next partition".
-- MJF
The function below lists the partitions of n into 5 parts, and I think
it's optimal in the since that there are no wasted iterations: in the
clauses "from ix to y", ix is always less than or equal to y, and
every iteration produces a unique partion. I'm only a few days into lisp,
so I haven't generalised it, but I bet there is an elegant lisp way of
defining a similar but more general function (part n k) that lists the
partitions of n into k parts. The pattern should be obvious from the
k=5 case. Of course, all partitions of n can be obtained from (part n 1)
through (part n n).
I have an idea how to do it using a vector for the ix's and a single
simple loop, but this would just be a translation of how I would do it
in perl and it wouldn't look much like the k=5 case when it was done.
(Still, I would welcome such a solution.) I would like to see something
"more lispy", like defining a function that generates the definion.
(defun part5 (n)
(loop for i1 from 1 to (/ n 5) do
(loop for i2 from i1 to (/ (- n i1) 4) do
(loop for i3 from i2 to ( / (- n i1 i2) 3) do
(loop for i4 from i3 to (/ (- n i1 i2 i3) 2) do
(format t "~D ~D ~D ~D ~D~%" i1 i2 i3 i4 (- n i1 i2 i3 i4))
)
)
)
)
)
On 2005-05-19, Winston Smith <·····@yahoo.com> wrote:
> The function below lists the partitions of n into 5 parts, and I think
> it's optimal in the since that there are no wasted iterations: in the
> clauses "from ix to y", ix is always less than or equal to y, and
> every iteration produces a unique partition. I'm only a few days into lisp,
> so I haven't generalised it, but I bet there is an elegant lisp way of
> defining a similar but more general function (part n k) that lists the
> partitions of n into k parts. The pattern should be obvious from the
> k=5 case. Of course, all partitions of n can be obtained from (part n 1)
> through (part n n).
>
> I have an idea how to do it using a vector for the ix's and a single
> simple loop, but this would just be a translation of how I would do it
> in perl and it wouldn't look much like the k=5 case when it was done.
> (Still, I would welcome such a solution.) I would like to see something
> "more lispy", like defining a function that generates the definition.
>
> (defun part5 (n)
> (loop for i1 from 1 to (/ n 5) do
> (loop for i2 from i1 to (/ (- n i1) 4) do
> (loop for i3 from i2 to ( / (- n i1 i2) 3) do
> (loop for i4 from i3 to (/ (- n i1 i2 i3) 2) do
> (format t "~D ~D ~D ~D ~D~%" i1 i2 i3 i4 (- n i1 i2 i3 i4))
>
> )
> )
> )
> )
> )
Here's a recursive solution:
(defun partition (n &optional k (i 1) p)
(if (not k)
(loop for k from 1 to n do (partition n k))
(if (= k 1)
(print (cons n p))
(loop for j from i to (/ n k) do
(partition (- n j) (- k 1) j (cons j p))))))
(partition n) prints all partitions of n
(partition n k) prints all partitions of n into k parts
(partition n k i) prints all partitions of n into k parts all greater than
or equal to i.
The advantage of keeping track of k is that it allows the optimisation
"for j from i to (/ n k)" as opposed to "for j from i to n".
One line shorter, one argument less, and without loop:
(defun partitions (n &optional k part)
(unless k (setq k n))
(cond ((or (< n 0) (= k 0)))
((= n 0) (print part))
(t (partitions (- n k) k (cons k part))
(partitions n (1- k) part))))
(partitions 10)
Nicolas.
One line shorter, no SETQ! One test less per recursive call. :)
(defun partitions (n &optional (k n) part)
(cond ((or (< n 0) (= k 0)))
((= n 0) (print part))
(t (partitions (- n k) k (cons k part))
(partitions n (1- k) part))))
Marco
Nicolas Neuss wrote:
> One line shorter, one argument less, and without loop:
>
> (defun partitions (n &optional k part)
> (unless k (setq k n))
> (cond ((or (< n 0) (= k 0)))
> ((= n 0) (print part))
> (t (partitions (- n k) k (cons k part))
> (partitions n (1- k) part))))
>
> (partitions 10)
>
> Nicolas.
Marco Antoniotti <·······@cs.nyu.edu> writes:
> (defun partitions (n &optional (k n) part)
> (cond ((or (< n 0) (= k 0)))
> ((= n 0) (print part))
> (t (partitions (- n k) k (cons k part))
> (partitions n (1- k) part))))
Oh, lovely:-) CL again does more than I dared to ask for. Seems that we
finally have reached the optimum. Where are the laptops?
Addendum (solution to the exercise): This is similar to the money exchange
problem in SICP (in fact, partitions are easier). You can trivially change
the above function into a function p which counts the number of partitions
of n using numbers smaller or equal than k. Using memoization then speeds
up the calculation so much that p(1000) can be easily calculated. Of
course, memoizing the (correct) Euler formula speeds it up even more, such
that p(10000) and more becomes easily achievable.
Nicolas.
On 2005-05-20, Nicolas Neuss <·······@iwr.uni-heidelberg.de> wrote:
> One line shorter, one argument less, and without loop:
>
> (defun partitions (n &optional k part)
> (unless k (setq k n))
> (cond ((or (< n 0) (= k 0)))
> ((= n 0) (print part))
> (t (partitions (- n k) k (cons k part))
> (partitions n (1- k) part))))
>
> (partitions 10)
>
> Nicolas.
Nice, but slower. As I explained, the advantage of keeping
track of the number of parts (my k) is that it allows an optimisation.
I, Winston, wrote:
> (defun partition (n &optional k (i 1) p)
> (if (not k)
> (loop for k from 1 to n do (partition n k))
> (if (= k 1)
> (print (cons n p))
> (loop for j from i to (/ n k) do
> (partition (- n j) (- k 1) j (cons j p))))))
>
> ...
>The advantage of keeping track of k is that it allows the optimisation
>"for j from i to (/ n k)" as opposed to "for j from i to n".
If there are k numbers whose sum is n, the smallest must be less than
or equal to n/k. With this observation I was able to eliminate all
culs-de-sac from my recursion. There are culs-de-sac in your (Nicolus's)
recursion (eg., when n < 0). It would be interesting if you could fix
that.
Also, you could change your first two lines to
(defun partitions (n &optional (k n) part)
so yours is really two lines shorter.
Here are time comparisons for n=40:
;Winston
(time (partition 40) )
; Evaluation took:
; 8.41 seconds of real time
; 1.9757 seconds of user run time
; 0.13398 seconds of system run time
; 15,135,067,469 CPU cycles
; [Run times include 0.11 seconds GC run time]
; 0 page faults and
; 60,029,664 bytes consed.
;
;Nicolas
(time (partitions 40) )
; Evaluation took:
; 71.68 seconds of real time
; 7.922796 seconds of user run time
; 0.518921 seconds of system run time
; 129,022,811,885 CPU cycles
; [Run times include 0.28 seconds GC run time]
; 0 page faults and
; 161,695,256 bytes consed.
;
T
Winston
Winston Smith <·····@yahoo.com> writes:
> If there are k numbers whose sum is n, the smallest must be less than or
> equal to n/k. With this observation I was able to eliminate all
> culs-de-sac from my recursion. There are culs-de-sac in your (Nicolus's)
> recursion (eg., when n < 0). It would be interesting if you could fix
> that.
I think it is very misguided to optimize this quite useless function whose
real bottleneck is printing out the results, so I do not want to
participate in this. You can do something, of course, using declarations,
filtering out the easy case k=1, etc., but it really think that this should
NOT be done at this point. YMMV.
Nicolas.
On 2005-05-21, Nicolas Neuss <·······@iwr.uni-heidelberg.de> wrote:
> I think it is very misguided to optimize this quite useless function whose
> real bottleneck is printing out the results, so I do not want to
> participate in this. You can do something, of course, using declarations,
> filtering out the easy case k=1, etc., but it really think that this should
> NOT be done at this point. YMMV.
I had already optimised it -- your 'improvement' of my program was,
from my point of view, a trivial de-optimisation of it, which point I
tried to make diplomatically before. It's 'very misguided' to trivially
de-optimise a program in a sub-thread about optimising a program and
think one has accomplished something.
On 2005-05-21, Nicolas Neuss <·······@iwr.uni-heidelberg.de> wrote:
> BTW, a strange timing result. I measure the same speed for both our
> functions (which is also to be expected since the bottleneck lies in
> printing). Try replacing the PRINT with nil.
The timing differences are real. It's not strange at all. As I have
explained, your recursion has a lot of unproductive dead ends. Mine
has none.
> printing). Try replacing the PRINT with nil.
If you insist.
;winston print -> nil
(defun partition (n &optional k (i 1) p)
(if (not k)
(loop for k from 1 to n do (partition n k))
(if (= k 1) nil ; was (print (cons n p))
(loop for j from i to (/ n k) do
(partition (- n j) (- k 1) j (cons j p))))))
;nicolus print -> nil
(defun partitions (n &optional (k n) part)
(cond ((or (< n 0) (= k 0)))
((= n 0) nil) ; was (print part)
(t (partitions (- n k) k (cons k part))
(partitions n (1- k) part))))
;n=40
;winston
(time (partition 40))
; Evaluation took:
; 1.17 seconds of real time
; 1.065838 seconds of user run time
; 0.015997 seconds of system run time
; 2,109,293,307 CPU cycles
; [Run times include 0.07 seconds GC run time]
; 0 page faults and
; 22,048,000 bytes consed.
;
NIL
;nicolus
(time (partitions 40))
; Evaluation took:
; 6.53 seconds of real time
; 5.722131 seconds of user run time
; 0.120981 seconds of system run time
; 11,741,432,263 CPU cycles
; [Run times include 0.21 seconds GC run time]
; 0 page faults and
; 120,912,528 bytes consed.
;
;n=60
;winston
(time (partition 60))
; Evaluation took:
; 27.5 seconds of real time
; 23.739391 seconds of user run time
; 0.459931 seconds of system run time
; 49,502,725,998 CPU cycles
; [Run times include 0.9 seconds GC run time]
; 0 page faults and
; 509,588,072 bytes consed.
;
NIL
;nicoulus
(time (partitions 60))
; Evaluation took:
; 201.94 seconds of real time
; 175.25435 seconds of user run time
; 3.02054 seconds of system run time
; 363,506,862,906 CPU cycles
; [Run times include 6.57 seconds GC run time]
; 0 page faults and
; 3,648,018,704 bytes consed.
;
T
Winston
Winston Smith <·····@yahoo.com> writes:
> On 2005-05-21, Nicolas Neuss <·······@iwr.uni-heidelberg.de> wrote:
>> I think it is very misguided to optimize this quite useless function whose
>> real bottleneck is printing out the results, so I do not want to
>> participate in this. You can do something, of course, using declarations,
>> filtering out the easy case k=1, etc., but it really think that this should
>> NOT be done at this point. YMMV.
>
> I had already optimised it -- your 'improvement' of my program was,
> from my point of view, a trivial de-optimisation of it, which point I
> tried to make diplomatically before. It's 'very misguided' to trivially
> de-optimise a program in a sub-thread about optimising a program and
> think one has accomplished something.
Your mileage obviously varies. But if you are so keen on performance you
should consider using another Lisp implementation or another computer.
Here are the times for CMUCL on a P4/2.4GHz which is more that 100 times
faster.
(partition 40)
; 0.024997 seconds of user run time
(partitions 40)
; 0.043994 seconds of user run time
(partition 60)
; 0.616906 seconds of user run time
(partitions 60)
; 1.503771 seconds of user run time
Indeed, your version is still 2-3 times faster. But if you think this
speed difference matters when printing is included, let's leave it with
that.
Nicolas.
On 2005-05-22, Nicolas Neuss <·······@iwr.uni-heidelberg.de> wrote:
> Winston Smith <·····@yahoo.com> writes:
>
>> On 2005-05-21, Nicolas Neuss <·······@iwr.uni-heidelberg.de> wrote:
>>> I think it is very misguided to optimize this quite useless function whose
>>> real bottleneck is printing out the results, so I do not want to
>>> participate in this. You can do something, of course, using declarations,
>>> filtering out the easy case k=1, etc., but it really think that this should
>>> NOT be done at this point. YMMV.
>>
>> I had already optimised it -- your 'improvement' of my program was,
>> from my point of view, a trivial de-optimisation of it, which point I
>> tried to make diplomatically before. It's 'very misguided' to trivially
>> de-optimise a program in a sub-thread about optimising a program and
>> think one has accomplished something.
>
> Your mileage obviously varies. But if you are so keen on performance you
> should consider using another Lisp implementation or another computer.
> Here are the times for CMUCL on a P4/2.4GHz which is more that 100 times
> faster.
> ...
> Indeed, your version is still 2-3 times faster. But if you think this
> speed difference matters when printing is included, let's leave it with
> that.
The kind of performance I was interested in this sub-thread has
nothing to do with printing or who has the fastest CPU. I initiated
this sub-thread, "Breaking numbers (partial optimal solution)", with a
post in which I explained that I had a very specific sense of optimal
in mind -- "optimal in the sense that there are no wasted iterations".
It's an academic question, a question of algorithms, not computers.
You don't have to be interested in it. You can be interested in golf
(writing the shortest program) instead.
But, you have to admit, if you take your golf clubs into a pool hall,
jump up on the billiards table in the middle of a game, and putt the
eight ball into the corner pocket in two strokes, the folks in the pool
hall are not going to be impressed. If in response they say "nice,
but try a pool cue next time, and by the way here's how you could have
done it in one stroke", that would be noblesse oblige.
You could reply "billiards is for sissys," "shove that pool stick where
the sun don't shine", "make them holes in the table bigger so it's easier
to knock the ball in," or "if you think this speed difference matters
when printing is included, let's leave it with that". It's all the same
to me.
Understanding what makes recursive algorithms slow or fast in a theortical
sense is worthwhile, even if it doesn't matter when the output of the
alogorithm is printed on the screen of Nicolas Neuss' P4/2.4Ghz computer
in this particular case.
Winston
Winston Smith <·····@yahoo.com> writes:
> (time (partitions 40) )
> ; Evaluation took:
> ; 71.68 seconds of real time
> ; 7.922796 seconds of user run time
BTW, a strange timing result. I measure the same speed for both our
functions (which is also to be expected since the bottleneck lies in
printing). Try replacing the PRINT with nil.
Nicolas.
On Sat, 21 May 2005 09:02:02 +0200, Nicolas Neuss <·······@iwr.uni-heidelberg.de> wrote:
> Winston Smith <·····@yahoo.com> writes:
>
>> (time (partitions 40) )
>> ; Evaluation took:
>> ; 71.68 seconds of real time
>> ; 7.922796 seconds of user run time
>
> BTW, a strange timing result. I measure the same speed for both our
> functions (which is also to be expected since the bottleneck lies in
> printing). Try replacing the PRINT with nil.
>
> Nicolas.
I'm a lisp newbie (I wrote my "hello world" about two weeks ago),
but I have to say I've enjoyed this thread, and am pleasantly
surprised at how helpful this newsgroup is.
To add my $0.02, here's my solution: it's an "iterator" that
computes the "next" partition, returning nil when there aren't any
more. And it does it in O(1) time. No loops. (It looks complicated only
because there are so many corner cases.)
I'm pretty sure it will run faster than the previous recursive
solutions I've seen in this thread. In those cases, the partitions are
embedded conceptually as the leaves of a tree, and the overhead of
traversing this tree is a big penalty.
(defun next-par (mu)
(let* ((a (car mu)) (mu (cdr mu)) (b (car mu)))
(if b
(let ((nu (cons (- a b) (cons b mu))))
(if (>= (car nu) b) nu
(progn
(setf nu (cons (1- a) (cons (1+ b) (cdr mu))))
(cond
((>= (car nu) (cadr nu)) nu)
((not (cadr mu)) nil)
((> b 1) (cons (+ a b -1) (cons (1+ (cadr mu)) (cddr mu))))
((caddr mu) (cons 2 (cons 2 (cdddr mu))))))))
(when (and a (> a 1)) (list (1- a) 1)))))
; Try these:
(do ((nu '(10) (next-par nu))) ((not nu)) (print nu)))
(do ((nu '(60) (next-par nu)) (ct 0 (1+ ct))) ((not nu) ct)))