Enjoy an ad free experience by logging in. Not a member yet? Register.


Results 1 to 15 of 22

09292011, 11:11 PM #1
 Join Date
 Sep 2011
 Posts
 4
 Thanks
 0
 Thanked 0 Times in 0 Posts
Combinations of numbers that add up to a total.
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
09292011, 11:51 PM
#2
 Join Date
 Sep 2011
 Location
 Sweden
 Posts
 154
 Thanks
 1
 Thanked 22 Times in 22 Posts
Looks like homework to me...
09292011, 11:57 PM
#3
 Join Date
 Sep 2011
 Location
 Sweden
 Posts
 154
 Thanks
 1
 Thanked 22 Times in 22 Posts
Read and learn:
http://www.mathsisfun.com/primefactorization.html
09302011, 12:03 AM
#4
 Join Date
 Sep 2011
 Posts
 4
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.
09302011, 12:04 AM
#5
 Join Date
 Sep 2011
 Location
 Sweden
 Posts
 154
 Thanks
 1
 Thanked 22 Times in 22 Posts
So what do you use this for then?
09302011, 12:10 AM
#6
 Join Date
 Sep 2011
 Location
 Sweden
 Posts
 154
 Thanks
 1
 Thanked 22 Times in 22 Posts
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?
Last edited by ironboy; 09302011 at 12:12 AM.
09302011, 12:36 AM
#7
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.
Last edited by Old Pedant; 09302011 at 12:40 AM.
An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.
09302011, 01:05 AM
#8
 Join Date
 Sep 2011
 Posts
 4
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.
Last edited by FullThrottle; 09302011 at 01:09 AM.
09302011, 01:46 AM
#9
Okay, almost have it. But one more thing:
Ummm... once again, you do *NOT* have 11 in your array. So will ignore that one.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
But...
*ARE* you allowed to use the same number twice???
??? That seems inconsistent with your other rules.8x16,1x8,1x4
And your list there is wrong, as I read it. You are missing possibilities.
My result:
Again, that assumes I can reuse a number in a "1x" when it has already been used in the first product.Code:[16,12,8,6,4,2] 16x8,1x1216x8,1x8,1x416x8,1x6,1x4,1x216x6,1x16,1x12,1x8,1x6,1x212x8,1x16,1x12,1x8,1x6,1x2
Last edited by Old Pedant; 09302011 at 01:56 AM.
An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.
09302011, 02:30 AM
#10
Here, rather than waiting for you:
That code does *NOT* use "1xN" where "N" is one of the number in the first product.Code:<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>
So forIf you want to have "1xN" where "N" is already in the first product, make one tiny change:Code:test = [8,2,16,4,12,6]; result is 16x8,1x1216x8,1x6,1x4,1x2
toCode:} else if ( product < target ) { sumFromArray( list, ar3, target  product ); }
Then forCode:} else if ( product < target ) { sumFromArray( list, arr, target  product ); }Happy?Code: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
An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.
09302011, 02:43 AM
#11
 Join Date
 Sep 2011
 Location
 Sweden
 Posts
 154
 Thanks
 1
 Thanked 22 Times in 22 Posts
Wow, that looks complicated How about:
Code://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) } })();
09302011, 02:50 AM
#12
 Join Date
 Sep 2011
 Location
 Sweden
 Posts
 154
 Thanks
 1
 Thanked 22 Times in 22 Posts
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
09302011, 02:53 AM
#13
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.
An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.
09302011, 02:56 AM
#14
 Join Date
 Sep 2011
 Location
 Sweden
 Posts
 154
 Thanks
 1
 Thanked 22 Times in 22 Posts
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)
09302011, 02:59 AM
#15
<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.
An optimist sees the glass as half full.
A pessimist sees the glass as half empty.
A realist drinks it no matter how much there is.