C #: Ограничивающий Макс и Мин на массиве []

Question

Предположим, у меня есть список. Я хотел бы иметь возможность рассчитать полуэквивалентные максимальные и минимальные ограничивающие точки. Я не хочу просто получить Max () и Min (), это немного сложнее.

Для начала я бы хотел указать в списке точку, на которую можно разделить список. Для упрощения предположим, что точка равна 0. Затем я хотел бы указать количество делений. Пример:

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

Таким образом, используя эти параметры, я бы хотел выйти на крайние значения, начиная с 0 до 4 делений. В этом случае DivisionSize должен быть 6.

Таким образом, алгоритм будет начинаться с 0 и идти к -6 для 1-го деления, а затем к -12 для 2-го деления. -12 станет ограничивающим минимумом для целей этого алгоритма.

Макс тогда будет рассчитываться, начиная с 0 и переходя к 6, затем 12. Ограничивающий Макс будет тогда 12. Это нормально, если Рассчитать Макс и Мин это фактические Макс и Мин в списке, это просто маловероятный случай.

У меня, в основном, есть некоторые проблемы с вычислением DivisionSize. Я начал с (Abs (Max) + Abs (Min)) / Divisions, но я не могу понять тот крайний случай, когда Расчетный размер каждого подразделения должен быть расширен, чтобы фактически охватить исходные Min и Max. Может ли кто-нибудь дать какое-нибудь руководство?

Edit: я не обязательно хочу, чтобы BoundedMax и BoundedMin были симметричны относительно среза. Я хочу добавить слабину по обе стороны от обрезания до тех пор, пока BoundedMin и BoundedMax не будут> = и <= диапазон списка. </p>

Answer 1

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

Давайте попробуем:

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

Обратите внимание, что целочисленные деления должны быть разбиты (не округлены)

Для оптимизации вы можете использовать двоичный поиск для размера от 1 до R.

Answer 2

Я думаю, что ключ в том, чтобы определить, сколько ваших делений вы хотите получить по обе стороны от точки CutOff, взяв отношение длины каждой стороны к общей длине.

В вашем примере, стороны равны 9 и 12, давая (приблизительно) 1,7 и 2,2 деления с каждой стороны. Фактические числа должны быть целыми числами, поэтому попробуйте (1,3) и (2,2). 1 деление слева означает, что размер должен быть 9, 2 деления с каждой стороны позволяют использовать размер деления 6.

Написал немного C #, чтобы проиллюстрировать это. Не особенно элегантно, но, похоже, работает.

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);
    }

}

• Мин -7, CutOff 0, Макс. 57, NumDivisions 4 дает размер деления 19
• Min-9, CutOff 0, Max 12, NumDivisions 4 дает размер деления 6
• мин -1, CutOff 0, макс. 7, NumDivisions 6 дает размер деления 2

Answer 3

Поскольку ваши деления будут "полуэквидистантными" от отсечки, ваш алгоритм должен фокусироваться только на половине делений (одна сторона от отсечки). Следующим шагом будет определение того, какая из «сторон» среза больше.
Затем мы делим большую сторону на половину деления и получаем потолок значения (округление до следующего более высокого целого числа). Это даст нам размер каждого деления большей стороны, который будет охватывать все значения с обеих сторон среза.
Следующий алгоритм даст вам DivisionSize 6 применительно к предоставленному вами примеру:

int NewMax = Abs(Max - CutOff);
int NewMin = Abs(Min - CutOff);
int DivisionSize = (int)Math.Ceiling(NewMax > NewMin ? NewMax/(Divisions/2) : NewMin/(Divisions/2));