The next number that is not in an array

[Tim Conner]

I want to increment the current value of a variable to the next number
that does not appear in an array of restricted numbers.
e.g.
restricted_numbers = [2,3,4,5,8,10,15,29]

if the variable is currently storing 11 then I want to increment it to
12,
however if the variable is currently storing 1 then I want to increment
it to 6.

How is this done in ruby?
Thanks in advance

 

[Joel VanderWerf]

I want to increment the current value of a variable to the next number
that does not appear in an array of restricted numbers.
e.g.
restricted_numbers = [2,3,4,5,8,10,15,29]

if the variable is currently storing 11 then I want to increment it to
12,
however if the variable is currently storing 1 then I want to increment
it to 6.

How is this done in ruby?

By writing a Ruby Quiz?

 

[Eric I.]

I want to increment the current value of a variable to the next number
that does not appear in an array of restricted numbers.
e.g.
restricted_numbers = [2,3,4,5,8,10,15,29]

if the variable is currently storing 11 then I want to increment it to
12,
however if the variable is currently storing 1 then I want to increment
it to 6.

How is this done in ruby?

How about:

begin
value += 1
end while restricted_numbers.member?(value)

Depending on the size of your list of restricted values, you may want
to use a Set rather than an Array, as it can test membership much more
efficiently.

Eric

====

LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE workshops.
Please visit http://LearnRuby.com for all the details.

 

[Jeff]

I want to increment the current value of a variable to the next number
that does not appear in an array of restricted numbers.
e.g.
restricted_numbers = [2,3,4,5,8,10,15,29]

if the variable is currently storing 11 then I want to increment it to
12,
however if the variable is currently storing 1 then I want to increment
it to 6.

How is this done in ruby?

How about this?

def find_next_slot(n)
n += 1 # start one higher
n += 1 until !restricted_numbers.include(n)
n # return the next empty slot
end

Jeff
softiesonrails.com
purpleworkshops.com

 

[Siep Korteling]

How about this?

def find_next_slot(n)
n += 1 # start one higher
n += 1 until !restricted_numbers.include(n)
n # return the next empty slot
end

Jeff
softiesonrails.com
purpleworkshops.com

Heh, I had

def permitted_next(n)
n += 1
n += 1 while @restricted_numbers.include?(n)
return n
end

find_next_slot is a way better method name.

Regards,

Siep

 

[David A. Black]

Hi --

I want to increment the current value of a variable to the next number
that does not appear in an array of restricted numbers.
e.g.
restricted_numbers = [2,3,4,5,8,10,15,29]

if the variable is currently storing 11 then I want to increment it to
12,
however if the variable is currently storing 1 then I want to increment
it to 6.

How is this done in ruby?

Here's a pretty terse way -- maybe too terse, and rather
side-effect-ish, but kind of interesting:

true while restricted_numbers.include?(n+=1)

This (and I think the other versions) keeps incrementing off the end
of the array, so you'd have to add something to make that not happen.


David

 

[Harry Kakueki]

I want to increment the current value of a variable to the next number
that does not appear in an array of restricted numbers.
e.g.
restricted_numbers = [2,3,4,5,8,10,15,29]

if the variable is currently storing 11 then I want to increment it to
12,
however if the variable is currently storing 1 then I want to increment
it to 6.

How is this done in ruby?
Thanks in advance

# If your range is not too big, you could try this.
# It is not so efficient, but....

ngnums = [2,3,4,5,8,10,15,29]
mynum = 1

p (0..100_000).select {|x| x > mynum and ngnums.include?(x) == false}[0]

Harry

 

[Rob Biedenharn]

I want to increment the current value of a variable to the next
number
that does not appear in an array of restricted numbers.
e.g.
restricted_numbers = [2,3,4,5,8,10,15,29]

if the variable is currently storing 11 then I want to increment it
to
12,
however if the variable is currently storing 1 then I want to
increment
it to 6.

How is this done in ruby?
Thanks in advance

# If your range is not too big, you could try this.
# It is not so efficient, but....

ngnums = [2,3,4,5,8,10,15,29]
mynum = 1

p (0..100_000).select {|x| x > mynum and ngnums.include?(x) == false}
[0]

Harry

Change that to:
p (0..100_000).detect {|x| x > mynum and ngnums.include?(x) == false}

and it doesn't have to go all the way to the end of the range. You
can use the alias find if that makes more sense than detect.

p (0..100_000).find {|x| x > mynum and ngnums.include?(x) == false}

-Rob

Rob Biedenharn http://agileconsultingllc.com
(e-mail address removed)

 

[Robert Dober]

true while restricted_numbers.include?(n+=1)
I think there is a typo in here

Did you mean

42 while restricted_numbers.include?( n+= 1 )

of course you did.

 

[Robert Dober]

I think there is a typo in here

Did you mean

42 while restricted_numbers.include?( n+= 1 )

of course you did.

Now to add injustice to injury

What about

n = ([*n.succ..rn.max.succ]-rn).min || n.succ

This will be about 10 times slower than David's beautiful code.
However in some extreme cases, e.g. very densely populated rn arrays
this functional approach becomes more interesting.

If rn is [*1..1_000] the functional code runs 50 times faster, and if
you have to jump over an restricted
numbers array of [*1..10_000] the functional code runs 500 times faster.

So maybe just in case you can afford the extra runtime for the
"normal" case you can assure nice performance in edge cases by the
functional approach.

Cheers
Robert

 

[Pit Capitain]

How is this done in ruby?

So maybe just in case you can afford the extra runtime for the
"normal" case you can assure nice performance in edge cases by the
functional approach.

Tim, I think Robert is right. Depending on the use case there might be
better ways to store the restricted numbers and to search for the next
unused one. For example it depends on how many restricted numbers
there are, how often and how you have to change the restricted
numbers, how often you need to fetch the next unused number and so on.
It's foremost a question of the appropriate algorithm and data
structure and only then how to do it in Ruby.

Regards,
Pit

 

[Michael W. Ryder]

I think there is a typo in here

Did you mean

42 while restricted_numbers.include?( n+= 1 )

of course you did.

Now to add injustice to injury

What about

n = ([*n.succ..rn.max.succ]-rn).min || n.succ

This will be about 10 times slower than David's beautiful code.
However in some extreme cases, e.g. very densely populated rn arrays
this functional approach becomes more interesting.

If rn is [*1..1_000] the functional code runs 50 times faster, and if
you have to jump over an restricted
numbers array of [*1..10_000] the functional code runs 500 times faster.

So maybe just in case you can afford the extra runtime for the
"normal" case you can assure nice performance in edge cases by the
functional approach.

Cheers
Robert

I just thought of an "optimization" that might work with dense arrays of
restricted numbers. Instead of storing just an array of restricted
numbers store the restricted number along with the final number in the
range, or the first non-restricted number. Then you would just have to
build the original array once and then read it to get the next available
number. Much less looping, etc.

 

[Robert Dober]

true while restricted_numbers.include?(n+=1)

I think there is a typo in here

Did you mean

42 while restricted_numbers.include?( n+= 1 )

of course you did.

Now to add injustice to injury

What about

n = ([*n.succ..rn.max.succ]-rn).min || n.succ

This will be about 10 times slower than David's beautiful code.
However in some extreme cases, e.g. very densely populated rn arrays
this functional approach becomes more interesting.

If rn is [*1..1_000] the functional code runs 50 times faster, and if
you have to jump over an restricted
numbers array of [*1..10_000] the functional code runs 500 times faster.

So maybe just in case you can afford the extra runtime for the
"normal" case you can assure nice performance in edge cases by the
functional approach.

Cheers
Robert

I just thought of an "optimization" that might work with dense arrays of
restricted numbers. Instead of storing just an array of restricted numbers
store the restricted number along with the final number in the range, or the
first non-restricted number. Then you would just have to build the original
array once and then read it to get the next available number. Much less
looping, etc.

After my benchmarks I suspect that Ruby does this for [*a..b] internally

 

[Michael W. Ryder]

true while restricted_numbers.include?(n+=1)
I think there is a typo in here

Did you mean

42 while restricted_numbers.include?( n+= 1 )

of course you did.


Now to add injustice to injury

What about

n = ([*n.succ..rn.max.succ]-rn).min || n.succ

This will be about 10 times slower than David's beautiful code.
However in some extreme cases, e.g. very densely populated rn arrays
this functional approach becomes more interesting.

If rn is [*1..1_000] the functional code runs 50 times faster, and if
you have to jump over an restricted
numbers array of [*1..10_000] the functional code runs 500 times faster.

So maybe just in case you can afford the extra runtime for the
"normal" case you can assure nice performance in edge cases by the
functional approach.

Cheers
Robert

I just thought of an "optimization" that might work with dense arrays of
restricted numbers. Instead of storing just an array of restricted numbers
store the restricted number along with the final number in the range, or the
first non-restricted number. Then you would just have to build the original
array once and then read it to get the next available number. Much less
looping, etc.

After my benchmarks I suspect that Ruby does this for [*a..b] internally

So, if I have an array [2,3,4,5,6,8,9,10,11,15,16,17] and entered '2' it
would know that 7 was the first number not in the array without looking
at 2, 3, 4, 5, and 6 first? Or maybe the time to loop through the
numbers was so small that it wasn't noticeable.

 

[David A. Black]

Hi --

I think there is a typo in here

Did you mean

42 while restricted_numbers.include?( n+= 1 )

of course you did.

No, I believe I got it right the first time


David

 

[Erik Veenstra]

n = ([*n.succ..rn.max.succ]-rn).min || n.succ

Two enhancements

* "min" can be replaced by "first", since a range is ordered.
"first" is faster.

* "max" returns nil in case of an empty array. Fall back to n.

Enhanced version:

n = ([*n.succ..(rn.max||n).succ]-rn).first || n.succ

gegroet,
Erik V. - http://www.erikveen.dds.nl/

 

[Robert Dober]

Two enhancements

* "min" can be replaced by "first", since a range is ordered.
"first" is faster.

This indeed is an excellent idea

 

[Dave Bass]

Some of these answers are ludicrously incomprehensible! For goodness'
sake, pity the poor b*gger who has to maintain your code. (It might even
be you.)

Eric has shown how to do it. Put the restricted numbers in a Set or
Hash. It's easy to test for membership as you increment through the
numbers.

Dave

 

[David A. Black]

Some of these answers are ludicrously incomprehensible! For goodness'
sake, pity the poor b*gger who has to maintain your code. (It might even
be you.)

Eric has shown how to do it. Put the restricted numbers in a Set or
Hash. It's easy to test for membership as you increment through the
numbers.

If someone else has already shown how to do it, and you have nothing
technical to say and nothing to add except some insults vaguely aimed
at the rest of us who have tried to help the OP, please either don't
write in or or try to add some value to what you write so that it
isn't just grandstanding about how much higher your standards of
simplicity and clarity are than ours. To start with, they're not
And it comes across as awfully uncollegial.


David

 

[Robert Dober]

No, I believe I got it right the first time

My fault David, I really thought that ?* was the only real "true" value :-O