Алгоритм: все возможные целые из наборов от .. до

#рекурсия #комбинаторика #алгоритм #javascript

Вроде простая задача, но что-то лыжи не едут.

Дан массив диапазонов — пар мин. и макс. значений. Только целые числа.
Нужно найти все возможные целые, получаемые суммированием «допустимых» значений из
произвольного комплекта идущих подряд диапазонов, по одному из каждого участвующего.
Например, дано три диапазона:
[{"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? Подскажите, как называются
алгоритмы для похожих задач?    

Ответы

Ответ 1

Складывая два интервала [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
Ответ 2

вот такое решение не подойдет ?
var ranges=[{"min":2,"max":3},{"min":1,"max":20},{"min":3,"max":5},{min: 2,max: 10}];
//var ranges=[{"min":2,"max":3},{"min":2,"max":2},{"min":2,"max":2}]
function range2array(range) {
    var ret=[];
    for (var i=range.min;i<=range.max;i++) ret.push(i);
    return ret;
}

function arrays_summ(array1,array2) {
    var ret=[];
    if (array2===undefined) return array1;
    for (var i in array1) 
        for (var n in array2) 
          ret.push(array1[i]+array2[n]);
    return ret;
}

function process(ranges) {
    var lastarray;
    var result={};
    for (var i in ranges) {
        lastarray=arrays_summ(range2array(ranges[i]),lastarray);
        for (var n in lastarray) result[lastarray[n]]=1;
    }
    return result;
}
function keys2array(hash){
    var ret=[];
    for (var i in hash) {
        ret.push(i);
    }
    return ret.sort(function(a,b) {return (a*1)>(b*1)?1:-1;})
}
console.log(keys2array(process(ranges)));

http://jsfiddle.net/oceog/mhT5Z/


Ответ 3

Пример здесь http://jsfiddle.net/8cdez/7/
Осталось только обернуть в красивую функцию, но само решение не очень красивое, плюсики
ответу не ставьте, пожалуйста. Пусть будет.  

test=[{"min":2,"max":3},{"min":2,"max":2},{"min":2,"max":2}];
res=new Array();
for (var x=test[0].min; x<=test[0].max; x++) {
    for (var y=0; y<=test[1].max; y++ ? y!=0: y=test[1].min) {
        for (var z=0; z<=test[1].max; z++ ? z!=0: z=test[2].min) {
            res.push(x+y+z);
        }
    }
};
res.push(test[1].min+test[2].min);
res.push(test[1].max+test[2].max);
res=_.unique(res.sort());
alert(res);

Используется UnderScore (функция unique).