Масштабировать вектор целых чисел

Question

Предположим, у меня есть вектор V целых положительных чисел.Если сумма целых чисел больше положительного целого числа N, я хочу изменить масштаб целых чисел в V так, чтобы сумма была <= N. Элементы в V должны оставаться выше нуля.Длина V гарантированно будет <= N. </p>

Есть ли алгоритм для выполнения этого масштабирования за линейное время?

Это не домашняя работа, кстати :).Мне нужно изменить масштаб карты с символов на частоты символов, чтобы использовать кодировку диапазона.

Некоторое быстрое мышление и поиск в Google не дали решения проблемы.

РЕДАКТИРОВАТЬ:

Хорошо, вопрос был несколько неясным.«Масштабировать» означает «нормализовать».То есть преобразуйте целые числа в V, например, умножив их на константу, на меньшие натуральные числа, чтобы критерий суммы (V) <= N был выполнен.Чем лучше сохраняются соотношения между целыми числами, тем лучше будет сжатие. </p>

Таким образом, проблема не ограничена, метод не должен находить оптимальный (например, в наименьших квадратах)в смысле смысла) способ сохранить соотношения, но "хороший".Установка целого вектора в 1, как предлагается, недопустима (если не принудительно).Достаточно «хорошим», например, будет нахождение наименьшего делителя (определенного ниже), который удовлетворяет критерию суммы.

Следующий наивный алгоритм не работает.

1. Найти текущую сумму (V), Зв
2. делитель: = int (ceil (Sv / N))
3. Разделите каждое целое число в V на делитель, округляя в меньшую сторону, но не ниже 1.

Сбой при v = [1,1,1,10] с N = 5.

divisor = ceil(13 / 5) = 3.
V := [1,1,1, max(1, floor(10/3)) = 3]
Sv is now 6 > 5.

В этом случае правильная нормализация равна [1,1,1,2]

Один алгоритм, который работал бы, - это выполнить бинарный поиск делителя (определенный выше), пока не будет найден самый маленький делитель в [1, N], удовлетворяющий критерию суммы.Начиная с предположения ceil (Sv / N).Это, однако, не линейно по количеству операций, а пропорционально len (V) * log (len (V)).

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

Answer 1

Просто разделите все целые числа на их Величайший общий делитель . Вы можете эффективно найти GCD с несколькими приложениями Алгоритма Евклида .

d = 0
for x in xs:
    d = gcd(d, x)

xs = [x/d for x in xs]

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

Answer 2

Как насчет этого:

1. Найти текущую сумму (V), Зв
2. делитель: = int (ceil (Зв / (N - | V | + 1))
3. Разделите каждое целое число в V на делитель, округлив

На v = [1,1,1,10] с N = 5:

делитель =ceil (13/2) = 7. V: = [1,1,1, ceil (10/7)) = 2]

Answer 3

Я думаю, что вы должны просто изменить масштаб части выше 1. Итак, вычтите 1 из всех значений и V.length из N. Затем измените масштаб, затем добавьте 1 обратно.Вы можете даже сделать немного лучше, если будете продолжать подводить итоги по ходу дела, вместо того, чтобы выбирать только один фактор, который обычно тратит некоторое «пространство чисел».Как то так:

public static void rescale(int[] data, int N) {
    int sum = 0;
    for (int d : data)
        sum += d;

    if (sum > N) {
        int n = N - data.length;
        sum -= data.length;

        for (int a = 0; a < data.length; a++) {
            int toScale = data[a] - 1;
            int scaled = Math.round(toScale * (float) n / sum);

            data[a] = scaled + 1;
            n -= scaled;
            sum -= toScale;
        }
    }
}

Answer 4

Это проблема «нормализации диапазона», но это очень просто. Предположим, что S - сумма элементов вектора и S> = N, тогда S = dN для некоторого d> = 1. Следовательно, d = S / N. Поэтому просто умножьте каждый элемент вектора на N / S (то есть разделите на d). В результате получается вектор с измененными компонентами, сумма которых равна N. Эта процедура явно линейна:)