Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: (Golf as well): List of Partitions

by danger (Priest)
on May 06, 2001 at 13:15 UTC ( #78337=note: print w/ replies, xml ) Need Help??


in reply to (Golf as well): List of Partitions

Well, if I'm allowed to generate a list of strings rather than a list of lists, then I'll kick off the golfing with a strict compliant one in 70 characters (inside of P):

#!/usr/bin/perl -w use strict; sub P { my($i)=@_;push@_,grep!/[^1-$i]/,map"$i$_",P($_[0]-$i)and$i--while$i;@_ } for(P(5)){ print "$_\n"; } __END__ # output is 5 41 32 311 221 2111 11111

If you do insist on a list of lists, we can tack on the following 16 character wrapper sub to call instead of P:

sub W{map{[split//]}&P}

Update: In response to my major oversight that tilly's followup points out, all I can say is:
"Rats! Last time I go golfing in the middle of the night!"
:-)

Update2:Ok, in the light of day, here's a recursive one in 82 chars (ignoring unnecessary whitespace) that returns a list of lists:

sub P{ my$i=my$n=pop; push@_,grep{!grep{$_>$i}@$_}map{[$i,@$_]}P($n-$i)while$i-->1; [$n],@_ }


Comment on Re: (Golf as well): List of Partitions
Select or Download Code
Re (tilly) 2: (Golf as well): List of Partitions
by tilly (Archbishop) on May 06, 2001 at 16:06 UTC
    Cute idea, but your output from P(11) is..ambiguous.

    And P(12) has the incorrect "1011" entry for 10, 11.

    UPDATE
    Nice improvement. It can indeed be compressed. Here is 74 characters:

    sub P{ my$n=pop;[$n],map{my$i=$_;grep{!grep$_>$i,@$_}map[$i,@$_],P($n-$i)}1.. +$n-1 }

      Hmm, and we can shave that down to 71 chars:

      sub P{ [@_],map{my$i=$_;grep{!grep$_>$i,@$_}map[$i,@$_],P($_[0]-$i)}1..$_[0]- +1 }
        Nice, now slimed down to 64 on the knowledge that the partitions are always sorted from largest number to smallest...
        sub P{ [@_],map{my$i=$_;map$$_[0]>$i?():[$i,@$_],P($_[0]-$i)}1..$_[0]-1 }
        UPDATE
        Saved an additional char because my map could be commified.

        UPDATE 2
        Scraping the barrel for 61:

        sub P{ my$i;[@_],map{map$$_[0]>$i?():[$i,@$_],P($_[0]-++$i)}2..$_[0] }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://78337]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (12)
As of 2014-10-23 13:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (125 votes), past polls