0

Suppose I have a List. I'd like to be able to calculate semi-equi-distant max and min bounding points. I don't want to simply get the Max() and Min() its slightly more complicated.

To start, I'd like to specify a point in the list in which the list can be divided. To make it easy for now, suppose that point is 0. I'd then like to specify the number of divisions. Example:

List<int> Array = {-9,-8,-7,-2,-1,0,1,6,9,12};
int Divisions = 4;
int CutOff = 0;

So using these parameters I'd like to walk out to the extremes starting from 0 until there are 4 divisions. In this case the DivisionSize should be 6.

So the algorithm would start at 0 and walk to -6 for 1 Division then walk to -12 for the 2nd division. -12 would then become the bounding Min for the purposes of this algorithm.

The Max would then be calculated by starting at 0 and walking to 6, then 12. The bounding Max would then be 12. Its okay if the Calculate Max and Min are the actual Max and Min of the list, this is just an unlikely case.

I'm basically have some issues calculating the DivisionSize. I started with (Abs(Max)+Abs(Min))/Divisions but I can't seem to get the edge case where the Calculated size of the each division needs to be expanded to actually encompass the original Min and Max. Can somebody provided some guidance?

Edit: I don't necessarily want the BoundedMax and BoundedMin to be symmetrical about the cutoff. I want to add slack to either side of the cutoff until the BoundedMin and BoundedMax are >= and <= the range of the List.

3
  • 1
    Abs(Max)-Abs(Min) sounds very wrong. Do you mean Abs(Max - Min)?
    – leppie
    Jan 18, 2011 at 4:57
  • Supposed to be a +. Fixed thanks.
    – David
    Jan 18, 2011 at 5:06
  • It must be Abs(Max - Min). Consider Max = 102, Min = 98; division size would be 50 when in reality it should be 26. Jan 18, 2011 at 5:40

3 Answers 3

0

Since your divisions are going to be "semi-equidistant" from the cutoff, your algorithm should only focus on half the divisions (one side from the cutoff). The next step would be to determine which of the "sides" of the cutoff is larger.
Next, we divide the larger side by half the division, and get the Ceiling of the value (round to next higher integer). This will give us the size of each division of the larger side which would encompass all the values on both sides of the cutoff.
The following algorithm would give you the DivisionSize of 6 when applied to the example you provided:

int NewMax = Abs(Max - CutOff);
int NewMin = Abs(Min - CutOff);
int DivisionSize = (int)Math.Ceiling(NewMax > NewMin ? NewMax/(Divisions/2) : NewMin/(Divisions/2));
1
  • The division by 2 is unnecessary. I don't think I adequately articulated what I actually was trying to do.
    – David
    Jan 19, 2011 at 4:00
0
L = abs(min(A)-cut)
R = abs(max(A)-cut)
size = max(L,R) # ate least two divisions
while divisions >= (1+(L-1)/size + 1+(R-1)/size)
    size = size-1
size = size+1

Lets try it out:

L = 9
R = 12
size = 12
d = 1 + (9-1)/12 + 1 + (12-1)/12 = 1 + 1 = 2
size = 11
d = 1 + (9-1)/11 + 1 + (12-1)/11 = 1 + 2 = 3
size = 10
d = 1 + (9-1)/10 + 1 + (12-1)/10 = 1 + 2 = 3
size = 9
d = 1 + (9-1)/9 + 1 + (12-1) / 9 = 1 + 2 = 3
size = 8
d = 1 + (9-1)/8 + 1 + (12-1) / 8 = 2 + 2 = 4
size = 7 
d = 1 + (9-1)/7 + 1 + (12-1) / 7 = 2 + 2 = 4
size = 6
d = 1 + (9-1)/6 + 1 + (12-1) / 6 = 2 + 2 = 4
size = 5
d = 1 + (9-1)/5 + 1 + (12-1) / 5 = 2 + 3 = 5
--> size = 6

Note that the integer divisions must be floored (not rounded).

For optimization, you can use a binary search between 1 and R for the size.

0

I think the key is to determine how many of your divisions you want either side of the CutOff point, by taking the ratio of each side's length to the total length.

In your example, the sides are 9 and 12, giving (approx) 1.7 and 2.2 divisions either side. The actual numbers must be integers, so try (1,3) and (2,2). 1 division on the left means the size must be 9, 2 divisions on either side allow you to use division size 6.

Wrote some C# to illustrate this. Not particularly elegant, but it seems to work.

public class RangeDivider
{
    public int Min;
    public int CutOff;
    public int Max;
    public int NumDivisions;

    public RangeDivider(int min, int cutOff, int max, int numDivisions)
    {
        Min = min;
        CutOff = cutOff;
        Max = max;
        NumDivisions = numDivisions;
        System.Diagnostics.Debug.Assert(Min < CutOff && CutOff < Max && numDivisions >= 2);
    }

    public int LeftSize { get { return CutOff - Min; } }
    public int RightSize { get { return Max - CutOff; } }
    public int WholeSize { get { return Max - Min; } }

    private static int divCeil(int dividend, int divisor) { return 1 + (dividend - 1)/divisor; }

    private int ReturnSize(int leftDivisions)
    {
        int rightDivisions = NumDivisions - leftDivisions;
        if (leftDivisions > 0 && rightDivisions > 0)
        {
            return Math.Max(divCeil(LeftSize, leftDivisions), divCeil(RightSize, rightDivisions));
        }
        else
        {   //Must have at least 1 division each side of cutoff
            return int.MaxValue;
        }
    }

    public int GetSize()
    {
        var leftDivisions = NumDivisions * LeftSize / WholeSize;
        var size =  Math.Min(ReturnSize(leftDivisions), ReturnSize(leftDivisions + 1));
        Console.WriteLine("Min {0}, CutOff {1}, Max {2}, NumDivisions {3} gives a Division Size of {4}", Min, CutOff, Max, NumDivisions, size);
        return size;
    }

    public static int Get(int min, int cutOff, int max, int numDivisions) 
    { 
        return new RangeDivider(min, cutOff, max, numDivisions).GetSize(); 
    }

    public static void Test()
    {
        Get(-7,0,57,4);
        Get(-9, 0, 12, 4);
        Get(-1, 0, 7, 6);
    }

}
  • Min -7, CutOff 0, Max 57, NumDivisions 4 gives a Division Size of 19
  • Min -9, CutOff 0, Max 12, NumDivisions 4 gives a Division Size of 6
  • Min -1, CutOff 0, Max 7, NumDivisions 6 gives a Division Size of 2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.