Need help finding an algorithm

[IHateMyJob2004]

This also sounds liek a problem that people think is in a book. It's not. Imagine the numbers on sheets of paper in front of you. What procedure would you use to do this?

It's kinda like sorting. I "discovered" merge sort in 8th grade jsut doing code on my own. Didn't know it had a name till I went to college.

 

[ed21x]

 

[fleshconsumed]

If the simplest of the simplest of all algorithms is implemented, i.e. the brute search as I outlined, you will simply run out of computational power, it's not a problem of memory, it's time needed to do all the calculations. If you have 1000 numbers to check you will need to check 2^999-1 combinations to check, that is 5.35*10^300 combinations. No CPU will be able to handle that.

Now your solution as I understand it may not actually work because it will miss possible combinations. For example if you have following numbers 9, -3, -6 , -9 you can cancel -9 and 9, but then you will miss 9 -3 -6 branch of the the solution. Unless of course you will find a way to handle that, but in that case I'm guessing it won't be any different from brute search.

 

[AkumaX]

I was honestly thinking of brute force in my head. The max amount of #'s would probably be around 100. So 2^100-1? I was hoping that a Core 2 Duo @ 3.0ghz w/ 2gb of DDR2-800 would be able to do it, hahaha

 

[IHateMyJob2004]

Originally posted by: fleshconsumed
If the simplest of the simplest of all algorithms is implemented, i.e. the brute search as I outlined, you will simply run out of computational power, it's not a problem of memory, it's time needed to do all the calculations. If you have 1000 numbers to check you will need to check 2^999-1 combinations to check, that is 5.35*10^300 combinations. No CPU will be able to handle that.

Now your solution as I understand it may not actually work because it will miss possible combinations. For example if you have following numbers 9, -3, -6 , -9 you can cancel -9 and 9, but then you will miss 9 -3 -6 branch of the the solution. Unless of course you will find a way to handle that, but in that case I'm guessing it won't be any different from brute search.

With proper test cases up front, this would be resolved during code. Hopefully it was thoguht about during the desing phase.

Could we use a GPU? Muliple CPUs over a network?

is thiss systems engineering problem of stricly software?

 

[IHateMyJob2004]

K, seriously... bed .. g'night.

This is doable, just think about how you would do it and don't think about ideas you've read in books. Think for yourself.

Still convinced this is a question Google would ask.

 

[fleshconsumed]

Like I said I do not think you can brute force this problem even with multiple CPUs because with each additional digit your problem grows by a factor of 2. Remember tale where the guy asked a penny for first nail in the horseshoe, 2 for the second, 4 for the third, 8 for the fourth?

GPUs? Another can of worms, never worked with it, you'll have to use nVidia API and I have no idea how hard would that be.

I wonder if you can reuse computations from bruteforce algorithm, that would probably greatly simplify the problem.


BTW, we need programming forum...

 

[AkumaX]

Originally posted by: IHateMyJob2004
K, seriously... bed .. g'night.

This is doable, just think about how you would do it and don't think about ideas you've read in books. Think for yourself.

Still convinced this is a question Google would ask.

Haha, seriously, I appreciate your help

This is a problem for an accountant. What they do is stare at these dozens of positive and negative numbers and 'zero' them out.

It would be a nice google question...

I would be writing up this code in C# btw

en.wikipedia.org/wiki/Pascal's_triangle

 

[Chronoshock]

The problem is provably in NP. This can be done through a polynomial time reduction to PCP (post correspondence problem). For a list of n numbers, create n(n-1) tiles, one for each number n_i with number n_j where i != j (and you can have n_i on top and n_j on the bottom or the other way around, hence n*(n-1)/2 *2 = n*(n-1)). Mark each tile with the numbers n_i and n_j encoded in unary.

More obviously, this problem is a variant of Subset Sum, another problem in NP (NP-Complete in fact).

The only currently known algorithm which can solve PCP takes time O(n^k). If you believe it can be done faster, feel free to write a proof.

 

[esun]

#!/usr/bin/perl

use Math::Combinatorics;

my @nums = qw(-10 -8 -12 7 5 4 3 1 9);

for my $i (0..@nums-1) {
    for my $j (1..@nums) {
	my $combinat = Math::Combinatorics->new(
						count => $j,
						data => [@nums[1..$#nums]]
						);
	while (my @combo = $combinat->next_combination) {
	    if (sum(@combo) == $nums[0]) {
		print $nums[0] . " = " . join(" + ", @combo);
		print "\n";
	    }
	}
    }
    @nums = rotate(@nums);
}

sub sum {
  my $sum = 0;
  foreach my $i (@_){
    $sum += $i if $i == int($i);
  }
  return $sum;
}

sub rotate {
    my @array = @_;
    return (@array[1..$#array], $array[0]);
}

Brute force method in Perl. You'll need the Math::Combinatorics package from CPAN.

On your data set: -10, -8, -12, 7, 5, 4, 3, 1, 9

It produces:

-10 = 3 + -12 + -8 + 7
-10 = -12 + -8 + 1 + 9
-10 = -12 + 5 + 4 + 1 + -8
-8 = 4 + -12
-8 = 1 + 3 + -12
-8 = 5 + 9 + -12 + -10
-8 = 7 + -10 + 4 + -12 + 3
-8 = -10 + 9 + 4 + 1 + -12
-12 = -8 + -10 + 5 + 1
7 = 4 + 3
7 = -10 + 3 + 9 + 5
7 = 1 + -8 + 9 + 5
7 = 4 + 1 + 3 + 9 + -10
7 = 4 + 1 + 9 + -12 + 5
5 = 4 + 1
5 = -8 + 9 + 4
5 = -8 + 3 + 9 + 1
5 = 9 + -12 + 7 + 1
5 = 3 + 1 + 9 + 4 + -12
5 = 3 + 1 + -10 + 4 + 7
5 = 7 + 3 + -8 + 9 + -10 + 4
4 = 1 + 3
4 = -12 + 7 + 9
4 = -8 + 5 + 7
4 = -8 + 3 + 9
4 = 5 + -10 + 9
4 = 1 + -12 + 3 + 7 + 5
4 = 5 + 3 + -12 + 9 + 7 + -8
4 = 5 + 1 + 9 + -10 + 7 + -8
3 = 7 + -8 + 4
3 = 9 + -10 + 4
3 = 7 + 1 + -10 + 5
3 = 9 + 1 + -12 + 5
3 = 9 + -8 + -10 + 5 + 7
3 = 4 + 1 + 9 + 7 + -10 + -8
3 = 4 + 9 + 7 + -10 + -12 + 5
1 = -8 + 9
1 = 5 + -8 + 4
1 = 7 + -10 + 4
1 = -12 + 9 + 4
1 = -10 + -8 + 9 + 7 + 3
1 = -8 + 5 + 9 + -12 + 7
1 = 4 + 3 + -10 + 9 + -12 + 7
1 = 4 + 3 + -10 + -8 + 5 + 7
1 = 4 + 3 + 9 + -8 + 5 + -12
9 = 4 + 5
9 = 5 + 3 + 1
9 = -8 + 7 + 4 + 1 + 5
9 = 7 + 4 + -10 + 3 + 5


EDIT: No code tag...if you paste it into Emacs and use the indent every line feature it'll show up nicely.

 

[LS20]

an accountant would ask something silly like that. think like a scientist and question what is the greater purpose behind it.. other than the novelty of finding 0-sum pairs

 

[Madwand1]

Originally posted by: Chronoshock
The problem is provably in NP. This can be done through a polynomial time reduction to PCP (post correspondence problem). For a list of n numbers, create n(n-1) tiles, one for each number n_i with number n_j where i != j (and you can have n_i on top and n_j on the bottom or the other way around, hence n*(n-1)/2 *2 = n*(n-1)). Mark each tile with the numbers n_i and n_j encoded in unary.

More obviously, this problem is a variant of Subset Sum, another problem in NP (NP-Complete in fact).

The only currently known algorithm which can solve PCP takes time O(n^k). If you believe it can be done faster, feel free to write a proof.

Well, it's hard to argue that this problem isn't like Subset Sum...

Here's a proof that Subset Sum is NP-Complete:

http://www.student.cs.uwaterloo.ca/~cs341/Old_courses/W03/section1/Unit28.pdf

(NP-Complete very roughly means that the problem takes a very very long time to solve for large data sets using any known algorithm.)