From: Ken Bloom <kbloom@...>
Date: 2009-09-02T06:08:32+09:00
Subject: Re: Nice algorithm for 'spreading' indexes across an array?

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




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