Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
here another approach, it calculates the possible partial sums in %step with increasing possible $delta.

the solutions are than printed by walking back from $target to zero.

NB: it creates two kind of outputs, a tree with partial solutions and a result hash.

unfortunately this only works efficiently for unique deltas, I'll probably try to fix it tomorrow.

(or better leave it open for the interested reader ;)

use strict; use warnings; use Data::Dump qw/pp dd/; use Data::Dumper; # --- input my @input = (1,99,2,40,50,60,90,3,5,95,100); my $target = 100; my %steps = ( 0 => []); # --- processing my @deltas = sort { $a <=> $b } @input ; for my $delta ( @deltas ) { for my $last (keys %steps) { my $next = $last + $delta; unshift @{$steps{$next}},$last if $next <= $target-$delta # $delta grows! or $next == $target; # goal } # pp $delta, \%steps; } pp \%steps; # --- output my %free; $free{$_}++ for @deltas; our $level = -1; sub walk_back { my ($target,$h_path)=@_; local $level = $level +1; for my $last (@{$steps{$target}}) { my $delta = $target-$last; next unless $free{$delta}; local $free{$delta} = $free{$delta}-1; print "\t" x $level , "+$delta\n"; my $sub_path = $h_path->{$delta} = {}; if ( $last>0 ) { walk_back($last,$sub_path) } else { print "\n\n"; } } } my %path; walk_back($target,\%path); pp \@deltas; print Dumper \%path;

{ "0" => [], "1" => [0], "2" => [0], "3" => [0, 1], "4" => [1], "5" => [0, 2], "6" => [1, 3], "7" => [2], "8" => [3], "9" => [4], "10" => [5], "11" => [6], "40" => [0], "41" => [1], "42" => [2], "43" => [3], "44" => [4], "45" => [5], "46" => [6], "47" => [7], "48" => [8], "49" => [9], "50" => [0, 10], "51" => [11], "100" => [0, 1, 5, 10, 40, 50], } [1, 2, 3, 5, 40, 50, 60, 90, 95, 99, 100] +100 +99 +1 +95 +5 +3 +2 +90 +5 +3 +2 +60 +40 +50 +40 +5 +3 +2 $VAR1 = { '99' => { '1' => {} }, '50' => { '40' => { '5' => { '3' => { '2' => {} } } } }, '95' => { '5' => {}, '3' => { '2' => {} } }, '100' => {}, '60' => { '40' => {} }, '90' => { '5' => { '3' => { '2' => {} } } } };

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery


In reply to Re: Find combination of numbers whose sum equals X by LanX
in thread Find combination of numbers whose sum equals X by harangzsolt33

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others imbibing at the Monastery: (4)
    As of 2021-01-25 01:45 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      Notices?