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

Question

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

Это

• Количество комбинаций
• Коэффициент умножения
• расстояние

Пример ввода 1: (2-10-20)

Это значит

• перечислите действительную двухстороннюю комбинацию, чтобы сформировать 100.
• расстояние между комбинациями должно быть не более 20.
• И вся полученная комбинация должна делиться на заданный коэффициент умножения 10

Вывод будет

[40,60]

[50,50]

[60,40]

здесь [30,70], [20,60] недопустимы, потому что расстояние больше 20.

Пример ввода 2: [2-5-20]

[40,60]

[45,55]

[50,50]

* * Тысяча сорок-девять [55,45]

[60,40]

Я был бы очень признателен, если бы вы направили меня в правильном направлении.

Приветствие.

Answer 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

Answer 2

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

100/2 - N / 2

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

100/3 - 2N / 3

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

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

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

(100 - (М-1) Н) / М

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

(100 + (М-1) Н) / М

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

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

• расстояние с первым значением (не должно быть больше вашего максимального расстояния)
• можем ли мы еще достичь суммы (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 для двух других значений. Опять же, мы можем распределить 80 по 2 значениям с максимальным расстоянием 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);
}

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Давайте попробуем разместить как можно более низкие числа, за исключением последнего, который будет максимально высоким (учитывая, что остальныенизкие).Пусть общий делитель будет d и разделим на него 100, чтобы мы получили S = 100/d.Это хорошо определяет нашу проблему.Теперь у нас есть ограничение на расстояние не более s, за исключением того, что мы преобразуем его в число квантованных шагов n = s/d.Теперь предположим, что у нас есть M выборок, 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 (или к тому, какой это поворот другой переменной).

Answer 5

Входной сигнал: (2-10-20)

1. Разделите число на параметр 1

(50,50)

2 Проверьте, разрешает ли правило разности эту комбинацию. Если это повредит правилу, тогда ОСТАНОВИТЕ, если это позволяет, затем добавьте это и его комбинации в список результатов

Например: abs (50-50) <20, так что все в порядке </p>

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

4. Go 2. точка