Split X into Y and Z where Y = Z (NP-issue)

Ended up looking at Nondeterministic Polynomial-problems, and found this one:

Let X be a finite amount of positive integers. Example:

X = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}

Is it possible to split X up into two parts Y and Z in such a way that Y = Z?

Well, in the above example, this would be rather easy to state, as the sum of X is an odd number. However, a general algorithm finding this out, what would it consist?

We can easily test out if the outcome number is odd, so that will be the first test. If the sum is odd, then it won't be possible to split X with our requirements.

Next out will be to check if any number in X is over half the sum of X. If it is, then it won't be possible to split X with our requirements.

Next step here would then be to check if i numbers equal to half the sum of X, starting from 1, incrementing by 1 until i is over half of the amount of numbers in X. While we do this, we check if all the solutions are over half the sum of X (if it is, then sorry, no solution).

So, any faster solution than this (or anything else that should be done)?

I'm kinda tired as of right now, but I was thinking about something like checking if all the solutions are under a certain value, but I couldn't get a firm grip on that thought.

Are all the integers in set X explicitly/assumed to be sorted in ascending order?

What I'm about to say assumes the above is true.

Next step here would then be to check if i numbers equal to half the sum of X, starting from 1, incrementing by 1 until i is over half of the amount of numbers in X. While we do this, we check if all the solutions are over half the sum of X (if it is, then sorry, no solution).

Two interpretations...

1.) If I'm understanding this correctly, you're adding the sum of the numbers in indexes [i-j] (i through j inclusive), where the sum of the numbers in indexes [i-(j-1)] < Sum(X) / 2, and seeing if this is over Sum(X) / 2.

Counter-proof: X = { 1, 5, 5, 7, 7, 15, 30 }

2.) You're adding the sum of the numbers in indexes [i-j], where j - i = over half the elements in set X, and you're checking if the sum of the numbers in indexes [i-j] are higher than Sum(X) / 2.

Counter-proof: X = { a, a }

(yeah that was lame xD)

With the initial assumption, it seems you only really need to check one solution.

Well, somewhat. If I increment the amount of number in index [i] from 1 to 2, then I have to decrement the amount of numbers in index[j] from x to 1-x. And since when i'm over half the amount of numbers, I will just stop, because I've already tested if the other half of the numbers equal to half of the sum.

If you split it into two groups A and B

Then you can calculate the change in sums by swapping any pair of numbers from 1 to the other set (or just by moving a small number from 1 set to the other). If you find the swap that puts it closest to Y = Z then you'd converge to an almost-solution pretty quickly.

When there are no swaps that put it closer to equal, then you'd extend the number of swaps up to the number of elements in each set 1 at a time looking for a closer solution. (eg. 1 from set A, 2 from set B, then 2 from set A, 1 from set B)
If you get up to swapping 1/2 the elements from each set you know it's not possible, similar reasoning to yours (swapping more than half of each set is the same as swapping the other smaller half)


I think this is better than your way since instead of going to permutations on 1/2 the numbers in X, you go to permutations on two halves. Which if I remember right permutations are factorial growth so cutting the limit in half and then multiplying the product is good. (8!8! < 16!)

Changing your set so it would theoretically have a split
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 36
Split halfway (faster would be to add items to set A until it's >= 1/2 the total)
2 3 5 7 11 13 (41) | 17 19 23 29 31 36 (155)
Moving 36 from set 2 to set 1 changes it toward the middle [98] the best
2 3 5 7 11 13 36 (77) | 17 19 23 29 31 (119)
Moving 19 from set 2 to set 1 changes it toward the middle the best
2 3 5 7 11 13 19 36 (96) | 17 23 29 31 (100)
Moving 2 from set 1 to set 2 makes them match
3 5 7 11 13 19 36 (98) | 2 17 23 29 31 (98)

This should improve find times on sets with a solution, and not end up any worse on sets without one.. dunno how much that helps.

Artificial example that won't solve just by moving single numbers
80 17 (97) | 83 20 (103)
No single movement gets closer to 100...
Swapping 17 & 20 though...
80 20 (100) | 83 17 (100)


I guess this is variation on the backpack problem.. how do you put as many items in the backpack as possible if they have fixed size {S}

Oh yeah, KajitiSouls, you can just sort them in order and manipulate the list how you'd like to, as long you get the right answer.

And Stereo, nice one.
Then, first of all, find the sum of all the numbers. If odd, quit. Then find the half of the sum.
(Then, I'd check for a number higher than X/2.)
From that, say the list is sorted in ascending order. We can either put every second number in each list, or we can put all numbers in a list until sum of list >= X/2.
Then swap and move as you suggested. However, when do you prove it's not possible to set the list?

And what's faster? Every second number, or all numbers in a list until sum of list >= X/2?

Then swap and move as you suggested. However, when do you prove it's not possible to set the list?

I'm not quite sure...

If you test up to half the elements in 1 set, switched with from 1 to all the elements in the other, you cover everything. But I'd guess that's more than you need to actually check.

I'm just not sure where that can be decreased, or how to get to it most efficiently.

I mean if you're (for example) only 3 away from equal piles, you'd need a trade that adjusts the difference to become lower.

So if one set to trade is {23, 3}=26 and the other is {7, 13}=20 and you want the first set to be 3 smaller than the second, you would only have a limited range to hit (27-31), thus adding (7 to 11) into the 2nd set, and then you'd try a new set. So if the remaining items in set B don't have any < 12, you could step back (ie. remove 13 from the set) and try {7, 16} from the 2nd set, or whatever is next.

If you have the items in set B in a specific order (eg. 7, 13, 16, 28) then you only have to test combos involving items further along. So from {7} you would add 13, 16, or 18. Then from {13} you can add 16 or 18. etc. Looking for a minimum value is easier if they're in increasing order (since you only have to check the next element, if B(i+1) > 12 then B(i+2),...B(n) are all > 12