The next number that is not in an array

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

Tim C. wrote:

How is this done in ruby?
By writing a Ruby Q.? :slight_smile:

On Wed, Jul 16, 2008 at 5:01 PM, Tim C. [email protected]
wrote:

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 C. wrote:

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

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

Hi –

On Thu, 17 Jul 2008, Tim C. wrote:

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

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

On Thu, Jul 17, 2008 at 6:01 AM, Tim C. [email protected]
wrote:

How is this done in ruby?
Thanks in advance

Posted via http://www.ruby-forum.com/.

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

On Jul 16, 2008, at 9:38 PM, Harry K. wrote:

12,
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


A Look into Japanese Ruby List in English
http://www.kakueki.com/ruby/list.html

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 B. http://agileconsultingllc.com
[email protected]

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

Did you mean

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

of course you did.

On Thu, Jul 17, 2008 at 3:44 PM, Robert D. [email protected]
wrote:

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

Did you mean

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

of course you did.

Now to add injustice to injury :wink:

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


http://ruby-smalltalk.blogspot.com/


AALST (n.) One who changes his name to be further to the front
D.Adams; The Meaning of LIFF

2008/7/16 Tim C. [email protected]:

How is this done in ruby?

2008/7/17 Robert D. [email protected]:

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

Robert D. wrote:

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 D. wrote:

42 while restricted_numbers.include?( n+= 1 )
This will be about 10 times slower than David’s beautiful code.

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.

Hi –

On Thu, 17 Jul 2008, Robert D. wrote:

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

Did you mean

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

of course you did.

No, I believe I got it right the first time :slight_smile:

David

On Thu, Jul 17, 2008 at 9:05 PM, Michael W. Ryder
[email protected] wrote:

functional approach.
looping, etc.

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

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/

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

On Fri, Jul 18, 2008 at 3:20 AM, Erik V. [email protected]
wrote:

Two enhancements

  • “min” can be replaced by “first”, since a range is ordered.
    “first” is faster.
    This indeed is an excellent idea :slight_smile:

No, I believe I got it right the first time :slight_smile:

My fault David, I really thought that ?* was the only real “true” value
:open_mouth:

On Sat, 19 Jul 2008, Dave B. wrote:

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 :slight_smile:
And it comes across as awfully uncollegial.

David

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs