Nice algorithm for 'spreading' indexes across an array?

[Max Williams]

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.
=> [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

 

[John W Higgins]

[Note: parts of this message were removed to make it a legal post.]

Morning Max,

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.
=> [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

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

 

[Jesús Gabriel y Galán]

Little ruby algorithm puzzle...

I have a situation where i have an array of 12 items. =A0If 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.
=3D> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

I would get results back like this

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

arr.spread(4)
=3D> [1, 5, 9, 12] =A0(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. =A0Anyone?

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 =3D []
each_slice(size / (how_many - 1)) { |a, *_| result << a}
result << self[-1]
result
end
end

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

Jesus.

 

[John W Higgins]

[Note: parts of this message were removed to make it a legal post.]

Morning Max,

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?

thanks
max

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.
http://gist.github.com/179241

John

 

[Dylan]

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.

=> [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

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

 

[Dylan]

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.

=> [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

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

 

[Ken Bloom]

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

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-self[i-1] if(i!=0 and self-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=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-self[i-1] if(i!=0 and self-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=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

 

[Harry Kakueki]

=> [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
--

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

 

[Max Williams]

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

 

[Brian Candler]

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.
=> [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)

 

[Harry Kakueki]

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

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

 

[Max Williams]

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

 

[Clifford Heath]

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 Heath.