The interval is not the number of arrays within the group, it is the interval covered by the integer keys to the arrays in the group.

Therefore, with an interval of 2, 4 & 6 are not in the same group. Neither are 8 & 11.

Also, to avoid redoing work already done, when a new array is added to the group, it is necessary not only to discard any old arrays that are no longer a part of the group (Ie. no longer covered by the interval), but distinguish between those arrays that remain (from the previous group), and the new one that has been added.

It is quite tricky to even describe, let alone code!

Oh, I missed that! Something like this then:

#!/usr/lib/perl
use strict;
use warnings;

my $kPoolSpan = 2;
my %hash      = (
    3  => [1 .. 2],
    4  => [2 .. 2],
    6  => [4 .. 5],
    7  => [2 .. 6],
    8  => [1 .. 3],
    11 => [5 .. 10],
    );
my @indexes = sort {$a <=> $b} keys %hash;
my @pool;

while (@indexes) {
    my $oldPoolSize = @pool;

    push @pool, shift @indexes if !@pool;
    push @pool, shift @indexes
        while @indexes && $pool[0] + $kPoolSpan >= $indexes[0];

    my $poolSum;
    my @new = @pool[$oldPoolSize .. $#pool];

    for my $poolEntry (@pool) {
        $poolSum += $_ for @{$hash{$poolEntry}};
    }

    print "Pool @pool sum (added @new): $poolSum\n";
    shift @pool while @indexes && @pool && $pool[0] + $kPoolSpan < $in
+dexes[0];
}
[download]

Prints:

Pool 3 4 sum (added 3 4): 5
Pool 4 6 sum (added 6): 11
Pool 6 7 8 sum (added 7 8): 35
Pool 11 sum (added 11): 45
[download]

True laziness is hard work

Thank you. With a few tweaks to deal with stuff not mentioned in the question, this is my addaption of your code:

our $INT //= 4;

my %hash;
push @{ $hash{ calcScore( $_ ) } }, $_ while <>;

my @grpKeys = sort{ $a <=> $b } keys %hash;

my @oldGrp;
while( my $next = shift @grpKeys ) {

    ## Remove any arrays from teh previously processed group
    ## that are below the interval of the next value - $INT
    shift @oldGrp while ( $next - $oldGrp[ 0 ] ) > $INT.

    ## Process items in the new array
    for my $i ( 0 .. $#{ $hash{ $next } } ) {

        ## against each of the (other) items in the new array
        for my $j ( $i+1 .. $#{ $hash{ $next } } ) {
            process( $i, $j );
        }

        ## and all of the items in each of the arrays 
        ## retained from the previous pass
        for my $g ( @oldGrp ) {
            for my $j ( 0 .. $#{ $hash{ $g } } ) { 
                process( $i, $j );
            }
        }
    }
    
    ## Add this array to the previously processed group
    push @oldGrp, $next;
}
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

It seems to me, therefore, that the event of “a new array is added to the group” is .. “somehow, quite significant.”   That is to say, the definition of “the problem that is to be solved” is in some way dynamic.   (Perhaps it is in some way reliant upon what has already been solved?)

I cordially suggest that this might well prove to be a crux of the problem:   that the most-desirable solution to this problem is not one that can be resolved statically, but rather, one that is in some way either “dependent on,” or “rather profoundly affected by,” adding-and-removing.   Perhaps this is what makes the problem “difficult to describe.”

Is this problem, one of such a nature that you could describe “an optimal solution” without considering “(therefore...?) what happens next?”   If the answer to that question is, “no,” then ... aye, the problem is most difficult to describe.   In that case, the outcome of a particular solution is very heavily weighted by what its consequences will be, and that becomes an altogether different class of problem.

Sorry, but I simply do not see how you think anything in this post will help solve the problem.

To me every computer program is "dynamic". If it were static, there would be no need to write a program to solve it.

The problem is difficult to describe, because: it doesn't fit with commonly described patterns; has a couple of edge cases need to be handled; but most because it is difficult to express in words.

Having re-read your post 4 times to convince myself I wasn't missing anything, all I see is meaningless words.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.