### Finding missing numbers in a list

by Morlane (Scribe)
 on Sep 03, 2004 at 15:43 UTC Need Help??

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 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.

(Twelve years later - directed here by a post on Stack Overflow.)

I'm not convinced that @list is much of an improvement over @a as a name for an array :-)

--

See the Copyright notice on my home node.

Re: Finding missing numbers in a list
by BrowserUk (Patriarch) 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 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

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://388315]
Front-paged by mifflin
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (1)
As of 2022-07-01 23:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?