Вроде простая задача, но что-то лыжи не едут. Дан массив диапазонов — пар мин. и макс. значений. Только целые числа. Нужно найти все возможные целые, получаемые суммированием «допустимых» значений из произвольного комплекта идущих подряд диапазонов, по одному из каждого участвующего. Например, дано три диапазона: [{"min":1,"max":2},{"min":3,"max":4},{"min":5,"max":6}] Можно получить числа [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]. На деле пар больше, значения веселее. Может, есть известный красивый алгоритм? В общем смысл моего, далеко не оптимального, решения, такой (перебор): распаковать пары min:max до массивов допустимых значений [[1,2],[3,4],[5,6]] перебирать массивы слева направо; для каждого варианты глубины вправо от 0 (только себя), до правого края; перебрать все возможные комбинации значений между этими массивами, по одному зн. из каждого. Суммировать, уникальные значения сохранить в результат. Интересно ещё решить обратную задачу: даны опять эти пары, и число. Разложить его в идущие подряд допустимые значения. Усложнённая условием про «подряд» Subset Sum Problem? Подскажите, как называются алгоритмы для похожих задач?
Ответ
Складывая два интервала [a,b]+[c,d] получим итервал [a+c,b+d], если интервалов больше то будет [a1+a2+...+an,b1+b2+...+bn]. Таким образом мы избавляемся от лишних вычислений, в частности от рекурсии совсем. Нам достаточно знать для каждой комбинации интервалов сумму их минимумов и сумму их максимумов.
Чтобы перебрать все комбинации интервалов будем двигать границы в списке интервалов. Т.е. сначала будем смотреть первый интервал, потом первый и второй, потом с первого по n-й, затем второй, со второго по третий и т.д.
var a = [{"min":2,"max":3},{"min":2,"max":2},{"min":2,"max":2}];
var a_l = a.length;
var res = [];
for (var i=0;i
Комментариев нет:
Отправить комментарий