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

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.

    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 }
        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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://78337]
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
Find Nodes?
    Voting Booth?

    For retirement, I am banking on:

    Results (125 votes), past polls