PDA

View Full Version : Combinations of numbers that add up to a total.

FullThrottle
09-30-2011, 12:11 AM
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,1x12|8x16,1x8,1x4|11x12,1x8

ironboy
09-30-2011, 12:51 AM
Looks like homework to me... :D

ironboy
09-30-2011, 12:57 AM
http://www.mathsisfun.com/prime-factorization.html

FullThrottle
09-30-2011, 01: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
09-30-2011, 01:04 AM
So what do you use this for then?

ironboy
09-30-2011, 01: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
09-30-2011, 01: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

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
09-30-2011, 02: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,4|11x12,8|4x32,12|etc.

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
09-30-2011, 02: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,1x12|16x8,1x8,1x4|16x8,1x6,1x4,1x2|16x6,1x16,1x12,1x8,1x6,1x2|12x8,1x16,1x12,1x8,1x6,1x2

Again, that assumes I can re-use a number in a "1x" when it has already been used in the first product.

Old Pedant
09-30-2011, 03:30 AM
Here, rather than waiting for you:

<html>

function targetFromArray( arr, target )
{

// sort descending, just to be safe
arr = arr.sort( function(n1,n2) { return n2-n1; } );

// 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 )
{
} else if ( product < target ) {
sumFromArray( list, ar3, target - product );
}
}
}
}

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 )
{
} 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>
<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,1x12|16x8,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,1x12|16x8,1x8,1x4|16x8,1x6,1x4,1x2|16x6,1x16,1x12,1x8,1x6,1x2|12x8,1x16,1x12,1x8,1x6,1x2

Happy?

ironboy
09-30-2011, 03: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 == (target-s)%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
? ((target-x[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
09-30-2011, 03:50 AM
Test:
possibleParts([16,12,8,6,4,2],140)
Result:
8x16,1x12|7x16,1x12,1x8,1x6,1x2|8x16,1x8,1x4|8x16,1x6,1x4,1x2|11x12,1x8|10x12,1x8,1x6,1x4,1x2|11x12, 1x6,1x2|16x8,1x6,1x4,1x2|17x8,1x4|23x6,1x2|35x4|70x2

Old Pedant
09-30-2011, 03:53 AM
Doesn't seem to work.

Calling possibleParts([16,12,8,6,4,2],140)

Produced this result:
8x16,1x12|7x16,1x12,1x8,1x6,1x2|8x16,1x8,1x4|8x16,1x6,1x4,1x2|11x12,1x8|10x12,1x8,1x6,1x4,1x2|11x12, 1x6,1x2|16x8,1x6,1x4,1x2|17x8,1x4|23x6,1x2|35x4|70x2

??? It seems to ignore the array of numbers.

EDIT: So we agree. And it doesn't fulfill the conditions he asked for, at all.

ironboy
09-30-2011, 03: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
09-30-2011, 03: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
09-30-2011, 04:02 AM
Ahhh...I see what you are basing that on!

First number is arbitrary, but the second is always from the array

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
09-30-2011, 04: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
09-30-2011, 04:06 AM
:p Cross-posted...

Old Pedant
09-30-2011, 04: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
09-30-2011, 04: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
09-30-2011, 04:26 AM
Yes, exactly what I very clumsily tried to say. Thanks for articulating it.

FullThrottle
09-30-2011, 04:39 PM
Thanks guys. Your answers have helped to give me enough to solve my problem.