From: "Michael W. Ryder" <_mwryder@...>
Date: 2008-07-18T04:05:10+09:00
Subject: Re: The next number that is not in an array

Robert Dober wrote:
> On Thu, Jul 17, 2008 at 3:44 PM, Robert Dober <robert.dober@gmail.com> wrote:
>>>  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.