Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Sum of N elements in an M element array

by abhay180 (Sexton)
on Feb 01, 2020 at 07:32 UTC ( #11112217=perlquestion: print w/replies, xml ) Need Help??

abhay180 has asked for the wisdom of the Perl Monks concerning the following question:

Hi! Say i have array of 5 numbers (a,b,c,d,e). (repetition allowed)
I want sums of all possible 4 elements; a+b+c+d a+b+c+e a+b+d+e ... ... all possible 3 elements ; a+b+c a+b+d a+b+e .. .. all possible 3 elements... all possible 2 elements
Is there a simple way to do this?

Replies are listed 'Best First'.
Re: Sum of N elements in an M element array
by Corion (Pope) on Feb 01, 2020 at 09:11 UTC

    There are many simple ways to do this. I would look at Data::PowerSet to generate sets of all numbers to sum, or program it myself by using the binary digits of a counter to indicate whether an element should be included:

    00000 # (no element summed) 00001 # e 00010 # d 00011 # d+e 00100 # c ... 11111 # a+b+c+d+e

    What code have you written and where do you have problems?

      Thanks Corion. The exact problem is about finding all the combinations. I find Math:Combinatorics useful as well. Here is what i did to gather all 2-item combinations from N item array. I wasn't sure how i would do it for any M items.
      @a=(1..5); my @comb=""; for(my $i=0;$i<=$#a;$i++) { for(my $j=0;$j<=$#a;$j++) { next if $i==$j; if ($a[$i] < $a[$j]) { push @comb, "$a[$i] , $a[$j]" ; } else { push @comb, "$a[$j] , $a[$i]" ; } } } shift @comb; use List::MoreUtils qw(uniq); @comb = uniq(@comb);
        Thanks all for your suggestions. I managed w Math:Combinatorics to get what i want.
Re: Sum of N elements in an M element array
by tybalt89 (Parson) on Feb 01, 2020 at 19:04 UTC
    #!/usr/bin/perl use strict; # https://perlmonks.org/?node_id=11112217 use warnings; use List::Util qw( sum ); my @array = qw( 1 2 3 4 5 ); local $_ = "@array"; for my $possible ( 1 .. @array ) { my $pattern = join '.+?', ('\b(\d+)\b') x $possible; local $" = '+'; /$pattern(?{print "@{^CAPTURE} = ", sum(@{^CAPTURE}), "\n"})(*FAIL)/ +; }

    Outputs:

    1 = 1 2 = 2 3 = 3 4 = 4 5 = 5 1+2 = 3 1+3 = 4 1+4 = 5 1+5 = 6 2+3 = 5 2+4 = 6 2+5 = 7 3+4 = 7 3+5 = 8 4+5 = 9 1+2+3 = 6 1+2+4 = 7 1+2+5 = 8 1+3+4 = 8 1+3+5 = 9 1+4+5 = 10 2+3+4 = 9 2+3+5 = 10 2+4+5 = 11 3+4+5 = 12 1+2+3+4 = 10 1+2+3+5 = 11 1+2+4+5 = 12 1+3+4+5 = 13 2+3+4+5 = 14 1+2+3+4+5 = 15

      I stared a little while at the code you provided wondering why and how it works and jumped to the conclusion that using Data::PowerSet is by far the better solution. Regards, Karl

      «The Crux of the Biscuit is the Apostrophe»

      perl -MCrypt::CBC -E 'say Crypt::CBC->new(-key=>'kgb',-cipher=>"Blowfish")->decrypt_hex($ENV{KARL});'Help

        He's building a regex which is trying to match n numbers, because of the (fail) it keeps backtracking to match all possibilities.

        The embedded Perl code ensures the output before backtracking to the next match.

        I actual like seeing such code as answers to lazy questions. ;)

Re: Sum of N elements in an M element array
by Cristoforo (Curate) on Feb 02, 2020 at 01:10 UTC
Re: Sum of N elements in an M element array
by johngg (Canon) on Feb 03, 2020 at 22:59 UTC

    It's probably a bit late to post this but since the code is now written I might as well. Corion's mention of a binary counter made me think of this thread in which I ventured this solution. I can use this to generate all strings of, say, three ones and two zeros and then use a regex and pos to generate an array of elements to sum. Because the iterator returns strings in this order for the above example

    00111 01011 01101 01110 10011 10101 10110 11001 11010 11100

    I use unshift rather than push to build the array of sums so that they are in the same order as in the OP. The routine returns a ref. to an AoAoH where elements 0 and 1 are empty, element 2 contains an array of hashes of all possible 2-element sums where the key is the string representing the sum and the value is the result, element 3 an array of hashes of 3-element sums etc. The code:-

    The results:-

    I hope this is of interest.

    Cheers,

    JohnGG

Re: Sum of N elements in an M element array
by Marshall (Abbot) on Feb 02, 2020 at 03:14 UTC
    This might help?
    There are duplicates, eg 12 and 21.
    #!/usr/bin/perl use strict; use warnings; my @perms = glob "{1,2,3}" x 3; print "@perms\n"; @perms = glob "{1,2,3}" x 2; print "@perms\n"; __END__ Prints: 111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 23 +3 311 312 313 321 322 323 331 332 333 11 12 13 21 22 23 31 32 33
    Another run:
    #!/usr/bin/perl use strict; use warnings; my @perms = glob "{a,b,c,d,e}" x 3; print "@perms\n"; print "\n"; @perms = glob "{a,b,c,d,e}" x 2; print "@perms\n"; __END__ Prints: aaa aab aac aad aae aba abb abc abd abe aca acb acc acd ace ada adb ad +c add ade aea aeb aec aed aee baa bab bac bad bae bba bbb bbc bbd bbe + bca bcb bcc bcd bce bda bdb bdc bdd bde bea beb bec bed bee caa cab +cac cad cae cba cbb cbc cbd cbe cca ccb ccc ccd cce cda cdb cdc cdd c +de cea ceb cec ced cee daa dab dac dad dae dba dbb dbc dbd dbe dca dc +b dcc dcd dce dda ddb ddc ddd dde dea deb dec ded dee eaa eab eac ead + eae eba ebb ebc ebd ebe eca ecb ecc ecd ece eda edb edc edd ede eea +eeb eec eed eee aa ab ac ad ae ba bb bc bd be ca cb cc cd ce da db dc dd de ea eb ec e +d ee
      For the record: your output is significantly different from others, because you allow single elements to appear multiple times, like in "aaa".

      The OP said "repetitions allowed", but I read this as the numbers don't need to be pairwise different.

      To increase the confusion does his demo not show any repetitions.

      >

      ... all possible 3 elements ; a+b+c a+b+d a+b+e ...

      slightly annoying.

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

        Ok, I wanted to show the glob combination gizmo and the spec wasn't perfect.
        For permutations 3 of a set of 5, consider the following.
        No element is repeated, meaning no element of the input array appears more than once per "sum"
        I just sorted the output in my program editor rather than adding that feature to the Perl code.
        #!/usr/bin/perl use strict; use warnings; use Algorithm::Permute; my $p = Algorithm::Permute->new(['a','b','c','d','e'], 3); while (my @res = $p->next) { print join("+", @res), "\n"; } __END__ # I just used my editor to sort the output # adapt the above code as you wish a+b+c a+b+d a+b+e a+c+b a+c+d a+c+e a+d+b a+d+c a+d+e a+e+b a+e+c a+e+d b+a+c b+a+d b+a+e b+c+a b+c+d b+c+e b+d+a b+d+c b+d+e b+e+a b+e+c b+e+d c+a+b c+a+d c+a+e c+b+a c+b+d c+b+e c+d+a c+d+b c+d+e c+e+a c+e+b c+e+d d+a+b d+a+c d+a+e d+b+a d+b+c d+b+e d+c+a d+c+b d+c+e d+e+a d+e+b d+e+c e+a+b e+a+c e+a+d e+b+a e+b+c e+b+d e+c+a e+c+b e+c+d e+d+a e+d+b e+d+c
      Thanks Marshall. This helps. Never a great user of glob() function , will try it out.
        This glob thing is a bit weird.
        Good Luck!
        Consider also:
        #!/usr/bin/perl use strict; use warnings; my @combos = glob "{a,b,c}{1,2}"; print "@combos\n"; __END__ Prints: a1 a2 b1 b2 c1 c2
Re: Sum of N elements in an M element array
by johngg (Canon) on Feb 17, 2020 at 13:54 UTC

    I put together a small benchmark comparing the Algorithm::Permute approach demonstrated by Marshall, a solution using combinations() from Algorithm::Combinatorics as mentioned by AnomalousMonk and my bit-shuffling permutary routine (which I now understand has been misnamed, I always confused permutations and combinations at school). I have not included tybalt's solution because it would take too much mangling to produce output in the form that would pass the tests. I have also omitted trying to produce a solution using glob because as far as I can see, whichever way you slice it, it breaks down as soon as array indexes go into double figures or array values do if acting on them directly.

    In each case I preserve the order demonstrated in the OP, effectively working from left to right with no repeated elements. Using array indices gets around any problems with duplicates or sorting, as noted by AnomalousMonk and the results show that calculating all permutations then filtering out re-ordered duplicates is an enormous hit on performance. The code:-

    The results:-

    ok 1 - combinations ok 2 - johngg ok 3 - permutations (warning: too few iterations for a reliable count) Rate permutations johngg combinations permutations 4.76e-02/s -- -100% -100% johngg 70.0/s 146784% -- -69% combinations 229/s 480720% 227% -- 1..3

    I hope this is of interest.

    Cheers,

    JohnGG

      ... I always confused permutations and combinations at school ...

      Not to mention the many sub-species of each :)


      Give a man a fish:  <%-{-{-{-<

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (4)
As of 2020-07-07 00:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?