View Full Version : Combinations of numbers that add up to a total.
FullThrottle 09292011, 11:11 PM I looked around for a solution but could not find one. I am trying to find combinations of numbers that can add up to a total. The numbers available and the total are different each time.
For example, I have an array that contains the following numbers:
[16,12,8,6,4,2]
I want to find the combinations that add up to 140, like this:
8x16,1x12
8x16,1x8,1x4
11x12,1x8
Notice I do not do:
8x16,2x6
8x16,3x4
This is because as a rule, only the first number can be used in multiple of more than one. All other number pairs can only be a 1x.
Output string could be formatted like this in a single string containing all combinations:
8x16,1x128x16,1x8,1x411x12,1x8
ironboy 09292011, 11:51 PM Looks like homework to me... :D
ironboy 09292011, 11:57 PM Read and learn:
http://www.mathsisfun.com/primefactorization.html
FullThrottle 09302011, 12:03 AM Its not homework, but thanks for looking.
I'm stuck on this problem and am looking for an elegant way to do it. I gave a simple starting array, but it could be far more complex, such as [64, 48, 40, 36, 32, 28, 24, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2], which would produce a larger number of combinations. Even larger arrays would be expected when testing with larger totals, so something fast and efficient is needed.
ironboy 09302011, 12:04 AM So what do you use this for then?
ironboy 09302011, 12:10 AM If I understand you correctly only the first number pair is actually a pair (i.e. to items from the array)  all other are just one item from the array?
Or are each pair always only one from the array and the multiple can be arbitrary?
Old Pedant 09302011, 12:36 AM Not to ask a dumb question, but what is the point in displaying the 1x values?
That is, why
8x16,1x12
8x16,1x8,1x4
11x12,1x8
instead of simply
8x16,12
8x16,8,4
11x12,8
And why is it listed in that order instead of larger number first?
16x8,12
16x8,8,4
12x11,8
It is the kind of requirements you put on it that make it feel like homework. Doesn't feel like a real world problem.
Oh...and where did 11x12 come from? There's no 11 in your original array.
Anyway, there's really no answer for this except recursion. Probably could be done without it, but so much easier to conceive of using recursion.
FullThrottle 09302011, 01:05 AM This is being used for an imposition model (how to layout things on a bigger area).
Your right, there is no point in displaying the 1x notation, other than for readability. It could very well be:
8x16,8,4
11x12,8
4x32,12
Regardless, the final output contains all the possible combinations in a single string separated by a delimiter, for example:
8x16,8,411x12,84x32,12etc.
8 x 16 + 8 + 4 = 140
11 x 12 + 8 = 140
4 x 32 + 12 = 140
First number is arbitrary, but the second is always from the array. Only the first number can be used more than once (8x16, all others are 1x).
Hope that helps clarify it.
Old Pedant 09302011, 01:46 AM Okay, almost have it. But one more thing:
For example, I have an array that contains the following numbers:
[16,12,8,6,4,2]
I want to find the combinations that add up to 140, like this:
8x16,1x12
8x16,1x8,1x4
11x12,1x8
Ummm... once again, you do *NOT* have 11 in your array. So will ignore that one.
But...
*ARE* you allowed to use the same number twice???
8x16,1x8,1x4
??? That seems inconsistent with your other rules.
And your list there is wrong, as I read it. You are missing possibilities.
My result:
[16,12,8,6,4,2]
16x8,1x1216x8,1x8,1x416x8,1x6,1x4,1x216x6,1x16,1x12,1x8,1x6,1x212x8,1x16,1x12,1x8,1x6,1x2
Again, that assumes I can reuse a number in a "1x" when it has already been used in the first product.
Old Pedant 09302011, 02:30 AM Here, rather than waiting for you:
<html>
<head><script type="text/javascript">
var answer;
function targetFromArray( arr, target )
{
answer = [];
// sort descending, just to be safe
arr = arr.sort( function(n1,n2) { return n2n1; } );
// alert( arr );
// first, find factors:
for ( var i = 0; i < arr.length; ++i )
{
var n1 = arr[i];
var ar2 = arr.concat([]); // clone the array
ar2.splice(i,1); // remove n1 from it
for ( var j = i+1; j < arr.length; ++j )
{
var n2 = arr[j];
var ar3 = ar2.concat([]); // clone the array
// then remove n2 from it
for ( var n = 0; n < ar3.length; ++n )
{
if ( ar3[n] == n2 )
{
ar3.splice( n, 1 );
break;
}
}
var product = n1 * n2;
var list = n1 + "x" + n2;
if ( product == target )
{
// alert( list );
answer.push( list );
} else if ( product < target ) {
sumFromArray( list, ar3, target  product );
}
}
}
return answer.join( "" );
}
function sumFromArray( list, arx, target )
{
for ( var i = 0; i < arx.length; ++i )
{
var n = arx[i];
var nlist = list + ",1x" + n;
if ( n == target )
{
// alert( nlist );
answer.push( nlist );
} else if ( n < target ) {
var ary = arx.concat([]);
ary.splice( 0, i+1 );
if ( ary.length > 0 ) sumFromArray( nlist, ary, target  n );
}
}
}
var test = [8,2,16,4,12,6];
function testit() { document.getElementById("result").innerHTML = targetFromArray( test, 140 ); }
</script>
</head>
<body>
<input type="button" value="try it" onclick="testit()"/>
<div id="result"></div>
</body>
</html>
That code does *NOT* use "1xN" where "N" is one of the number in the first product.
So for
test = [8,2,16,4,12,6];
result is 16x8,1x1216x8,1x6,1x4,1x2
If you want to have "1xN" where "N" is already in the first product, make one tiny change:
} else if ( product < target ) {
sumFromArray( list, ar3, target  product );
}
to
} else if ( product < target ) {
sumFromArray( list, arr, target  product );
}
Then for
test = [8,2,16,4,12,6];
result is 16x8,1x1216x8,1x8,1x416x8,1x6,1x4,1x216x6,1x16,1x12,1x8,1x6,1x212x8,1x16,1x12,1x8,1x6,1x2
Happy?
ironboy 09302011, 02:43 AM Wow, that looks complicated ;) How about:
//possibleParts(numbers:array,target:number)
var possibleParts = (function(){
var r;
var a = function(numbers,target,partial){
var i, s;
for(i=0,s=0;i<partial.length;s+=partial[i++]);
if(s > target){return};
partial.s = s;
(s == target  0 == (targets)%partial[0]) && r.push(partial);
for (i = 0; i < numbers.length; i++){
a(numbers.slice(i+1),target,partial.concat(numbers[i]));
};
};
var b = function(x,target){
for(var i = 0; i < x.length; i++){
for(var j = 0; j < x[i].length; j++){
x[i][j] = j == 0 && x[i].s < target
? ((targetx[i].s+x[i][0])/x[i][0]) + 'x' + x[i][0]
: x[i][j] = '1x' + x[i][j];
};
x[i] = x[i].join(',');
};
x = x.join('');
return x
};
return function(numbers,target){
r = [];
a(numbers,target,[]);
return b(r,target)
}
})();
ironboy 09302011, 02:50 AM Test:
possibleParts([16,12,8,6,4,2],140)
Result:
8x16,1x127x16,1x12,1x8,1x6,1x28x16,1x8,1x48x16,1x6,1x4,1x211x12,1x810x12,1x8,1x6,1x4,1x211x12, 1x6,1x216x8,1x6,1x4,1x217x8,1x423x6,1x235x470x2
Old Pedant 09302011, 02:53 AM Doesn't seem to work.
Calling possibleParts([16,12,8,6,4,2],140)
Produced this result:
8x16,1x127x16,1x12,1x8,1x6,1x28x16,1x8,1x48x16,1x6,1x4,1x211x12,1x810x12,1x8,1x6,1x4,1x211x12, 1x6,1x216x8,1x6,1x4,1x217x8,1x423x6,1x235x470x2
??? It seems to ignore the array of numbers.
EDIT: So we agree. And it doesn't fulfill the conditions he asked for, at all.
Note that your answer can include only numbers *from* the array.
ironboy 09302011, 02:56 AM I think it does exactly what he asks for ;)
(Took me a while to understand what was asked for:
in each result the first item can be multiplied several times)
Old Pedant 09302011, 02:59 AM <shrug> I guess we will find out, if he ever comes back.
I do note that adding that condition to your code would be easy, so not a big deal.
Old Pedant 09302011, 03:02 AM Ahhh...I see what you are basing that on!
First number is arbitrary, but the second is always from the array
Okay, I agree with your answer, then.
But that sentence doesn't seem to me to jibe with the first one in the same message
This is being used for an imposition model (how to layout things on a bigger area).
Ah, well.
ironboy 09302011, 03:05 AM I qoute:
First number is arbitrary, but the second is always from the array. Only the first number can be used more than once (8x16, all others are 1x).
ironboy 09302011, 03:06 AM :p Crossposted...
Old Pedant 09302011, 03:16 AM imposition is the art of laying out multiple print jobs on a single printed page.
In other words, if you have a customer who wants a 9x12 poster, and you have 16x20 paper, you might put two copies per piece of paper. But you might also put only one per piece of paper and, at the same time, print a job for a customer who has a need for something that it 6x8. And so on. (And you charge both customers for the cost of the full 16x20 sheet, if you are nasty.)
So, actually, I'm not sure I see why he wants the kind of answer he wants. Not sure why you'd want to limit anything to 1xN, for example. (Because, for example, you could put two 6x8 along with that one 9x12 on the same sheet.)
Oh, well.
ironboy 09302011, 03:23 AM @OldPedant:
I agree with what you say, but imposition is about area isn't it. So each item should actually have three numbers in that case i.e:
numberOfCopiesOnSheet x width x height
so it doesn't make sense for this either... (Unless I'm missing something about running the algorithm twice for each calculation...)
Old Pedant 09302011, 03:26 AM Yes, exactly what I very clumsily tried to say. Thanks for articulating it.
FullThrottle 09302011, 03:39 PM Thanks guys. Your answers have helped to give me enough to solve my problem.

