LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 06-20-2006, 01:39 PM   #1
jonlake
Member
 
Registered: Apr 2004
Distribution: Slackware 11.0, Gentoo
Posts: 252

Rep: Reputation: 31
sequence of numbers, how to extract which numbers are missing


I have a sequence of numbers sorted in an array, but they are not necessarily contigous. (ex 1,2,4,7,8). How can I iterate through determine which numbers are missing? They should each count up by one.

I have done this as the following, but think there may be a better way to do it.
Started at the first value, if the next array value is 1 greater than the previous, then it is in sequence, then move to the next array element.

Thanks,

Jon
 
Old 06-20-2006, 01:56 PM   #2
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
You'd have to step through each element of the array once so you approach would appear to be alright. Was there something more specific that you were concerned about?
 
Old 06-20-2006, 06:29 PM   #3
demon_vox
Member
 
Registered: May 2006
Location: Argentina
Distribution: SuSE 10
Posts: 173

Rep: Reputation: 30
Hi,
I dont know what language you are using, so I will make my examples in Python
One idea is to generate another array with the complete sequence and then filter the ones that are in your array.
You would have:
Code:
numbers = [1,4,5,7,9]
maxNumber = max(numbers)
sequence = range(1, maxNumber + 1) # +1 because it stops one less

# this is a function that returns true if a value is not in your array of numbers
def notIncluded(x): return x not in numbers

dif = filter(notIncluded, sequence)

#here you have en dif the numbers that are missing
Another solution (far more declarative) is, again, to generate the whole sequence of numbers and then remove the ones you have:

Code:
numbers = [1,4,5,7,9]
maxNumber = max(numbers)
sequence = range(1, maxNumber + 1) # +1 because it stops one less

# This aplies the function sequence.remove to all the elements
# in numbers. Since sequence.remove takes one element from the
# sequence list, at the end you'll have in the sequence
# variable, a list with the missing numbers
map(sequence.remove, numbers)
The drawback from this solutions is that you have to generate an array with the whole sequence, which could take a lot of memory if your sequence is extremely long.
Plus, you could need to write some more depending on the language you are using (i.e. in C you would have to work some more for this solution since you dont any of this prebuilt functions).

But its another solution which might be useful (which I hope it is).

Greetings!
 
Old 06-20-2006, 07:39 PM   #4
xhi
Senior Member
 
Registered: Mar 2005
Location: USA::Pennsylvania
Distribution: Slackware
Posts: 1,065

Rep: Reputation: 45
Quote:
Originally Posted by jonlake
I have a sequence of numbers sorted in an array, but they are not necessarily contigous. (ex 1,2,4,7,8). How can I iterate through determine which numbers are missing? They should each count up by one.

I have done this as the following, but think there may be a better way to do it.
Started at the first value, if the next array value is 1 greater than the previous, then it is in sequence, then move to the next array element.

Thanks,

Jon
i dont see a problem with how you are doing it unless you also needed to keep track of which numbers were missing. then you would need 2 counters, one for the index position in the array and one for the ordered count.
 
Old 06-21-2006, 09:34 AM   #5
jonlake
Member
 
Registered: Apr 2004
Distribution: Slackware 11.0, Gentoo
Posts: 252

Original Poster
Rep: Reputation: 31
Thought I put in the language, but I am using perl. My sequence is about 6000 numbers long, so it can take some time.
 
Old 06-21-2006, 09:56 AM   #6
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
It shouldn't take very long you only need to step through the list once so the time required will be linear.
 
Old 06-21-2006, 10:51 AM   #7
demon_vox
Member
 
Registered: May 2006
Location: Argentina
Distribution: SuSE 10
Posts: 173

Rep: Reputation: 30
Hi,
6000 numbers doesnt seem too much for todays computers (mine took no time in solving it...) unless your max number is 10000000.
But since we are talking Perl, here is a Perl solution. First, since we are talking Perl, you array maybe shouldnt be an array. It should probably be a hash, with your numbers as key. I think this is better because Perl doesnt have a happy way to check if a number is in an array. So, apart from the solution, to change your array to a hash be could write:

Code:
my %hashNumbers = ();
map { $hashNumbers{$_} = 1 } @numbers;
and then we could solve the problem with:

Code:

map {
  push @result, $_ unless (defined($hashNumbers{$_}));
} (1..6000);
And as I am writting this I came with a cooler solution! (I just love Perl ). My new idea is to traverse the numbers array just once, and in each step we generate the missing secuence (with the .. operator). Something like this:

Code:
my @numbers = (1, 4, 5 ,7 ,9);

$lastNumber = 0;
@result = ();

for $currentNumber (@numbers) {
  $min = $lastNumber + 1;
  $max = $currentNumber - 1;
  push @result,  ($min .. $max);
  $lastNumber = $currentNumber;
}

print "$_\n" for (@result);
I like this solution because there is no searching and we just iterate once over the array.

Well I cant think of anything more right now (plus I should get to work jejejejje).

Hope this is useful!
Greetings!
 
Old 06-21-2006, 04:35 PM   #8
jonlake
Member
 
Registered: Apr 2004
Distribution: Slackware 11.0, Gentoo
Posts: 252

Original Poster
Rep: Reputation: 31
Thank you so much for your replies. demon_vox I was able to use some of the code you gave me to improve my scripts. I hadn't used map or push before (briefly heard of them) but have found ways to improve my scripts with them.

Thanks,

Jon
 
Old 06-22-2006, 01:32 AM   #9
ppanyam
Member
 
Registered: Oct 2004
Location: India
Distribution: Redhat
Posts: 88

Rep: Reputation: 15
Similar to demon_vox's code, but more like a C-programmer!!!

Code:
#!/usr/bin/perl5 -w
my @numbers = (1, 4, 5 ,7 ,9);

@result = ();

for ($i=0;$i<$#numbers;$i++) {
  if ( $numbers[$i+1] - $numbers[$i] > 1)  {
     push @result,  ($numbers[$i]+1 .. $numbers[$i+1]-1);
    } 
}
print "$_\n" for (@result);
 
Old 06-22-2006, 04:14 AM   #10
elluva
Member
 
Registered: Aug 2003
Location: Belguim, Ostend and Ghent
Distribution: Ubuntu
Posts: 600

Rep: Reputation: 30
hmm, you could use a search like algorithm to check where you have an error. Since all your numbers add one up, you know what number that should be in the middle. So you read the number in the middle, if it is what you expected this means the first half of the list is ok. If it isn't, this means you have a problem in the first half of the list. You just repeat this for the first have of the list, until you find the index where the problem resides. You solve the problem and start all over again.

Searching a list this way is O(log n) in time, so as long as there aren't to many issues it should give you a speedup. Of course if you have to solve your problem by inserting stuff, this will get slow because the whole tail of the list will have to be copied everytime! This was probably your problem in the first place.
 
Old 06-22-2006, 05:25 AM   #11
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
Quote:
Originally Posted by elluva
Searching a list this way is O(log n) in time
But if every element is in error ie [1,3,5,7,9] Then it is O(n), but using your idea you could start from the end of the list and then mimic a binary search. The best case would therefore be O(2), a list with one error would be O(log n) a list with m errors would be O(min(mlog n, n)) and so a list with n errors would be O(n).

Last edited by graemef; 06-22-2006 at 05:26 AM.
 
Old 06-22-2006, 07:09 AM   #12
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,314

Rep: Reputation: 175Reputation: 175
my go!
Code:
#!/usr/bin/perl -ws



# make random list
@list = sort{$a<=>$b}  map {int rand(30) + 1} (1..15);

# your list goes here
# ===================
%hash = map {$_, $_} @list; # make a hash of it!!!
@missing = grep { !defined($hash{$_}) && $_ } (1..$list[-1]);

print "@list\n";
print "missing = @missing\n";
 
Old 06-23-2006, 01:33 AM   #13
ppanyam
Member
 
Registered: Oct 2004
Location: India
Distribution: Redhat
Posts: 88

Rep: Reputation: 15
Wow!

Quote:
%hash = map {$_, $_} @list; # make a hash of it!!!
@missing = grep { !defined($hash{$_}) && $_ } (1..$list[-1]);
Can you anglicize your perl code plz. I dont seem to understand anything which isnt procedural(& OO).

ppanyam
 
Old 06-26-2006, 04:28 AM   #14
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,314

Rep: Reputation: 175Reputation: 175
I will try!
Code:
%hash = map {$_, $_} @list; # make a hash of it!!!
this is making a hash of the list by doubling up the members.
like $hash{1} = 1;
map returns what is in the {} block for each member of the list,
in this case just ($_, $_ } (could have been any value)


i.e. simply: (1,2,3) becomes (1,1,2,2,3,3)
so assign this to a hash. like {1=>1, 2=>2, 3=>3 } etc.

Code:
@missing = grep { !defined($hash{$_}) && $_ } (1..$list[-1]);
as you said the list is sorted, (i assumed ascending) then the last element $list[-1]
must be the highest number. So (1..$list[-1]) is the list of integers between the two.

grep finds in a list (1..max), items ($_) that satisfy the block expression.
so we find items that are NOT defined in the previous hash and return the value.
( just using !defined($hash{$_}) would return 1 each time, we need to return the value
hence && $_)

I hope that helps.

map applies function to each member of a list
grep simply is used for filtering out members of a list
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
how to get numbers of cpus hongxing Linux - Software 3 11-14-2005 08:23 AM
Even numbers paraiso Linux - Newbie 4 05-15-2005 04:31 PM
what do the numbers mean? drisay Slackware 1 12-14-2004 08:30 AM
Adding numbers, break on non-numbers... Cruger Programming 1 03-22-2004 10:18 AM
Help.. how do I add two numbers? Tengil Linux - Newbie 3 03-04-2004 01:58 PM


All times are GMT -5. The time now is 08:42 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration