in reply to Re: Split range 0 to M into N non-overlapping (roughly equal) ranges.

in thread Split range 0 to M into N non-overlapping (roughly equal) ranges.

FYI, there are occasional one-off rounding error issues with this algorithm (possibly platform dependent), 2.5% of the time partitioning ranges of 1..100 or less. Depending on your goals that may or may not matter, but here are some examples :

$M,$N final array element (should be $M) (14,11) ==> final=13 (14,13) ==> final=13 (29,11) ==> final=28 (29,13) ==> final=28 (29,22) ==> final=28 (29,26) ==> final=28 (59,11) ==> final=58 (59,13) ==> final=58 (59,22) ==> final=58 (59,26) ==> final=58 (59,44) ==> final=58 (59,52) ==> final=58 (59,55) ==> final=58 (100,49) ==> final=99 (100,98) ==> final=99 (100,99) ==> final=99

Test script

use strict; use warnings; #======================================== # Algorithms #======================================== sub ranges_javafan { my ($M, $N) = @_; return [ map {[int($_*($M+1)/$N) , int(($_+1)*(($M+1)/$N))-1] } 0..$N - 1]; } #---------------------------------------- sub ranges_javafan_buk { my ($M, $N) = @_; my $STEP = ( $M + 1 ) / $N; return [ map [int( $_ * $STEP ), int( ( $_+1 ) * $STEP ) -1] , 0 .. $N - 1]; } #---------------------------------------- sub ranges_elisheva_ikegami { my ($M, $N) = @_; my $r = ($M+1)%$N; my $q = ($M+1-$r)/$N; my $iEnd=0; return [ map { my $iStart=$iEnd; [$iStart, ($iEnd+=$_) - 1] } (($q+1) x $r, ($q) x ($N-$r)) ]; } #======================================== # Check of final element of range #======================================== sub roundCheck { my ($cr, $M) = @_; my $iTotal=0; my $iErrors=0; for my $m (1..$M) { for my $n (1..$m) { $iTotal++; my $aRanges = $cr->($m, $n); my $iFinal = $aRanges->[-1][1]; if ($iFinal != $m) { $iErrors++; # Uncomment here to see individual errors # --------------------------------------- # print "($m,$n) ==> final=$iFinal\n"; } } } printf "Error rate: %s\n", ($iErrors*100/$iTotal); } #------------------------------------------------------- print "Javafan:\n"; roundCheck(\&ranges_javafan, 100); print "Javafan_buk:\n"; roundCheck(\&ranges_javafan_buk, 100); print "elisheva_ikegami\n"; roundCheck(\&ranges_elisheva_ikegami, 100); #outputs (Debian Linux - Lenny, perl 5.10.0, 32-bit) Javafan: Error rate: 2.47524752475248 Javafan_buk: Error rate: 2.47524752475248 elisheva_ikegami Error rate: 0

**Update** added test script and added parenthetical remark about platform dependency.

In Section
Seekers of Perl Wisdom

Comment onRe^2: Split range 0 to M into N non-overlapping (roughly equal) ranges.SelectorDownloadCode