Nice algorithm for 'spreading' indexes across an array?

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

···

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

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.

>> 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
--
Posted via http://ww <http://www.ruby-forum.com/&gt;RijndaelManaged&lt;http://www.ruby-forum.com/&gt;
w.ruby-forum.com/ <http://www.ruby-forum.com/&gt;\.

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

···

On Tue, Sep 1, 2009 at 9:41 AM, Max Williams <toastkid.williams@gmail.com>wrote:

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.

···

On Tue, Sep 1, 2009 at 6:41 PM, Max Williams<toastkid.williams@gmail.com> 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?

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 :slight_smile:

http://pastie.org/601932

-Dylan

···

On Sep 1, 9:41 am, Max Williams <toastkid.willi...@gmail.com> 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
--
Posted viahttp://www.ruby-forum.com/.

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

···

On Wed, Sep 2, 2009 at 1:41 AM, Max Williams<toastkid.williams@gmail.com> wrote:

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

--
A Look into Japanese Ruby List in English

Max Williams 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)

···

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

Max Williams 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&gt;

Clifford Heath.

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.

John

···

On Tue, Sep 1, 2009 at 10:11 AM, John W Higgins <wishdev@gmail.com> wrote:

Morning Max,

On Tue, Sep 1, 2009 at 9:41 AM, Max Williams <toastkid.williams@gmail.com > >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
> --
> Posted via http://ww <http://www.ruby-forum.com/&gt;RijndaelManaged&lt;
http://www.ruby-forum.com/&gt;
> w.ruby-forum.com/ <http://www.ruby-forum.com/&gt;\.
>
>
So here is my silly attempt - simple but probably not the best performing
answer you will get here.

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

http://pastie.org/602026

···

On Sep 1, 11:12 am, Dylan <mej...@gmail.com> wrote:

On Sep 1, 9:41 am, Max Williams <toastkid.willi...@gmail.com> 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
> --
> 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 :slight_smile:

http://pastie.org/601932

-Dylan

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 :slight_smile:

···

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

> 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
> --
> 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 :slight_smile:

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 :slight_smile:

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

···

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

On Sep 1, 11:12 am, Dylan <mej...@gmail.com> wrote:

On Sep 1, 9:41 am, Max Williams <toastkid.willi...@gmail.com> wrote:

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

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

···

On Wed, Sep 2, 2009 at 5:30 PM, Max Williams<toastkid.williams@gmail.com> wrote:

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 :slight_smile:

--
A Look into Japanese Ruby List in English

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

···

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