найти все возможные комбинации из N неповторяющихся чисел в определенном диапазоне, которые складываются в X

Я уже несколько месяцев пытаюсь найти решение этой проблемы. это для моего художественного проекта. до сих пор я мог найти частичные решения python и c, но они бесполезны для моего случая... мне нужно рабочее решение либо на PHP, либо на Javascript.

Вот в чем вопрос:

  1. найти все возможные комбинации из N чисел, при этом должно выполняться следующее:
    • числа не повторяются в комбинации
    • числа не повторяются в других решениях в другом порядке
    • используются только целые числа
  2. в пределах некоторого диапазона целых чисел
  3. , которые складываются в X

Например:

  1. найти все комбинации из 3 чисел
  2. внутри всех чисел от 1-12
  3. что в сумме дает 15

Вычисленное решение должно выплюнуть: 

[1,2,12]
[1,3,11]
[1,4,10]
[1,5,9]
[1,6,8]
[1,7,7] = EXAMPLE OF WRONG OUTPUT, NO REPEATING NUMBERS WITHIN COMBINATION
[1,8,6] = EXAMPLE OF WRONG OUTPUT, NO REPEATING NUMBERS IN OTHER SOLUTIONS (see [1,6,8])
[2,3,10]
[2,4,9]
[2,5,8]
[2,6,7]
[3,4,8]
[3,5,7]
[4,5,6]
Очевидно, что это было легко сделать за пару минут вручную, но мне нужно вычислить гораздо больший диапазон и многое другое. цифры, поэтому мне нужен короткий сценарий, чтобы сделать это для меня...

Любая помощь будет оценена!

5 5
javascript php numbers algorithm combinations

5 ответов:

Я чувствую, что самый элегантный способ справиться с этой проблемой-это рекурсия.

function getCombos(target, min, max, n) {
    var arrs = [];
    if (n === 1 && target <= max) {
        arrs.push([target]);
    } else {
        for (var i = min; i < target / n && i <= max; i++) {
            var arrays = getCombos(target - i, i + 1, max, n - 1);
            for (var j = 0; j < arrays.length; j++) {
                var array = arrays[j];
                array.splice(0, 0, i);
                arrs.push(array);
            }
        }
    }
    return arrs;
}

Объяснение

Это работает путем восхождения от минимального числа i как первого элемента в каждом массиве и передачи остатка (target-i) обратно в рекурсивную функцию, которая будет разбита на компоненты n-1, причем минимум увеличивается на единицу с каждым рекурсивным вызовом. 
15 = (1 + 14) = 1 + (2 + 12)
15 = (1 + 14) = 1 + (3 + 11)
15 = (1 + 14) = 1 + (4 + 10)
    ...
15 = (1 + 14) = 1 + (6 + 8)
15 = (2 + 13) = 2 + (3 + 10)
15 = (2 + 13) = 2 + (4 + 9)
    ...
15 = (4 + 11) = 4 + (5 + 6)
Обратите внимание, что числа в первом индексе каждого массива никогда не будут превышать target/n, где target - это число, которое вы суммируете, а n - это число элементов в массиве. (Таким образом, при разбиении 15 на 3 компонента первая колонка всегда будет меньше 5.) Это справедливо и для других столбцов, но n уменьшается на 1 по мере роста индекса массива. Знание этого позволяет нам рекурсировать, не требуя дополнительных параметров для нашей рекурсивной функции.

Рабочий Пример

Проверьте фрагмент ниже, чтобы увидеть его в действие.

function getCombos(target, min, max, n) {
    var arrs = [];
    if (n === 1 && target <= max) {
        arrs.push([target]);
    } else {
        for (var i = min; i < target / n && i <= max; i++) {
            var nextTarget = target - i;
            var nextMin = i + 1;
            var arrays = getCombos(nextTarget, nextMin, max, n - 1);
            for (var j = 0; j < arrays.length; j++) {
                var array = arrays[j];
                array.splice(0, 0, i);
                arrs.push(array);
            }
        }
    }
    return arrs;
}

document.getElementById("submit").onclick = function () {
    var target = document.getElementById("target").value;
    var min = document.getElementById("min").value;
    var max = document.getElementById("max").value;
    var n = document.getElementById("n").value;
    var result = getCombos(+target, +min, +max, +n);
    document.getElementById("output").innerHTML = result.join("<br/>");
};
.table {
    display:table;
    table-layout:fixed;
    width:100%;
}
.table-row {
    display:table-row;
}
.cell {
    display:table-cell;
}
<div class="table">
    <div class="table-row">
        <div class="cell">Target:</div>
        <div class="cell">
            <input id="target" type="text" value=15>
        </div>
        <div class="cell">n:</div>
        <div class="cell">
            <input id="n" type="text" value=3>
        </div>
    </div>
    <div class="table-row">
        <div class="cell">Min:</div>
        <div class="cell">
            <input id="min" type="text" value=1>
        </div>
        <div class="cell">Max:</div>
        <div class="cell">
            <input id="max" type="text" value=12>
        </div>
    </div>
</div>
<input id="submit" type="button" value="submit" />
<div id="output" />
2

Если вы создадите списки в порядке возрастания, вы избежите повторения обоих видов.

Простое рекурсивное решение состоит в том, чтобы выбрать каждый возможный первый элемент, а затем рекурсивно вызвать генератор, запрашивающий возможные продолжения: то есть продолжения ограничены наличием одного меньшего элемента, начиная со значения, большего, чем выбранный элемент, и суммируя до желаемой суммы минус выбранный элемент. 
 Partitions(min, size, total):
   if size is 1:
     if total < min: return nothing
     else return the list [total]

   for each value i between min and total:
     get the set of lists Partitions(i+1, size-1, total-i)
     add i to the beginning of each list
   return all the lists.

Вышесказанное может быть улучшено путем не позволяя i выйти за пределы наибольшей практической ценности или, по крайней мере, за пределы консервативной оценки. Кроме того, вы можете остановить инкрементирование i после того, как рекурсивный вызов вернет пустой набор.

1

Ниже приведена рекурсивная функция, которая делает то, что вы хотите.

Для вашего примера, вы бы назвали это так: 

combos(3, 1, 12, 15);

Дополнительные параметры функции (a, running, current) Следите за текущим состоянием и можете игнорировать: 

var arr= [];

function combos(num, min, max, sum, a, running, current) {
  var i;

  a= a || [];
  running= running || 0;
  current= current || min;

  for(i = current ; i <= max ; i++) {
    if(num===1) {
      if(i+running===sum) {
        arr.push(a.concat(i));
      }
    }
    else {
      combos(num-1, min, max, sum, a.concat(i), i+running, i+1);
    }
  }
};

Скрипка

1

Вот немного оптимизированное решение. Перебегая от наибольшего к наименьшему в диапазоне, становится довольно легко пропустить все возможности, которые слишком велики.

function combos(size, start, end, total, solution) {  
    var solutions = [];
    solution = solution || [];
    if (size === 1) {        
        if (start <= total && end >= total) {            
            solutions.push(solution.concat([total]));
        }
        return solutions;
    } else {
        while (end > start) {
            var newTotal = total - end;                    
            solutions = solutions.concat(
                combos(
                    size - 1, 
                    start, 
                    Math.min(end - 1, newTotal), 
                    newTotal, 
                    solution.concat([end])
                )
            );   
            end--;
        }
        return solutions;
    }
}
1

Может быть неэффективно для больших чисел, но с помощью 3 вложенных for() циклов вы можете сделать - 

$t=20; // up to X
$s=$t-3; // sets inner loop max
$r=$t/3; // sets middle loop max
$q=$r-1; // sets outer loop max
$results= array(); // array to hold results

for($x=1;$x<=$q;$x++){

    for($y=($x+1);$y<=$r;$y++){

        for($z=($x+2);$z<=$s;$z++){

            // if sum == max && none are the same value
            if(($x+$y+$z)==$t && ($x!=$y && $x!=$z && $y!=$z)){
                $results[]=array($x,$y,$z);

            }

        }
    }
}
0