http://qs321.pair.com?node_id=388315

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

Looking for some perl magic.

Given an arbitrarily long list of numbers that SHOULD be consecutive, is there a simple method of finding any missing numbers?

For instance, given ( 41888, 41889, 41890, 41892, 41895 ), i'd like to determine that 41891, 41893 and 41894 are missing?

I've considered populating an array, indexed by my list, then looking for missing indexes, but I don't care for changing the start index of my arrays, and with the numbers I'm using, I'd have a LOT of empty indexes before I get to my first data.

I've also considered a simple loop that compares x to x+1, and steps x thru the list, but that seems kind of clunky to me.

I'm hoping for some perl elegance.

Morlane

Replies are listed 'Best First'.
Re: Finding missing numbers in a list
by BrowserUk (Pope) on Sep 03, 2004 at 16:52 UTC
    use List::Util qw[ reduce ]; my @in = ( 41888, 41889, 41890, 41892, 41895 ); my @missing; reduce{ push @missing, $a+1 .. $b-1; $b } @in; print @missing; 41891 41893 41894

    If your list is large, then this will be more (memory) efficient:

    my @in = ( 41888, 41889, 41890, 41892, 41895 ); my @missing; push @missing, $in[ $_ ] +1 .. $in[ $_+1 ] -1 for 0 .. $#in-1; print @missing; 41891 41893 41894

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

      Wow! Reduce with side effects, I've never seen that idiom. Smart.

        Well, I'd probably use my mapn utility func for this, but reduce is available pretty much everywhere and lent itself to avoiding the discussion about implementation details.


        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
        "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
Re: Finding missing numbers in a list
by ambrus (Abbot) on Sep 03, 2004 at 15:51 UTC

    You can do it with the .. operator:

    @a = (41888, 41889, 41890, 41892, 41895); @m = map $a[$_-1]+1..$a[$_]-1, 1..@a-1; print join(" ", @m), $/;

      It isn't the easiest to understand, but that's very nice outside the box thinking!

      Update: minor niggles: use $#a since that's what you mean — and please, please, use better variable names.

      my @list = ( 41888, 41889, 41890, 41892, 41895 ); my @missing = map { ( $list[ $_ - 1 ] + 1 ) .. ( $list[ $_ ] - 1 ) } 1 + .. $#list;

      Makeshifts last the longest.

Re: Finding missing numbers in a list
by Aristotle (Chancellor) on Sep 03, 2004 at 15:50 UTC

    I'll assume the list is sorted. If not, either sort it or use List::Util's min/max functions to set up the min( @list ) .. max( @list ) range.

    my @list = ( 41888, 41889, 41890, 41892, 41895 ); my @missing = do { my %missing; undef @missing{ $list[ 0 ] .. $list[ -1 ] }; delete @missing{ @list }; keys %missing; };

    That's the simplest way; it takes some memory and I'm not sure about its efficiency, so use with very large lists is not necessarily advised.

    Update: another option, assuming that the list really is sorted (can't rely on min/max here):

    my @missing; { my $i = 0; for ( $list[ 0 ] .. $list[ -1 ] ) { ++$i, next if $_ == $list[ $i ]; push @missing, $_; } }

    Update: and just because I had to, the same thing in functional lingo:

    my @missing = do { my $i = 0; grep { $_ == $list[ $i ] ? ++$i && 0 : 1 } $list[ 0 ] .. $list[ -1 + ]; };

    Makeshifts last the longest.

Re: Finding missing numbers in a list
by saintmike (Vicar) on Sep 03, 2004 at 17:55 UTC
    Set::IntSpan offers some nice features:
    use Set::IntSpan; my $set = Set::IntSpan->new("41888, 41889, 41890, 41892, 41895"); $set = $set->complement()->intersect( Set::IntSpan->new($set->min . "-" . $set->max)); print $set->run_list(), "\n";
    prints out
    41891,41893-41894
Re: Finding missing numbers in a list
by TrekNoid (Pilgrim) on Sep 03, 2004 at 16:16 UTC
    Here's my approach... assuming the list is always sorted:

    my @list = (41888, 41889, 41890, 41892, 41895); my $lo = $list[0]; my $hi = $list[$#list]; my $idx = 0; for ($cnt=$lo;$cnt<=$hi;$cnt++) { if ($cnt == $list[$idx]) { $idx++; } else { print "Missing: $cnt\n"; } }
    Trek
Re: Finding missing numbers in a list
by sleepingsquirrel (Hermit) on Sep 03, 2004 at 16:35 UTC
    Not exactly the model of efficiency...
    my @list = ( 41888, 41889, 41890, 41892, 41895 ); my @missing = grep { my $x=$_; not grep $x==$_, @list } $list[0]..$lis +t[$#list]; print "@missing\n";


    -- All code is 100% tested and functional unless otherwise noted.
Re: Finding missing numbers in a list
by ambrus (Abbot) on Jan 25, 2008 at 09:28 UTC