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

Has anyone encountered and/or developed a Perl-based solution to the following problem?

You have 2 or more lists, each holding 1 or more strictly increasing integers. None of the lists intersect with any of the others. There may be gaps between the last (highest) value of one list and the first (lowest) value of the next list (next in the sense of the lists being ordered by their lowest values). Example: 

(1..17);
(25..42);
(44..50);

[download]

Given two non-equal integers, m and n, generate a list of all integers between by concatenating (a) the already extant lists, or parts thereof; and (b) new lists to supply integers falling (i) below the first list, (ii) between any two extant lists, or (iii) above the last list.

With the lists above, and given: 

m = 12;
n = 62;

[download]

then the list (12 .. 62) would be built up from the following components: 

(12..17);   # sublist of the 1st list
(18..24);   # gap-filling list
(25..42);   # entirety of the 2nd list
(43);       # gap-filling list
(44..50);   # entirety of the 3rd list
(51..62);   # integers needed above highest list

[download]

I know I could figure this out if I had some spare cycles, but why re-invent the wheel? Thanks in advance.

Jim Keenan

Replies are listed 'Best First'.
Re: Gap-filling lists
by davidrw (Prior) on Mar 27, 2006 at 03:00 UTC
    you could use Set::Infinite or silimar that can do set logic ... pseduocode: 
    @lists =(  (12..17), (25..42), (44..50)  );
@gap_fillers = (m..n) - intersection( (m..n), @lists );

    [download]
    update can probably just do this: 
    $lists = Set::Infinite->new([12,17], [25,42], [44,50]);
print Set::Infinite->new([m,n])->minus($lists);

    [download]
[reply]
[d/l]
[select]
Re: Gap-filling lists
by BrowserUk (Patriarch) on Mar 27, 2006 at 03:26 UTC

    Assuming the input lists are already ordered I think this works. 

    #! perl -slw
use strict;
use List::Util qw[ min max ];
use Data::Dumper;

sub fillList {
    my( $m, $n, @lists ) = @_;
    my $lastE = $m-1;
    map {
        my( $s, $e ) = @{ $_ }[ 0, $#$_ ];
        (
            ( $lastE < $s ?  [ $lastE + 1 .. $s -1 ] : () ),
            [ max( $s, $lastE+1 ) .. min( $lastE = $e, $n ) ],
        );
    } @lists, [ $lastE, $n ];
}

my @in = ( [  1 .. 17 ], [ 25 .. 42 ], [ 44 .. 50 ], );

my @out = fillList 12, 62, @in;

print Dumper \@out;

__END__
C:\test>539350
$VAR1 = [
          [ 12, 13, 14, 15, 16, 17 ],
          [ 18, 19, 20, 21, 22, 23, 24 ],
          [ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39
+, 40, 41, 42 ],
          [ 43 ],
          [ 44, 45, 46, 47, 48, 49, 50 ],
          [ 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62 ]
        ];

    [download]
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
Re: Gap-filling lists
by gaal (Parson) on Mar 27, 2006 at 05:40 UTC
    This sounds very close, though not identical, to diets (discrete interval encoding trees).

    (There's a nice Haskell implementation available.)

[reply]

Back to Seekers of Perl Wisdom