Nice algorithm for 'spreading' indexes across an array?

cmaxvv · September 1, 2009, 6:41pm

Little ruby algorithm puzzle…

I have a situation where i have an array of 12 items. If someone
chooses to have n of them (where n can be between 3 and 12) then i want
to always include the first and last, and then ‘spread’ the others out
as evenly as possible between the rest.

So, lets say for the sake of argument that the array holds the numbers 1
to 12.

arr = (1…12).to_a
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

I would get results back like this

arr.spread(3)
=> [1,6,12] (or [1,7,12], either is fine)

arr.spread(4)
=> [1, 5, 9, 12] (or [1,4,8,12] or [1, 5, 8, 12])

It feels like there should be a simple solution for this but i can’t
think of a nice way. Anyone?

thanks
max

cmaxvv · September 1, 2009, 7:12pm

Morning Max,

On Tue, Sep 1, 2009 at 9:41 AM, Max W.
[email protected]wrote:

arr = (1…12).to_a
It feels like there should be a simple solution for this but i can’t
think of a nice way. Anyone?

thanks
max

Posted via http://ww http://www.ruby-forum.com/RijndaelManagedhttp://www.ruby-forum.com/
w.ruby-forum.com/ http://www.ruby-forum.com/.

So here is my silly attempt - simple but probably not the best
performing
answer you will get here.

class Array
def spread(members)
ret = Array.new
#We want sections that total 1 less then the number of members we
want
back - for example if we
#want 3 members in the spread we want 2 equal groups. We use .to_f
because we care about fractions here.
dist = count.to_f/(members-1)
#Now we simply run thru the array and take the members at each
spread
point.
(members-1).times{ |slot|
ret << at((slot*dist).ceil)
}
#Add the last member which is always the last member of the array
ret << at(-1)
end
end

cmaxvv · September 1, 2009, 7:44pm

On Tue, Sep 1, 2009 at 6:41 PM, Max
Williams[email protected] wrote:

arr = (1…12).to_a
It feels like there should be a simple solution for this but i can’t
think of a nice way. Anyone?

Here’s my try. It fails when the number you are asking for is more
than half the size, but anyway, it might give you an idea:

class Array
def spread how_many
result = []
each_slice(size / (how_many - 1)) { |a, *_| result << a}
result << self[-1]
result
end
end

irb(main):004:0> load ‘spread.rb’
=> true
irb(main):005:0> (1…12).to_a.spread 3
=> [1, 7, 12]
irb(main):006:0> (1…12).to_a.spread 4
=> [1, 5, 9, 12]
irb(main):007:0> (1…12).to_a.spread 12
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12]
irb(main):008:0> (1…12).to_a.spread 11
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12]
irb(main):019:0> (1…12).to_a.spread 8
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12]

Jesus.

cmaxvv · September 1, 2009, 7:45pm

On Tue, Sep 1, 2009 at 10:11 AM, John W Higgins [email protected]
wrote:

as evenly as possible between the rest.
=> [1,6,12] (or [1,7,12], either is fine)
Posted via http://ww http://www.ruby-forum.com/RijndaelManaged<
http://www.ruby-forum.com/>
w.ruby-forum.com/ http://www.ruby-forum.com/.

So here is my silly attempt - simple but probably not the best performing
answer you will get here.

small correction (should use floor instead of ceil)

class Array
def spread(members)
ret = Array.new
#We want sections that total 1 less then the number of members we
want
back - for example if we
#want 3 members in the spread we want 2 equal groups. We use .to_f
because we care about fractions here.
dist = count.to_f/(members-1)
#Now we simply run thru the array and take the members at each spread
point.
(members-1).times{ |slot|
ret << at((slot*dist).floor)
}
#Add the last member which is always the last member of the array
ret << at(-1)
end
end

Also, here is a gist which tends to read better.

gist.github.com

https://gist.github.com/wishdev/179241

Array.spread

class Array 
  def spread(members)
    ret = Array.new
    dist = count.to_f/(members-1)
    (members-1).times{ |pos|
      ret << at((pos*dist).floor)
    }
    ret << at(-1)
  end
end

John

cmaxvv · September 1, 2009, 9:00pm

On Sep 1, 11:12 am, Dylan [email protected] wrote:

=> [1,6,12] (or [1,7,12], either is fine)
Posted viahttp://www.ruby-forum.com/.

This should do what you’re looking for. It’s not always going to be
100% the most spread out possible, but it looks like you’re ok with
that

http://pastie.org/601932

-Dylan

Here’s an updated version that wont hang if you have more than one of
any number

http://pastie.org/602026

cmaxvv · September 1, 2009, 8:19pm

On Sep 1, 9:41 am, Max W. [email protected] wrote:

arr = (1…12).to_a

It feels like there should be a simple solution for this but i can’t
think of a nice way. Anyone?

thanks
max

Posted viahttp://www.ruby-forum.com/.

This should do what you’re looking for. It’s not always going to be
100% the most spread out possible, but it looks like you’re ok with
that

http://pastie.org/601932

-Dylan

cmaxvv · September 1, 2009, 11:09pm

On Wed, 02 Sep 2009 04:00:05 +0900, Dylan wrote:

others out as evenly as possible between the rest.
arr.spread(3)

Posted viahttp://www.ruby-forum.com/.

This should do what you’re looking for. It’s not always going to be
100% the most spread out possible, but it looks like you’re ok with
that

http://pastie.org/601932

I’m pasting in your code so in case pastie.org ever goes away, your code
will appear wherever the mailing list is mirrored.

class Array
def minDistance
minD=1.0/0
self.each_index{|i|
minD = self[i]-self[i-1] if(i!=0 and self[i]-self[i-1]<minD)
}
return minD
end

def spread(num)
return self if(num>=length)
outarr=[]
outarr[0]=self[0]
outarr[num-1]=self[-1]
minD=0.0
(1…100).each do
tempArr=[]
tempArr.replace(outarr)
tempArr.each_index{|i|
r = 0
r = Kernel.rand(length-1)+1 until(!tempArr.include? self[r])
tempArr[i]=self[r] if(i!=0 and i!=num-1)
}
tempArr.sort!
if(minD<tempArr.minDistance)
outarr.replace(tempArr)
minD=tempArr.minDistance
end
end
return outarr
end
end

Here’s an updated version that wont hang if you have more than one of
any number

http://pastie.org/602026

class Array
def minDistanceNotZero
minD=1.0/0
self.each_index{|i|
minD = self[i]-self[i-1] if(i!=0 and self[i]-self[i-1]<minD)
}
return minD if(minD!=0)
return 1
end

def spread(num)
return self if(num>=length)
outarr=[]
outarr[0]=self[0]
outarr[num-1]=self[-1]
minD=0.0
tempArr = []
(1…100).each do
tempArr.clear
tempArr[0]=self[0]
tempArr[num-1]=self[-1]
tempArr.each_index{|i|
r = 0
r = Kernel.rand(length-1)+1 until(tempArr.reject{|e| e!=self
[r]}.length<self.reject{|e| e!=self[r]}.length or i==0 or i==length-1)
tempArr[i]=self[r] if(i!=0 and i!=num-1)
}

  tempArr.sort!
  if(minD<tempArr.minDistanceNotZero)
    outarr.replace(tempArr)
    minD=tempArr.minDistanceNotZero
  end
end
return outarr

end
end

cmaxvv · September 2, 2009, 10:29am

Thanks, everyone. Harry, i like your solution but i thought of a way to
tweak it in a way which seems more readable, to me at least:

class Array
def spread(num)
discarded = []
(1…(size-num)).each{|u| discarded << self[size*u/(size-num+1)]}
self - discarded
end
end

The clever bit is of course line 4. I’m still trying to work out why
that works

cmaxvv · September 2, 2009, 5:06am

On Wed, Sep 2, 2009 at 1:41 AM, Max
Williams[email protected] wrote:

=> [1, 5, 9, 12] (or [1,4,8,12] or [1, 5, 8, 12])

It feels like there should be a simple solution for this but i can’t
think of a nice way. Anyone?

thanks
max

I haven’t tested enough to see if this always works.
But, take a look and make changes if necessary.

class Array
def spread(num)
res,de = [],[]
(1…(size-num)).each{|u| de << size*u/(size-num+1)}
(0…size).each{|y| res << self[y] if de.include?(y) == false}
res
end
end

arr = (1…12).to_a
(3…12).each{|t| p arr.spread(t)}

#output

#=> [1, 6, 12]
#=> [1, 4, 8, 12]
#=> [1, 3, 6, 9, 12]
#=> [1, 3, 5, 8, 10, 12]
#=> [1, 2, 4, 6, 8, 10, 12]
#=> [1, 2, 4, 6, 7, 9, 11, 12]
#=> [1, 2, 3, 5, 6, 8, 9, 11, 12]
#=> [1, 2, 3, 4, 6, 7, 8, 10, 11, 12]
#=> [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Harry

cmaxvv · September 2, 2009, 11:14am

Max W. wrote:

Little ruby algorithm puzzle…

I have a situation where i have an array of 12 items. If someone
chooses to have n of them (where n can be between 3 and 12) then i want
to always include the first and last, and then ‘spread’ the others out
as evenly as possible between the rest.

So, lets say for the sake of argument that the array holds the numbers 1
to 12.

arr = (1…12).to_a
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

I would get results back like this

arr.spread(3)
=> [1,6,12] (or [1,7,12], either is fine)

arr.spread(4)
=> [1, 5, 9, 12] (or [1,4,8,12] or [1, 5, 8, 12])

It feels like there should be a simple solution for this but i can’t
think of a nice way. Anyone?

I’d add 0.01 to give some margin for rounding errors

class Array
def spread(n)
interval = (size - 0.99) / (n - 1)
res = []
n.times do |i|
res << self[i * interval]
# or: res << self[i * interval + 0.5]
end
res
end
end

a = (1…12).to_a
puts a.spread(3)
puts a.spread(4)

cmaxvv · September 2, 2009, 11:27am

ah yes, in the case where you have repeated elements it goes wrong. In
this particular case the elements will always be unique (they will
always be numbers 1 to n in fact) but you’re right, your first method is
more general.

thanks again
max

cmaxvv · September 13, 2009, 4:55am

Max W. wrote:

It feels like there should be a simple solution for this but i can’t
think of a nice way. Anyone?

The algorithm you want is called Bresenham’s Line algorithm:
http://en.wikipedia.org/wiki/Bresenham’s_algorithm

Clifford H…

cmaxvv · September 2, 2009, 11:21am

On Wed, Sep 2, 2009 at 5:30 PM, Max
Williams[email protected] wrote:

The clever bit is of course line 4. I’m still trying to work out why
that works

That is not exactly the same thing.
But it depends on your specs.

class Array
def spread(num)
res,idue = [],[]
(1…(size-num)).each{|u| idue << size*u/(size-num+1)}
(0…size).each{|y| res << self[y] if idue.include?(y) == false}
res
end

def spread2(num)
discarded = []
(1…(size-num)).each{|u| discarded << self[size*u/(size-num+1)]}
self - discarded
end

end

arr = [1,2,3,4,5,6,7,8,9,9,10,11,12]
(3…13).each{|t| p arr.spread(t)}
puts
(3…13).each{|t| p arr.spread2(t)}

############output

#=> [1, 7, 12]
#=> [1, 5, 9, 12]
#=> [1, 4, 7, 9, 12]
#=> [1, 3, 6, 8, 10, 12]
#=> [1, 3, 5, 7, 9, 10, 12]
#=> [1, 2, 4, 6, 8, 9, 11, 12]
#=> [1, 2, 4, 5, 7, 9, 9, 11, 12]
#=> [1, 2, 3, 5, 6, 8, 9, 10, 11, 12]
#=> [1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12]
#=> [1, 2, 3, 4, 5, 6, 8, 9, 9, 10, 11, 12]
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 12]

#=> [1, 7, 12]
#=> [1, 5, 12]
#=> [1, 4, 7, 12]
#=> [1, 3, 6, 8, 10, 12]
#=> [1, 3, 5, 7, 10, 12]
#=> [1, 2, 4, 6, 8, 11, 12]
#=> [1, 2, 4, 5, 7, 9, 9, 11, 12]
#=> [1, 2, 3, 5, 6, 8, 10, 11, 12]
#=> [1, 2, 3, 4, 6, 7, 8, 10, 11, 12]
#=> [1, 2, 3, 4, 5, 6, 8, 9, 9, 10, 11, 12]
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 12]

Harry

Nice algorithm for 'spreading' indexes across an array?

thanks max

thanks max

others out as evenly as possible between the rest. arr.spread(3)

thanks max

I’d add 0.01 to give some margin for rounding errors

thanks
max

thanks
max

others out as evenly as possible between the rest.
arr.spread(3)

thanks
max