[SciPy-Dev] splitting an ordered list as evenly as possilbe

[Bruce Southey]

  On 08/25/2010 09:44 AM, josef.pktd at gmail.com wrote:
> On Wed, Aug 25, 2010 at 10:32 AM, Keith Goodman<kwgoodman at gmail.com>  wrote:
>> On Wed, Aug 25, 2010 at 7:19 AM, John Hunter<jdh2358 at gmail.com>  wrote:
>>> On Wed, Aug 25, 2010 at 9:10 AM, Keith Goodman<kwgoodman at gmail.com>  wrote:
>>>
>>>> How about using the percentiles of np.unique(x)? That takes care of
>>>> the first constraint (no overlap) but ignores the second constraint
>>>> (min std of cluster size).
>>> Well, I need the 2nd constraint....
>> Both can't be hard constraints, so I guess the first step is to define
>> a utility function that quantifies the trade off between the two.
>> Would it make sense to then start from the percentile(unique(x), ...)
>> solution and come up with a heuristic that moves an item with lots of
>> repeats in a large length quintile to a short lenght quintile and then
>> accept the moves if it improves the utility? Or try moving each item
>> to each of the other 4 quintiles and do the move the improves the
>> utility the most. Then repeat until the utility doesn't improve. But I
>> guess I'm just stating the obvious and you are looking for something
>> less obvious and more clever.
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-dev
>>
> What I'm doing for some statistical analysis, e.g. chisquare test with
> integer data (discrete random variable)?
>
> np.bincount to get the full count, or use theoretical pdf,
> then loop over the integers (raw bins) and merge them to satisfy the
> constraints.
>
> constraints that I'm using are equal binsizes in one version and
> minimum binsizes in the second version.
>
> I haven't found anything else than the loop over the uniques, but I
> think there was some discussion on this some time ago on a mailing
> list.
>
> Josef
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
As others have indicated you have to work with the unique values as well 
as the frequencies.

Hopefully you can determine what I mean from the code below and modify 
it as needed. It is brute force but provides a couple of options as the 
following output indicates.

3 [(2, 44), (3, 35), (5, 42), (13, 43), (43, 38)]
4 [(2, 44), (3, 35), (5, 42), (14, 45), (43, 36)]
5 [(2, 44), (3, 35), (5, 42), (14, 45), (43, 36)]
6 [(2, 44), (3, 35), (5, 42), (15, 47), (43, 34)]
7 [(2, 44), (3, 35), (5, 42), (15, 47), (43, 34)]
8 [(2, 44), (3, 35), (5, 42), (16, 49), (43, 32)]
9 [(2, 44), (3, 35), (5, 42), (16, 49), (43, 32)]


Some notes:
1) For this example, you need an average of 41 per group (202 elements 
divided by 5). But that will be impossible because the value '1' has a  
frequency of 44, the sum of frequencies of '2' and '3' is 61. This means 
we need some way to allow slight increases in sizes - I use the variable 
eval which is the expected count plus some threshold (berror).

If you have floats then you can not use np.bincount directly. So if 
these are integers use them directly or use some function to create 
these in the desirable range (such as np.ceil or work with 10*x etc.)

Bruce

binx=np.bincount(x.astype(int))
for berror in range(10): # loop over a range of possible variations in 
the counts
     eval=berror+np.ceil(binx.sum()/5.0) # find a count threshold
     count=0
     quintile=[]
     for i in range(binx.shape[0]): #loop over the frequencies to 
determine which bin
         if count+binx[i] > (eval): # If the bin overflows then start a 
new one
             quintile.append((i, count))
             count=binx[i]
         else: #other keep adding into current bin
             count +=binx[i]
     quintile.append((i, count)) #add the last bin
     if len(quintile)==5: # we must have five bins otherwise that loop 
is useless. You can also apply other criteria here as well.
         print berror, quintile