Re: Sum of N elements in an M element array
by Corion (Patriarch) 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? | [reply] [d/l] |
|
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);
| [reply] [d/l] |
|
Thanks all for your suggestions. I managed w Math:Combinatorics to get what i want.
| [reply] |
Re: Sum of N elements in an M element array
by tybalt89 (Monsignor) 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
| [reply] [d/l] [select] |
|
| [reply] [d/l] |
|
| [reply] |
Re: Sum of N elements in an M element array
by Cristoforo (Curate) on Feb 02, 2020 at 01:10 UTC
|
| [reply] |
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.
| [reply] [d/l] [select] |
Re: Sum of N elements in an M element array
by Marshall (Canon) 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
| [reply] [d/l] [select] |
|
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.
| [reply] [d/l] |
|
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
| [reply] [d/l] |
|
|
|
|
Thanks Marshall. This helps. Never a great user of glob() function , will try it out.
| [reply] |
|
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
| [reply] [d/l] |
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.
| [reply] [d/l] [select] |
|
| [reply] [d/l] |