Need help finding an algorithm

[AkumaX]

suppose you have a set of numbers,

-10, -8, -12, 7, 5, 4, 3, 1, 9

when you add them all up, you get -1

but what i need to find are how you can reduce the amount of #'s you have to add by zero-ing out stuff, such as:

-8 cancels with 4, 3, 1
-12 cancels with 7, 5

so all that's left is -10 and 9

how would i figure out "the zeroes"? thanks (its for a friend)

 

[potoba]

adding them up is the fastest way, i think.

 

[randomint]

how the heck would you know that it "cancels out" if you don't add the numbers. for example, unless you add 4 + 3 + 1 you wouldn't know that it cancels with 8! so you have to add regardless

 

[brandonbull]

Unless you are using a Commodore 64 and need to compare millions of numbers, I think brute force should do fine with modern PCs.

 

[ebaycj]

initial reaction: Design one your damn self, it doesn't seem like that hard of a problem.

secondary reaction: It would not make sense to do this on a computer anyway. You have to do more operations to figure out which ones cancel out, than you do to just add them all up. The only reason I can think to do something like this would be if you need to present the fewest number of charges in a human-readable format (an itemized bill, for example).

tertiary reaction: your problem is not well defined enough, because "the zeros" does not describe a single set of subsets of your array.
example:

-10, -8, -12, 7, 5, 4, 3, 1, 9

-8 could be offset by 4+3+1. Or it could be offset by 7+1. Or by 5+3. Who is to say which one is "correct"? Get my meaning?

 

[AkumaX]

im looking for an algorithm that i could use so that i could write a program that finds "zeroes"

here's a snippet of numbers:

21,425.80
17,940.00
10,336.99
7,864.11
7,048.54
776.22
(825.00)
(2,009.50)
(3,244.46)
(4,976.54)
(7,178.54)

 

[ebaycj]

Originally posted by: AkumaX
im looking for an algorithm that i could use so that i could write a program that finds "zeroes"

here's a snippet of numbers:

21,425.80
17,940.00
10,336.99
7,864.11
7,048.54
776.22
(825.00)
(2,009.50)
(3,244.46)
(4,976.54)
(7,178.54)

The real question is WHY are you trying to find "zeroes" ? If you are interested in the total amount, why not just add them all up and be done with it?

 

[AkumaX]

Originally posted by: ebaycj

Originally posted by: AkumaX
im looking for an algorithm that i could use so that i could write a program that finds "zeroes"

here's a snippet of numbers:

21,425.80
17,940.00
10,336.99
7,864.11
7,048.54
776.22
(825.00)
(2,009.50)
(3,244.46)
(4,976.54)
(7,178.54)

The real question is WHY are you trying to find "zeroes" ? If you are interested in the total amount, why not just add them all up and be done with it?

that's what the job wants. I have no idea...

anyways, the list is about 100 numbers and ranges anywhere between +1,000,000 to -1,000,000. brute force is fine, i just need a headstart

 

[brandonbull]

Kind of sounds like in some way to be a dynamic path finding/optimization problem.

The "Stage Coach Problem"

 

[dartworth]

work the problem...

 

[Flammable]

is this a test to see if you're qualified for said job?

 

[brandonbull]

Sounds like a waste of time. Someone is trying to get fancy and or get a homework question answered.

 

[Cooler]

Sorting the numbers first may help.

 

[AkumaX]

Originally posted by: Flammable
is this a test to see if you're qualified for said job?

no, its not for me, its for someone else

that person has been on this job for a while (> 1 year), but just received this (extremely stupid) account.

 

[AkumaX]

Originally posted by: Cooler
Sorting the numbers first may help.

have sorted the numbers (easy in excel)

 

[handoverfist]

sounds like hw

 

[chuckywang]

Originally posted by: AkumaX
suppose you have a set of numbers,

-10, -8, -12, 7, 5, 4, 3, 1, 9

when you add them all up, you get -1

but what i need to find are how you can reduce the amount of #'s you have to add by zero-ing out stuff, such as:

-8 cancels with 4, 3, 1
-12 cancels with 7, 5

so all that's left is -10 and 9

how would i figure out "the zeroes"? thanks (its for a friend)

Create your own algorithm....this is not a hard problem.

 

[cheesecurd]

did you check in the couch cushions?

 

[fleshconsumed]

Sounds like a homework really. If the number of numbers you need to check is sufficiently large any modern computer will choke up and will never return an answer in reasonable amount of time. Say in your example you have 9 digits total, this means that in order to check all possible variations for a single number you will have to perform 2^8-1 computations. The general formula if you have a sequence of n numbers, for each number you will have to perform 2^(n-1)-1 number of additions to find any combinations that add up to zero through brute force. That's impossible on any computer. I really don't think it's a work assignment because work assignments like these are not given to a person who has been with company for only one year, on the other hand it does sound exactly like college homework algorithm. Look into intelligent searches such as A* searches, that's the only thing I can advice. However, even if I knew exactly how to solve this problem in an efficient manner (and I don't) I'd need at least a week for coding to present first workable draft that involves any of the intelligent searches.

 

[AkumaX]

Originally posted by: fleshconsumed
Sounds like a homework really. If the number of numbers you need to check is sufficiently large any modern computer will choke up and will never return an answer in reasonable amount of time. Say in your example you have 9 digits total, this means that in order to check all possible variations for a single number you will have to perform 2^8-1 computations. The general formula if you have a sequence of n numbers, for each number you will have to perform 2^(n-1)-1 number of additions to find any combinations that add up to zero through brute force. That's impossible on any computer. I really don't think it's a work assignment because work assignments like these are not given to a person who has been with company for only one year, on the other hand it does sound exactly like college homework algorithm. Look into intelligent searches such as A* searches, that's the only thing I can advice. However, even if I knew exactly how to solve this problem in an efficient manner (and I don't) I'd need at least a week for coding to present first workable draft that involves any of the intelligent searches.

thanks for the insight. its giving me a better perspective of how to solve this problem. its still not a homework problem, and it really is a work problem. think bank transactions, dealing in the millions, and trying to zero out where errors occur.

if you had 9 digits, it would be something along the lines of:

array a[8] (0-8 = 9)
sum for each int n in a[]
P(n choose 9)

 

[IHateMyJob2004]

Isn't the problem that with a large set, you might have overflow problems if you jsut add everything together? Not a performance issue but an issue with overflows?

Use java and the BigInteger class and add the values together.... solved OK, that's the simple answer that works.

And the worst case scenerio would probably be numbers that don't find smaller sets that add to zero. Therefore, n osolution exists.

An actual idea:
I'd create two arrays to start. One to hold positive values. One for negative. I'd use a sorted array (SortedSet in Java).

Start by looking for matches (-9 and +9 cancel eachother out). Probably won't do much, but in larger sets, maybe).

.....................................
OK, I just thought more about this problem .... your F'ed. This almost sound liek a question Google would ask on an interview.

 

[IHateMyJob2004]

This just sounds like something that requiers brute force and recursion. But with big sets, ercursion will not work do to stack overflows (depending on programming language and other factors)

This is somethign I could figure out in a few hours ... I jsut don't feel like resolving it for you. Good luck.

 

[IHateMyJob2004]

take element one. Add it to element two. If it's zero, remove them from the original set.
If not, add element one and two to a red-black tree in some sort of data set. And place the result into the red black tree along with pointers to the values that make up the result. I'm saying pointers assuming C++ because with large data sets, it's would aid in performance.

So, you'd need a tree with elements like this:
int total
buildingElements *list[]

-----------------------
Better yet, you could take this concept a step farther by making things event driving (using hte observer pattern). So, whenever an value is elminated, any other objects in your tree that were dependant upon it would be notified and they would adjust their total values. You would need a custom tree to do this whcih will listen for changes to 'total' and resort automatically.

---------------------
Actually, I have the answer in my head, the above statements should lead one to water. I am stopping short of writing code, even though I thinkit is attainable via Java within a week. 2 weeks if you want JUnit tests to be written (before coding of course!). Then again, something liek this needs a solid design. Give me 2 weeks to design, a week to stub and write JUnit and another week to code.

C/C++ might be way faster though since it can use pointers directly. I'm rusty with C/C++ though. And it would take way logner especially if you want to do proper testing.

---------------------
Any harder problems?

EDIT: tired ..... spelling errors not to be fixed. And I re-read some of it. I really need to write a design doc to explain this idea well and that would be about 5-10 pages easily. Not worth the time that is needed, espcially on the interweb.

 

[fleshconsumed]

Brute force will not work with large numbers because with each additional number the problem grows by a factor of 2.

Say you have 3 numbers 3, 1, 9 and you want to check if any of the numbers cancel 3 ( so essentially you have to search in {1, 9} space ) which yields you following combinations: (1), (9) and (1+9). You have to perform 3 additions and then compare them to original number.

Now say you have 4 numbers: 4, 3, 1, 9 and you want to check if any of the numbers cancel 4 (so now you have to search {3,1,9} space ) which yields following combinations 1, 9, 1+9, 3, 3+1, 3+9, 3+1+9. Your problem just grew by a factor of 2.

This problem is not doable by brute force. Really. You need someone with extensive experience in AI to do this kind of job, or someone with a good head on his shoulders and a month or so of work.

 

[IHateMyJob2004]

Originally posted by: fleshconsumed
Brute force will not work with large numbers because with each additional number the problem grows by a factor of 2.

Say you have 3 numbers 3, 1, 9 and you want to check if any of the numbers cancel 3 ( so essentially you have to search in {1, 9} space ) which yields you following combinations: (1), (9) and (1+9). You have to perform 3 additions and then compare them to original number.

Now say you have 4 numbers: 4, 3, 1, 9 and you want to check if any of the numbers cancel 4 (so now you have to search {3,1,9} space ) which yields following combinations 1, 9, 1+9, 3, 3+1, 3+9, 3+1+9. Your problem just grew by a factor of 2.

This problem is not doable by brute force. Really. You need someone with extensive experience in AI to do this kind of job, or someone with a good head on his shoulders and a month or so of work.

It's doable. C/C++ would keep the memmory usage to a minimum, especially if pointers are used.

The problem doesn't look to bad. Now if were talking millions of numbers, that's an issue in itself. Thousand though? It's doable.

AI would do the trick though. I have a BSEE and never learned the topic well other than it's basic concepts.