adding combinations of arrays (of arrays)

[aquinom]

This is a combinatorial problem I think in essence, but I'm not interested in the number of combinations rather how to get them. If I'm working with a number of arrays (stored in an AoA or whatever data structure you want, but I think AoA is best) I need to return the sum of the elements of each combination of the arrays. I can do NC2 but I can't seem to figure out how to get up to NC3 let alone NCN with an algorithm (which is what I'm hoping someone can help me with) (All arrays in the AoA are the same size, hence my use of @$AoA[0] for size in the 3rd for loop) Here's NC2:

#!/usr/bin/perl
use strict;
use warnings;
my @newAoA;
my @AoA = ( [1,1,1],[0,0,0],[1,0,1],[0,0,1] );
my $arrRef = $AoA[0];
my $c = 0;
for (my $i = 0; $i < scalar @AoA ; $i++){
    for (my $j =$i+1; $j< scalar @AoA ; $j++){
       for (my $k=0; $k< scalar @$arrRef; $k++){  ### scalar @$AoA[0] 
+doesn't work, maybe im losing my mind but thats the same as @$arrRef 
           push @{$newAoA[$c]}, ($AoA[$i][$k] + $AoA[$j][$k]);
        }
      $c++;
    }
}

foreach my $array (@newAoA){
    print @$array,"\n";
}

foreach my $array (@newAoA){
    print @$array,"\n";
}

prints:

111
212
112
101
001
102

edit: sorry, I was a bit rusty too much java lately *sigh*. This code works

[TJPride]

It does what you're trying to do, only with single values rather than arrays. I think I know what you're trying to do now, though I have no idea why:

use strict;
use warnings;

my @vals = ( [1,1,1],[0,0,0],[1,0,1],[0,0,1] );
my $n = 2;
my @solutions;

nSum(\@vals, \@solutions, [], -1, $n);

print "@$_\n" for @solutions;

sub nSum {
    my ($vals, $solutions, $sums, $i, $n) = @_;
    my (@sums, $j, $k);

    $n--;
    for $j (($i+1)..$#$vals) {
        @sums = @$sums;
        for $k (0..$#{$vals->[0]}) {
            $sums[$k] += $vals->[$j][$k];
        }
        if ($n) {
            nSum($vals, $solutions, \@sums, $j, $n);
        }
        else {
            push @$solutions, [@sums];
        }
    }
}

You can change the number of elements in the arrays or AoA's and also the value for $n and you should get accurate results regardless.

[aquinom]

Hehe well the reason is that these integer values are numbers of non-reference alleles at specific sites and and AoA will be created for each gene and I'm taking these combinations and doing a correlation on them to a case-control pattern so to see if adding any of the sites in a gene produces a fit to that model. Yeah it's all hypothetical so if you're a statistician I know this likely isn't an optimal approach to looking for mutations at many sites over a gene to identify a target gene for further testing...yeah I am sure you didn't want to know all that much anyways!

[Anonymous Monk]

Thanks, some preliminary tests on this work so I think you nailed it. I'm very grateful.

[TJPride]

Not sure precisely what you're trying to do, since your code is one big mass of logic errors and bad Perl. But here's some code for NCN. I use recursion to allow for the variable number of nested loops.

use strict;
use warnings;

my @vals = (1, 2, 3, 4, 5);
my $n = 3;
my @solutions;

nSum(\@vals, \@solutions, 0, -1, $n);

print "@solutions\n";

sub nSum {
    my ($vals, $solutions, $sum, $i, $n) = @_;

    if (--$n) {
        nSum($vals, $solutions, $sum + $vals->[$_], $_, $n)
            for ($i+1)..$#$vals;
    }
    else {
        push @$solutions, $sum + $vals->[$_]
            for ($i+1)..$#$vals;
    }
}

[aquinom]

Not sure what your code is supposed to do, it prints: 6 7 8 8 9 10 9 10 11 12. But anyways, you should see more clearly what my idea is now if you run my updated code.

[BrowserUk]

I've read your description and your modified code several times, and I'm still at a loss to understand what you are doing. And the output from your code does not clarify it for me.

A wordful description -- something more than "I need to return the sum of the elements of each combination of the arrays. " and maybe a worked example might clarify things and get you more useful responses.

[aquinom]

Well I'm not sure how to more aptly say it, I'm sorry it's confusing for you. So if an array of arrays has 4 elements as in this example there are various combinations of these arrays that are possible depending on what your k is in n-choose-k. My example sums every combination in n-choose-2. So let's simplify it for the sake of expressing the problem: Array Of Arrays = 1,2,3,4 (each is an array) the six combinations choosing two at a time are 1+2,1+3,1+4,2+3,2+4,3+4 or six combinations (which is mathematically what 4 choose 2 equals). so if array 1 is 1,1,1,1 and array 2 is 1,1,0,0 the first SUMMED combination (i.e. 1+2) = 2,2,1,1 : this is how the outputs are created.

[BrowserUk]

That is much clearer. You want something like this?

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use Algorithm::Combinatorics qw[ combinations ];


our $N //= 4;
our $K //= 2;
our $M //= 3;

my @AoA = map{
    [ map int( rand 2 ), 1 .. $M ]
} 1 .. $N;

pp 'Input:', \@AoA;

my @newAoA;

my $i = combinations( \@AoA, $K );
while( my $comb = $i->next ) {
    my @sums;
    for my $a ( @{ $comb } ) {
        $sums[ $_ ] += $a->[ $_ ] for 0 .. $#{ $a };
    }
    push @newAoA, \@sums;
}

pp 'Output:', \@newAoA;

__END__
c:\test>940693
("Input:", [[0, 1, 1], [0, 1, 1], [1, 0, 1], [0, 1, 0]])

(
  "Output:",
  [[0, 2, 2], [1, 1, 2], [0, 2, 1], [1, 1, 2], [0, 2, 1], [1, 1, 1]],
)


c:\test>940693 -N=5 -M=2 -K=3
("Input:", [[0, 1], [1, 0], [1, 1], [0, 1], [0, 0]])

(
  "Output:",
  [
    [2, 2],
    [1, 2],
    [1, 1],
    [1, 3],
    [1, 2],
    [0, 2],
    [2, 2],
    [2, 1],
    [1, 1],
    [1, 2],
  ],
)


c:\test>940693 -N=5 -M=4 -K=3
(
  "Input:",
  [
    [1, 1, 1, 1],
    [0, 1, 1, 0],
    [1, 1, 0, 1],
    [1, 1, 1, 1],
    [0, 1, 1, 1],
  ],
)

(
  "Output:",
  [
    [2, 3, 2, 2],
    [2, 3, 3, 2],
    [1, 3, 3, 2],
    [3, 3, 2, 3],
    [2, 3, 2, 3],
    [2, 3, 3, 3],
    [2, 3, 2, 2],
    [1, 3, 2, 2],
    [1, 3, 3, 2],
    [2, 3, 2, 3],
  ],
)