Алгоритм вычисления количества комбинаций для формирования 100

Ответ 1

Я надеюсь, что это не проблема домашней работы!

    def combinations(n: Int, step: Int, distance: Int, sum: Int = 100): List[List[Int]] =
      if (n == 1) 
        List(List(sum))
      else 
        for {
          first <- (step until sum by step).toList
          rest <- combinations(n - 1, step, distance, sum - first)
          if rest forall (x => (first - x).abs <= distance)
        } yield first :: rest

Ответ 2

Если вам нужно разделить 100 на 2 с максимальным расстоянием N, самое низкое значение в комбинации

100/2 - N/2

Если вам нужно разделить 100 на 3 значения с максимальным расстоянием N, это становится более сложным. Среднее значение 3 будет равно 100/3, но если один из них намного ниже этого среднего, то другой может быть только немного больше этого среднего значения, что означает, что минимальное значение не является средним минусом максимального расстояния, разделенного на два, но, вероятно,

100/3 - 2N/3

В общем случае с значениями M это становится

100/M - (M-1) N/M

Что можно упростить до

(100 - (M-1) N)/M

Аналогично мы можем рассчитать максимально возможное значение:

(100 + (M-1) N)/M

Это дает вам диапазон для первого значения вашей комбинации.

Чтобы определить диапазон для второго значения, вы должны учитывать следующие ограничения:

• расстояние с первым значением (не должно превышать максимальное расстояние)
• мы можем достичь суммы (100)

Первое ограничение не является проблемой. Второй.

Предположим, что мы разделим 100 на 3 с максимальным расстоянием 30, используя кратные 10 Как было рассчитано ранее, минимальное значение:

(100 - (3-1) 30)/3 → 13 → округляется до следующего кратного 10 → 20

Максимальное значение

(100 + (3-1) 30)/3 → 53 → округленный до предыдущего кратного 10 → 50

Итак, для первого значения мы должны перебрать более 20, 30, 40 и 50.

Предположим, что мы выберем 20. Это оставляет 80 для других 2 значений. Опять же, мы можем распределить 80 из двух значений с максимальным расстоянием 30, что дает:

Минимум: (80 - (2-1) 30)/2 → 25 → закругленный → 30

Максимум: (80 + (2-1) 30)/2 → 55 → закругленный → 50

Второе ограничение состоит в том, что мы не хотим, чтобы расстояние больше 30 по сравнению с нашим первым значением. Это дает минимум -10 и максимум 50.

Теперь возьмите пересечение между двумя доменами → от 30 до 50, а для второго значения - итерации более 30, 40, 50.

Затем повторите это для следующего значения.

EDIT: Я добавил алгоритм в псевдокод, чтобы сделать его более ясным:

calculateRange (vector, remainingsum, nofremainingvalues, multiple, maxdistance)
{
if (remaingsum==0)
   {
   // at this moment the nofremainingvalues should be zero as well
   // found a solution
   print vector
   return;
   }

minvalueaccordingdistribution = (remainingsum-(nofremainingvalues-1)*maxdistance)/nofremaingvalues;
maxvalueaccordingdistribution = (remainingsum+(nofremainingvalues-1)*maxdistance)/nofremaingvalues;

minvalueaccordingdistance = max(values in vector) - maxdistance;
maxvalueaccordingdistance = min(values in vector) + maxdistance;

minvalue = min (minvalueaccordingdistribution, minvalueaccordingdistance);
maxvalue = max (minvalueaccordingdistribution, minvalueaccordingdistance);

for (value=minvalue;value<=maxvalue;value+=multiple)
   {
   calculaterange (vector + value, remainingsum - value, nofremainingvalues-1, multiple, maxdistance);
   }
}

main()
{
calculaterange (emptyvector, 100, 2, 20);
}

Ответ 3

Почему вы не можете использовать метод грубой силы с небольшой оптимизацией? Например, скажем N - количество комбинаций M - Multiples D - Максимальное возможное расстояние

Таким образом, возможными значениями в комбинациях могут быть M, 2M, 3M и т.д. Вам нужно сгенерировать этот набор, а затем начать с первого элемента из набора и попытаться выяснить следующие два из выбора значений из одного и того же набора (при условии, что они должны быть меньше D от первого/второго значения). Таким образом, с i/p 3-10-30 будет

• Создайте набор из 10, 20, 30, 40, 50, 60, 70, 80, 90 в качестве возможных значений
• Начните с 10, выбор для второго значения должен быть 20, 30, 40, 50 (D < 30)
• Теперь выберите второе значение из набора 20, 30, 40, 50 и попробуйте получить следующее значение и т.д.

Если вы используете рекурсию, тогда решение станет еще проще.

• Вы должны найти N значений из список возможных значений в пределах MIN & MAX.
• Итак, попробуйте первое значение в MIN (индекс MAX). Скажем, мы выбрали значение в X-индексе.
• Для каждого первого значения попробуйте найти выведите значения N-1 из списка, где MIN =   X + 1 и MAX.

Наихудшая производительность будет иметь место, когда M = 1 и N достаточно велики.

Ответ 4

Является ли расстояние между всеми аддитивными факторами или между ними? Например, с 3-10-20, является ли [20-40-60] действительным ответом? Я буду считать последнее, но нижеприведенное решение может быть изменено довольно тривиально, чтобы работать для первого.

В любом случае, путь - начать с самого крайнего ответа (одного вида), с которым вы можете справиться, а затем пройти ответы до тех пор, пока не дойдете до самого крайнего.

Попробуйте поместить числа как можно ниже, за исключением последнего, который будет как можно выше (учитывая, что остальные низкие). Пусть общий делитель d и делит на нем 100, поэтому мы имеем S = 100/d. Это качественно квантовало нашу проблему. Теперь у нас есть наше ограничение, что интервал не более s, за исключением того, что мы преобразуем это в число квантованных шагов, n = s/d. Теперь предположим, что мы имеем M samples, i1...iM и записываем ограничения:

i1 + i2 + i3 + ... + iM = S
0 <= i1 <= n
0 <= i2 <= n
. . .
0 <= iM <= n
i1 <= i2
i2 <= i3
. . .
i(M-1) <= iM

Мы можем решить первое уравнение, получив iM, учитывая другие.

Теперь, если мы сделаем все как можно более похоже:

i1 = i2 = ... = iM = I
M*I = S
I = S/M

Очень хорошо - у нас есть отправная точка! (Если I является дробью, сделайте первые несколько I и остаток I+1.) Теперь мы просто пытаемся ходить по каждой переменной по очереди:

for (i1 = I-1 by -1 until criteria fails)
  sum needs to add to S-i1
  i2 >= i1
  i2 <= i1 +n
  solve the same problem for M-1 numbers adding to S-i1
  (while obeying the above constraint on i2)

Хорошо, смотрите здесь - у нас есть рекурсивный алгоритм! Мы просто проходим и читаем ответы.

Конечно, мы могли бы идти i1 вверх, а не вниз. Если вам нужно распечатать ответы, может это сделать. Если вам просто нужно их подсчитать, обратите внимание, что подсчет является симметричным, поэтому просто удвойте ответ, который вы получаете от подсчета. (У вас также будет коэффициент коррекции, если не все значения начались одинаково - если некоторые из них были I, а некоторые из них были I+1, вам нужно учитывать это, чего я не буду делать здесь.)

Изменить: если диапазон соответствует всем значениям, а не всем

0 <= i1 <= n

у вас есть

max(i1,i2,...,iM) - min(i1,i2,...,iM) <= n

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

Ответ 5

Input: (2-10-20)

• Разделите число по параметру 1

(50,50)

2 Проверьте, разрешает ли это правило разницы это сочетание. Если это вредит правилу, тогда STOP, если он разрешает, затем добавьте эту комбинацию в список результатов

Например: abs (50-50) < 20, так что это нормально

3 Увеличьте первое значение по параметру 2, уменьшите второе значение по параметру 2

4. Перейти 2. точка