Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re: How to generate restricted partitions of an integer

by BrowserUk (Pope)
on Nov 11, 2004 at 12:14 UTC ( #407008=note: print w/replies, xml ) Need Help??


in reply to How to generate restricted partitions of an integer

Encode the knowledge of what substitions are possible as data instead of code and let the regex engine take the strain.

#! perl -slw use strict; my %subs = ( 100 => '50 50', 50 => '20 20 10', 20 => '10 10', 10 => '5 5', 5 => '2 2 1', 2 => '1 1', ); my $re_conversion = '(' . join( '|', sort{ length $b <=> length $a } keys %subs ) . ')'; my $input ); do { printf 'Denomination to change[100|50|20|10|5|2]: '; chomp( $input = <STDIN> ); } until exists $subs{ $input }; print $input while $input =~ s[$re_conversion][$subs{ $1 }]; __END__ [11:58:38.32] P:\test>406984 Denomination to change[100|50|20|10|5|2]: 20 10 10 5 5 10 2 2 1 5 10 1 1 2 1 5 10 1 1 1 1 1 5 10 1 1 1 1 1 2 2 1 10 1 1 1 1 1 1 1 2 1 10 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 5 5 1 1 1 1 1 1 1 1 1 1 2 2 1 5 1 1 1 1 1 1 1 1 1 1 1 1 2 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Replies are listed 'Best First'.
Re^2: How to generate restricted partitions of an integer
by hv (Parson) on Nov 11, 2004 at 13:17 UTC

    This will miss many conversions such as 10 => 2 2 2 2 2 (not catered for by %subs) and 20 => 5 5 5 5 (not catered for by the single iterative substitution approach).

    Hugo

      But...there isn't a 2 euro note, per the original OP (I wouldn't know...I'm a dumb American). The breaking of a 20 into 4 5's is valid, though.

      thor

      Feel the white light, the light within
      Be your own disciple, fan the sparks of will
      For all of us waiting, your kingdom will come

      Agreed. It's an idea that needs some work.


      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
      "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (8)
As of 2020-10-20 21:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (210 votes). Check out past polls.

    Notices?