Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 1 of 2 12 LastLast
Results 1 to 15 of 22
  1. #1
    New to the CF scene
    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,1x12|8x16,1x8,1x4|11x12,1x8

  • #2
    Regular Coder
    Join Date
    Sep 2011
    Location
    Sweden
    Posts
    154
    Thanks
    1
    Thanked 22 Times in 22 Posts
    Looks like homework to me...

  • #3
    Regular Coder
    Join Date
    Sep 2011
    Location
    Sweden
    Posts
    154
    Thanks
    1
    Thanked 22 Times in 22 Posts

  • #4
    New to the CF scene
    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.

  • #5
    Regular Coder
    Join Date
    Sep 2011
    Location
    Sweden
    Posts
    154
    Thanks
    1
    Thanked 22 Times in 22 Posts
    So what do you use this for then?

  • #6
    Regular Coder
    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; 09-30-2011 at 12:12 AM.

  • #7
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,933
    Thanks
    79
    Thanked 4,424 Times in 4,389 Posts
    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; 09-30-2011 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.

  • #8
    New to the CF scene
    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,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.
    Last edited by FullThrottle; 09-30-2011 at 01:09 AM.

  • #9
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,933
    Thanks
    79
    Thanked 4,424 Times in 4,389 Posts
    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:
    Code:
    [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.
    Last edited by Old Pedant; 09-30-2011 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.

  • #10
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,933
    Thanks
    79
    Thanked 4,424 Times in 4,389 Posts
    Here, rather than waiting for you:
    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 n2-n1; } );
        // 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
    Code:
    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:
    Code:
                } else if ( product < target ) {
                    sumFromArray( list, ar3, target - product );
                }
    to
    Code:
                } else if ( product < target ) {
                    sumFromArray( list, arr, target - product );
                }
    Then for
    Code:
    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?
    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.

  • #11
    Regular Coder
    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 == (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)
      }
    })();

  • #12
    Regular Coder
    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,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

  • #13
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,933
    Thanks
    79
    Thanked 4,424 Times in 4,389 Posts
    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.

    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.

  • #14
    Regular Coder
    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)

  • #15
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,933
    Thanks
    79
    Thanked 4,424 Times in 4,389 Posts
    <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.


  •  
    Page 1 of 2 12 LastLast

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •