Programming Questions

Help understanding Array Addition in JavaScript

For this problem http://coderbyte.com/CodingArea/information.php?ct=Array%20Addition%20I
I'm having trouble figuring out a way to go through each element in the array and check if every combination == the largest number.
Sorting the array is fine, 'pop'ping the largest number is fine, but finding all combinations is killing me haha. I looked at solutions but they are using methods I don't understand yet - can someone explain a more basic approach? Specifically how think about loops going through array elements. I kind of understand recursion so that can be included.

lumberjack87
posted this question on 6/11/14 **|**

5

This uses recursion to check every combination:

function subsetsum(target, array) { if (array.length == 0) { return target == 0; } var n = array[0]; array = array.slice(1); return subsetsum(target, array) || subsetsum(target - n, array); }Obviously you have to separate the maximum element (target) first.

scates

answered on 06/22/14

5

In order to do this in-place on the existing array you need to apply a special addition pattern. If you want to try every possible combination you may recognize that, if you picture the array without the largest element as a bitfield (1 bit per element), simply starting from 1 and continuously adding 1 until the largest possible value is reached will check all combinations. To make it a bit more concrete:
array: [1,8,9,17]
max =17 //you need to find this
//incluse array[i] if 1
0,0,0 can always be ignored.
1,0,0: 1
0,1,0: 8
1,1,0: 9
0,0,1: 9
1,0,1: 10
0,1,1: 17 - done, continuation for completeness
1,1,1: 18
The reason why I wrote it out like this is that you should be able to see now that this approach takes O(2^n) time - where n is the number of elements in the array - which means this solution is exponential time.
I am not entirely sure that there is no faster solution, but I think the problem itself has high computational complexity, such that I couldn't see any way to apply dynamic programming or a different classic approach, which covers all possible cases in a more efficient way.
However the algorithm described above is deterministic, so at least you get that compared to random selection, which is probabilistic (if you are unlucky, you just never get the right combination - this approach gets REALLY BAD if there is only one combination and the array is big).
I did intentionally not include a solution how to implement the iteration pattern on the array, so you can try for yourself.

mike0809

answered on 06/20/14

0

Mike, I have that same matrix written on a piece of paper and I don't know if it has a name or how to generate one given an array length. I know its an n x 2^n matrix and I can figure it out for various array sizes, but I can't think of the way to do it in JavaScript!
Do you know how to generate it?

Funktapus

answered on 06/20/14

0

@Funktapus: I wish I could have responded via pm, but I hope this will do:
There is no need to generate a matrix. What I suggested was a pattern to iterate over the array. It doesn't use any extra space but the actual array and 2 further varibales of the given array type. Spoiler warning: I will show an implementation of this iteration pattern (that does not implement the array addition). I did it in c++, so this won't work in js without small adjustments. However I think the operations I use are all available in js since all of it is very basic. One last note: you can do this with bitmaps if they are available in the language of your choice and you will also not be limited by the size of the the variable (if the array is bigger than 65 elements, you will NEED a bitmap or you have to build one from an array).

//this loop goes from 0,0,...,0 to 1,1,...,1 by steps of 1 for (unsigned long long i = 1; i < (1<<size); ++i){ //this loop checks which bits are set at the moment for (int j=0; j < size; ++j){ if (i & (1<<j) { //do something with arr[j] } } }

mike0809

answered on 07/10/14

0

I know this is late but this is a very famous problem called Subset Sum Problem. Understanding the recursion way of solving the problem was great but its also important to understand how to do it without recursion.
These youtube videos helped me understand:
www.youtube.com/watch?v=s6FhG--P7z0
www.youtube.com/watch?v=hi-Ec4jYyII

danielyaa5

answered on 06/13/15

0

Is there a way to use a similar model but have it be 'full-proof'? I really just want to engrave a method to run through every array element w/ recursion, checking for each possible combo - that can be applied to other problems as well.
The concept I'm thinking is (after assigning var largest and setting a new array with largest # removed) is some kind of pattern testing: ie;
try index 0 + index 1, try index 0 + index 2, try index 0 + index 3, try index 0+index1+index2, try index 0+index2+index3.
Then change starting index to go through the pattern again until starting index = last index. For every 'try' there will be a (test==largest) check. Just need to figure out how to build this pattern test...
Does this make sense or am I making it more complicated than it needs to be?

lumberjack87

answered on 06/18/14

0

When you you have the array sorted and the largest number assigned.
you can create a temporary array by picking all numbers that are not equal to your largest number and insert into the new array.
Then go through that array, and for every entry in the temporary array, go through your temporary array and do your math, if it equals the largest number you can return true.

Juksefantomet

answered on 06/18/14

0

Thanks for the answer Matt.
- Okay I get randomIndex. It randomly picks an array position.
- randNum gets assigned the number at the randomly picked Index.
- that number gets pushed to tempArr
Here's where I'm a little confused as far as next steps:
- I only understand recursion as calling the same function within a function so I'm a bit confused on how to make a fail case (or if I even set up the for loop/recusion right):

function tester(){ var tempArr = []; while(numArr.length > 0){ var randomIndex = Math.floor(Math.random()*numArr.length); var randNum = numArr.splice(randomIndex,1); tempArr.push(randNum); } for (var i =0; i<numArr.length; i++){ var foo+=tempArr[i]; if (foo == largest){return true;} else {tester();} }

lumberjack87

answered on 06/12/14

0

Ok, you're on the right track. Use tempArr in the for-loop because that one has our random numbers, numArr should be empty. Call the tester and the bottom the function, you have it in the for-loop. Something like this:

function tester(numArr){ var tempArr = []; while(numArr.length > 0){ var randomIndex = Math.floor(Math.random()*numArr.length); var randNum = numArr.splice(randomIndex,1); tempArr.push(randNum); } var sum = 0 for (var i =0; i<tempArr.length; i++){ sum +=tempArr[i]; if (sum == largest){return true;} } tester(); }To stop the recursion you can add a counter to stop return false and a certain count.

mattlarsh

answered on 06/12/14

0

Gotchya - okay sweet everything up to this point makes sense to me except creating a false statement. I keep calling max/exceeding the call stack becuase I don't see how to create an optimal counter. A working but technically incorrect fail case was just setting a var to a higher number and having the fail case come into effect after hitting that number (ie; 500) - but if the array is triple the size or regardless of size there's still a chance it won't hit the solution.

lumberjack87

answered on 06/16/14

0

Yeah, this solution only works because the arrays are so small.

mattlarsh

answered on 06/16/14

0

The easiest way for me was make the order of the array random many times. If numArr had our numbers this would give us the same array in random order:

var tempArr = []; while(numArr.length > 0){ var randomIndex = Math.floor(Math.random()*numArr.length); var randNum = numArr.splice(randomIndex,1); tempArr.push(randNum); }Then use a for loop to see if adding each number ever equaled the largest. Use recusion to do that many times. Does that make sense?

mattlarsh

answered on 06/11/14

Log in to write an answer.