Как распределить значение по ячейкам примерно равномерно?

Question

[dollar]

Есть массив чисел, его размер N.
Числа произвольные от 0 до 1.
Нужно разбить число X на N мелких чисел, и прибавить к каждому элементу массива так, чтобы каждый не превышал 1.

Сложность составляет именно последнее условие. Так-то можно было бы просто посчитать мелкое число как:
x = X / N
И дальше к каждому элементу массива прибавить по x.
Но что если хотя бы какой-то элемент будет 1 или близкий к 1? Тогда этот x (или ту часть, что высовывается за единицу) придётся снова бить между оставшимися. И получается как-то не понятно и не эффективно.

Comments

[Wataru]

Вам надо, чтобы итоговые числа в массиве были максимально равномерны, или чтобы положенные кусочки были максимально равномерны? И вообще, что значит равномерны? Можно минимизировать разность максимального и минимального. Или дисперсию. Или количество различных значений. Или черт его еще знает, что.

Формализуйте, пожалуйста, задачу.

[Wataru]

dollar, так, если в массиве уже 0.1 и 0.5, и число 0.2. то можно или везде по 0.1 прибавлять, или все в первую ячейку класть. Каждое решение где-то равномернее другого. Вам что надо-то. И вообще, лучше скажите, откуда у вас эта задача вылезла. Может вам вообще не надо вот это вот все делать и исходная задача решается проще и эффективнее не через такое деление.

Answer 1

[Сергей Соколов]

Для каждой ячейки известна её оставшаяся до потолка 1 «ёмкость».

Сложить ёмкости = capacity вместимость всего массива.
Если X > capacity — «невпихуемо!» — задача не имеет решения.

Коэффициент k = X / capacity меньше или равен 1.
Идти по ячейкам, откусывать от X в очередную кусочек, пропорционально ёмкости этой ячейки с коэфф. k.

Так в каждую доложат пропорционально её ёмкости, сглаживая неравномерность заполнения.

шесть строк на JS

const spread = (value, arr) => {
  const CELL_MAX = 1;
  const sum = arr.reduce((acc, c) => acc + c);
  const capacity = arr.length * CELL_MAX - sum;
  if (value > capacity) throw new Error("Value won't fit");
  const k = value / capacity;
  return arr.map(el => el + (CELL_MAX - el) * k);
}

spread(0.2, [ 0.1, 0.1 ]) // [ 0.2, 0.2 ]
spread(0.2, [ 0.1, 0.99 ]) // [ 0.29780219780219785, 0.9921978021978022 ]

Comments

[Rsa97]

Страдает равномерность распределения.
[0.2, 0.8], распределить 0.2
При равномерном получим [0.3, 0.9]
Вашим алгоритмом [0.36, 0.84]

[Сергей Соколов]

Rsa97, «равномерность распределения» не сформулирована.
С моим алгоритмом, по мере вливаний, все ячейки приходят к финишу в 1 одновременно (стремятся)

Answer 2

[Rsa97]

function distribute(arr, val) {
  let n = arr.length;
  let dVal = val;
  while (dVal > 0) {
    let d = dVal / n;
    dVal = 0;
    for (let i = 0; i < arr.length; i += 1) {
      if (arr[i] === 1) {
        continue;
      }
      arr[i] += d;
      if (arr[i] < 1) {
        continue;
      }
      dVal += arr[i] - 1;
      arr[i] = 1;
      n -= 1;
      if (n === 0) {
        return undefined;
      }
    }
  }
  return arr;
}

Comments

[Сергей Соколов]

Хорошо бы избавиться от цикла в цикле, а то это даёт квадратричную сложность O(n^2)
И обычно лучше не изменять переданные в функцию аргументы. Т.е. лучше вернуть копию массива arr, а не изменять его элементы.

[mayton2019]

Я вижу в этом задачу укладки множества рюкзаков.