Negating a List Of Numbers

[Eduardo Bezerra]

Hi,

I'm looking for an efficient way to create the oposite of a
list of numbers.

For example, suppose I have this list of numbers:

100
200
300

I want to generate a list of all numbers between 1 and 999 that
exclude the numbers in this list.

Any suggestions are welcome.

Regards,
Eduardo

[velthuijsen]

Store the list of numbers in a vector, build a predicate function which
contains the list of numbers and returns true if something is compared
to one of these numbers, create an empty vector , then perform
remove_copy_if on the vector with the numbers with as target the empty
vector. Your (once) empty vector should now contain all the values not
on the list.

[Andrew Koenig]

"Eduardo Bezerra" <ed****@gmail.c om> wrote in message
news:58******** *************** ***@posting.goo gle.com...

I'm looking for an efficient way to create the oposite of a
list of numbers.

For example, suppose I have this list of numbers:

100
200
300

I want to generate a list of all numbers between 1 and 999 that
exclude the numbers in this list.

I think it's impossible to do this without executing a number of operations
proportional to the domain (here [1,999]). My reasoning is that if n is the
size of the domain and m is the number of elements in the list, merely
building the result must take at least n-m operations (because it has that
many elements) and checking the input must take m operations (because you
have to examine every element of the input at least once in order to know
what it is). So you must execute at least O(n) operations.

The question, then, is how close to O(n) you need to be. There is an easy
way to solve the problem in O(n+log(m)) operations: Sort the input, then
write a loop along the following lines:

vector<int>::co nst_iterator it = input.begin();

for (int i = 1; i <= 999; ++i) {
if (it != input.end() && i == *it)
++it;
else
output.push_bac k(i);
}

So my question is: Is this solution good enough? If not, what's not good
enough about it and what would you consider good enough?

[Xepo]

I think using sets would be the way to go about this. The best way to
go about it, as I see, is this:
------------------------------------
set<int> exclude, result;

//Fill the exclude set with the list of integers you want to exclude

for(int i=0; i<1000; i++)
if (!exclude.count (i))
result.insert(i );
------------------------------------

and then there's the insane way, that actually provides very close to
zero performance benefits (maybe even worse depending on your
compiler), but I feel like posting cause I think it's cool:
------------------------------------
/* You shouldn't *actually* use this code */
class int_it : public iterator<input_ iterator_tag, int> {
public:
int i;
int_it(int c):i(c) {};
inline void operator++() { i++; };
inline int operator*() { return i; };
inline bool operator!=(cons t int_it &second) { return second.i != i; };
};
int main()
{
set<int> exclude, result;
int_it start_i(1), end_i(1000);

//Fill the exclude set with the list of integers you want to exclude

set_difference( start_i, end_i, exclude.begin() , exclude.end(),
inserter<int>(r esult, result.begin()) );
}
------------------------------------

I think the first way is about as efficient as you can get, assuming
you don't know the list of excluded numbers beforehand.

If you do know the numbers beforehand and really care about the
slightest bit of efficiency (and I'm talking slight, assuming you're
not working with multi-megabyte sets), then you could use the programs
which generate a perfect hash function to generate a mathematical
formula to determine if a number should be included or not, but that's
really splitting hairs.

[Mark P]

Andrew Koenig wrote:

"Eduardo Bezerra" <ed****@gmail.c om> wrote in message
news:58******** *************** ***@posting.goo gle.com...

I'm looking for an efficient way to create the oposite of a
list of numbers.

For example, suppose I have this list of numbers:

100
200
300

I want to generate a list of all numbers between 1 and 999 that
exclude the numbers in this list.

I think it's impossible to do this without executing a number of operations
proportional to the domain (here [1,999]). My reasoning is that if n is the
size of the domain and m is the number of elements in the list, merely
building the result must take at least n-m operations (because it has that
many elements) and checking the input must take m operations (because you
have to examine every element of the input at least once in order to know
what it is). So you must execute at least O(n) operations.

The question, then, is how close to O(n) you need to be. There is an easy
way to solve the problem in O(n+log(m)) operations: Sort the input, then
write a loop along the following lines:

vector<int>::co nst_iterator it = input.begin();

for (int i = 1; i <= 999; ++i) {
if (it != input.end() && i == *it)
++it;
else
output.push_bac k(i);
}

So my question is: Is this solution good enough? If not, what's not good
enough about it and what would you consider good enough?

That works but O(n) is easily achievable too. Create a vector with 999
elements and mark each position corresponding to an input value. Then
iterate through the vector and write out the index of each unmarked
vector element.

Interestingly, this same idea (complemented) allows the list of input
values to be sorted in O(n) time. It's left as an exercise for the
reader to explain why this doesn't violate "convention al wisdom" about
the complexity of sorting.

-Mark

[CrayzeeWulf]

Andrew Koenig wrote:

So my question is: Is this solution good enough? If not, what's not good
enough about it and what would you consider good enough?

vector<int>::co nst_iterator it = input.begin() ;
int i = 1 ;
while( it != input.end() )
{
for(; ( i < *it ) && ( i <= 999 ); ++i )
{
output.push_bac k( i ) ;
}
++it ;
++i ;
}
for(; ( i <= 999 ); ++i )
{
output.push_bac k( i ) ;
}

Is that O(n) ?
--
CrayzeeWulf

[Mark P]

CrayzeeWulf wrote:

Andrew Koenig wrote:

So my question is: Is this solution good enough? If not, what's not good
enough about it and what would you consider good enough?

vector<int>::co nst_iterator it = input.begin() ;
int i = 1 ;
while( it != input.end() )
{
for(; ( i < *it ) && ( i <= 999 ); ++i )
{
output.push_bac k( i ) ;
}
++it ;
++i ;
}
for(; ( i <= 999 ); ++i )
{
output.push_bac k( i ) ;
}

Is that O(n) ?

Yes, but it doesn't work unless the input is sorted.

[Kannan Goundan]

Like Mark P said, you can take advantage of the fact that your range is
relatively small and that integers are indexable. If "m" is the size
of the original list of numbers, and "n" is the size of the output
range, you can do it in O(m+n) time and O(n) space.

// read in original list
bool[] exclude = new bool[100];
for (int i = 0; i < 1000; i++) exclude[i] = false;
while (more_numbers() ) {
exclude[read_number()] = true;
}

// create new list
for (int i = 0; i < 1000; i++) {
if (!exclude[i]) output.push_bac k(i)
}

It's basically the same algorithm, but now your "exclude" set is O(1)
for insert/lookup.

[Eduardo Bezerra]

"Andrew Koenig" <ar*@acm.org> wrote in message news:<jr******* **************@ bgtnsc05-news.ops.worldn et.att.net>...

"Eduardo Bezerra" <ed****@gmail.c om> wrote in message
news:58******** *************** ***@posting.goo gle.com...

I'm looking for an efficient way to create the oposite of a
list of numbers.

For example, suppose I have this list of numbers:

100
200
300

I want to generate a list of all numbers between 1 and 999 that
exclude the numbers in this list.

I think it's impossible to do this without executing a number of operations
proportional to the domain (here [1,999]). My reasoning is that if n is the
size of the domain and m is the number of elements in the list, merely
building the result must take at least n-m operations (because it has that
many elements) and checking the input must take m operations (because you
have to examine every element of the input at least once in order to know
what it is). So you must execute at least O(n) operations.

The question, then, is how close to O(n) you need to be. There is an easy
way to solve the problem in O(n+log(m)) operations: Sort the input, then
write a loop along the following lines:

vector<int>::co nst_iterator it = input.begin();

for (int i = 1; i <= 999; ++i) {
if (it != input.end() && i == *it)
++it;
else
output.push_bac k(i);
}

So my question is: Is this solution good enough? If not, what's not good
enough about it and what would you consider good enough?

Mr. Koening

Actually I oversimplified my question, so let me refine it. The list is not
a list of integers, in reallity it's a list of strings numbers with a maximun
lenght of 15 characters.

For example:

"526"
"5261"
"526212"
"52621"

I was thinking about a solution based on a tree where any string number
not matching one of the tree element would be out. But I'm having trouble
implementing it. To tell you the truth I'm a little lost in here.

Best regards,
Eduardo

[Mark P]

Eduardo Bezerra wrote:

Actually I oversimplified my question, so let me refine it. The list is not
a list of integers, in reallity it's a list of strings numbers with a maximun
lenght of 15 characters.

For example:

"526"
"5261"
"526212"
"52621"

So what are you trying to find? All strings of length <= 15 that aren't
in your list? That would be an enormous amount of data so I assume it's
something else. But what?