Случайные числа с заданной сумой, какой алгоритм?

Question

[TonyStark1337]

Привет, какой алгоритм уже есть или как сделать свой если надо найти 4 рандомных числа сума которых ровна N, допустим x+y+z+m = 100, где каждая больше другой, то есть x > y > z > m. У кого какие мысли ?

Comments

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

Числа натуральные? Или отрицательные целые тоже ок. Или дробные тоже годятся?

[TonyStark1337]

Сергей Соколов, натуралиные

Answer 1

[Rsa97]

x = rand(1, 97);
y = rand(1, 98-x);
z = rand(1, 99-x-y);
result = sort([x, y, z, 100-x-y-z]);

Comments

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

не исключено равенство двух или более значений. В условии — неравенство.
1+1+1+97 — плохой вариант, как я понимаю.

[Rsa97]

Сергей Соколов, Тут общий принцип. Можно генерировать числа в цикле, проверяя на повторения.

Answer 2

[Александр]

Вариант 4 - Окончательный.
Возвращает массив уникальных чисел больше нуля отсортированных по убыванию. Имеется проверка на возможность разделения числа на более мелкие.

const sum = array => array.reduce((accumulator, value) => (accumulator += value), 0);

const breakUp = (number, count) => {
  const minimal = (count * (count + 1)) / 2;
  if (minimal > number) {
    throw new Error(`Число ${number} слишком маленькое. Минимальное допустимое число ${minimal}.`);
  }
  const numbers = Array.from({ length: count }, (_, index) => (count - index));

  numbers.forEach((value, index, array) => {
    const total = sum(array);
    const remainder = number - total;
    if (total < number) {
      const random = (index === count - 1)
        ? remainder + value
        : Math.floor(Math.random() * remainder);

      array[index] = random;
    }
  });

  const isUnique = new Set(numbers).size === numbers.length;

  if (!isUnique) {
    return breakUp(number, count);
  } else {
    return numbers.sort((a, b) => (b - a));
  }
};

Другие варианты

Вариант 1.

const breakUp = (number, count) => {
  const numbers = [];

  for (let index = 0; index < count; index++) {
    const random = index === count - 1
      ? number
      : Math.round(Math.random() * number);
    
    numbers.push(random);
    number -= random;
  }

  numbers.sort((a, b) => b - a);

  return numbers;
};

const numbers = breakUp(100, 4);
console.log(numbers); // [76, 15, 6, 3]

Вариант 2.

const breakUp = (number, count) => Array.from({ length: count }, (_, index) => {
  const random = index === count - 1
    ? number
    : Math.round(Math.random() * number);

  number -= random;

  return random;
}).sort((a, b) => b - a);

Вариант 3.

const breakUp = (number, count) => {
  const numbers = new Set();

  while (numbers.size < count) {
    const previousSize = numbers.size;
    const random = numbers.size === count - 1
      ? number
      : Math.floor(Math.random() * number);
    
    numbers.add(random);

    if (previousSize < numbers.size) {
      number -= random;
    }
  }

  return [...numbers.values()].sort((a, b) => b - a);
};

Comments

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

во 2-м варианте 4-е число может оказаться нулём, и вариант [97,1,1,1] тоже вероятен.

[Александр]

Сергей Соколов, Да и в первом тогда тоже, код самих чисел то никак не поменялся.

[Александр]

Сергей Соколов, Переписал алгоритм.

Answer 3

[mayton2019]

Сортировка не нужна вобщем-то.

Геометрически, задача сводится к генерации 3х случайных точек на отрезке длиной в 100.

Comments

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

где расстояния между ними не должны повториться.

[Роман]

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

[mayton2019]

Есть условие старшинства отрезков. И думая о нем , мне почему-то вспоминается золотое сечение, Парадокс Зенона, числа Фибоначчи и прочее.

Кстати. Условие случайности - слабое и неполноценное без требований получить определенную форму гистограммы. Ведь можно пойти на хитрость и генерировать золотое сечение с рандомным хвостиком.

[Karpion]

Роман, В условии задачи:

x > y > z > m

[Роман]

Karpion, сори, проглядел)))

Answer 4

[Karpion]

Проблема в том, что сделать у всех трёх чисел равномерное распределение - не получится. Вы бы написали, зачем это нужно.

Мне кажется, надо кинуть на отрезок длины 100 три точки, чтобы разделить его на четыре части. Полученные три числа - отсортировать.

Проблема: числа могут получиться одинаковыми.
Решение: Кидаем три точки на отрезок длиной 94=100-1-2-3. Сортируем отрезки. Потом к первому прибавляем 3, ко второму прибавляем 2, к третьему прибавляем 1 - это если нужны целые числа.

Answer 5

[xmoonlight]

Добавлю экзотическое заполнение.
Можно генерить любые числа рандомно (r) от 0 до 1 и поочерёдно заполнять переменные.
По шагам (на каждой строке r - генерируется только один раз):

1. (x+y+z+m+r<100)?(x+=r):break
2. (y+r<x&&x+y+z+m+r<=100)?y+=r:goto 1
3. (z+r<y&&x+y+z+m+r<=100)?z+=r:goto 1
4. (m+r<z&&x+y+z+m+r<=100)?m+=r:goto 1
5. goto 1

PS: Если избавиться от однотипных переменных в пользу массива, то получим сразу два бонуса:
1. Можно использовать простую рекурсию.
2. Набор количества значений в сумме - полностью произвольно-задаваемый.

Comments

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

кстати забавный алгоритм! Из какой книжки?

[xmoonlight]

Сергей Соколов, ты не поверишь: из своей башки сгенерил...
и как раз ждал реакции от тебя: насколько это тупая идея или имеет право на жизнь)

Answer 6

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

Чтобы соблюсти условие строго-больше, можно записать все слагаемые через их ненулевые разницы.
x > y, значит, x = y + ненулевое_число. Можно так перезаписать слагаемые:

m          = k0 
z = m + k1 = k0 + k1
y = z + k2 = k0 + k1 + k2
x = y + k3 = k0 + k1 + k2 + k3
-----------------------------
m+z+y+x    = 4k0 + 3k1 + 2k2 + k3 = SUM

k_i — это натуральные числа от 1.
Получили все k — вычислили x, y, z, m.

Сначала получим k0
Т.к. на k1..k3 уходит минимум 6, когда все по 1,
для k0 остаётся диапазон [1, (SUM - 6) / 4]
при этом k0 должен быть целым.

Выбрав случайный k0 в этом диапазоне,
получаем новую целевую сумму SUM1 = SUM - 4 * k0,
которую нужно заполнить 3k1 + 2k2 + k3 = SUM1

Рекурсия. Но на последнем шаге k3 это весь остаток.

const addUpTo = (top, n) => {
  const getDiffs = (sum, n, acc = []) => {
    if (n === 1) {
      x = sum;
    } else {
      const headroom = (n - 1) * n / 2;
      const cap = Math.floor((sum - headroom) / n);
      if (cap < 1) throw("Impossible. " + JSON.stringify(acc));
      x = 1 + Math.floor(Math.random() * cap);
    }

    acc.push(x);

    if (n <= 1) {
      return acc;
    } else {
      return getDiffs(sum - x * n, n - 1, acc);
    }
  }

  return getDiffs(top, n).map((_, i, a) => a.reduce((acc, c, j) => j <= i ? acc + c : acc)).reverse();
}

addUpTo(100, 4)  /*
[ 34, 30, 21, 15 ]
[ 31, 24, 23, 22 ]
[ 66, 17, 13, 4 ]
[ 47, 22, 21, 10 ]
...
*/

addUpTo(10, 4)  // [ 4, 3, 2, 1 ]
addUpTo(9, 4)   // ошибка, невозможно разложить