Talk:Partition problem

Hard instances

The section on Hard Instances uses the variable "m" but does not explain to what the variable refers. Presumably, it is talking about the problem of n numbers from 1 to m, but it is not clear.

This was later clarified in the 8 June 2011 edit. Joule36e5 (talk) 23:15, 19 September 2018 (UTC)

Bug?

The pseudo-polynomial algorithm function find_partition( S ) does not seem to work when S={1}.

I disagree. It initializes the top (and only) row to True, executes the outer loop zero times, and finally checks P(0, 1) and returns True, which is the correct answer. Joule36e5 (talk) 23:07, 19 September 2018 (UTC)

Equally hard problem?

Can any of you mathematical wizards out there tell me if this problem is equivalent or equally hard? My 4th grade daughter had this question for some bizarre reason in her science class:

Given three sets:

A = {4, 5, 7, 9, 1} B = {5, 5, 3, 3, 1} C = {2, 10, 6, 8, 3}

Can you exchange one number from each set with a number from a different set so that the sum of the numbers in each set is equal? — Preceding unsigned comment added by 108.227.230.4 (talk) 12:07, 28 October 2013 (UTC)

The problems are similar, but your problem is much easier because of the restriction that only one element (or two...) may be exchanged, which drastically reduces the number of possibilities to consider. However, you problem is ill posed in two ways: First, if B is really a set, then B = {1, 3, 5}. (A set is defined by specifying which object belongs to the set and which does not: Two sets are equal, B = B', iff ∀x:(x∈B ⇔ x∈B'). An object x cannot belong "twice" to a set.)

Second problem: given 3 sets, it's impossible to exchange exactly one element of each set with one element from a different set: Assume you exchange one element from A with one element from B. Then you have no partner left with whom C could exchange an element, else this partner (either A or B) would have exchanged *two* elements with other sets. So strictly speaking the answer would be no.

But let's ignore that for the moment. If we make exchanges, the total sum remains the same. So, if the sum of the numbers in each set is the same for all three, it must be one third of the total sum, or equivalently, the mean value of the 3 sums 26, 17 and 29, which is 72/3 = 24. (Here I consider that B's elements add up to 1+3+3+5+5 = 17 and not 1+3+5 = 9, in which case the average would not be an integer and therefore again no solution possible.)

So during the exchanges, the set A must lose 2 points and C must lose 5 points. (Also, B must win 7 points, but since the total sum remains the same, we can be sure that if A and C have the correct sum, this will be true for B, without further check; and indeed, 2+5 = 7.) It's easy to see that this is satisfied if C exchanges its 10 with one 5 of B (or its 8 with a 3, or its 6 with the 1), and A exchanges its 5 with a 3 from B (or its 7 with a 5 from B). Now in this solution, B exchanges 2 elements, one with A and one with C (unless it gives its 5 to C and takes a 5 from A: then it has received a 10 and given away a 3, but not exchanged these with the same partner; one could see this as a circular exchange with a 5 going from A to C). Now it's up to you to decide whether these solutions are compatible with the statement of the exercice.

If not, maybe you'd prefer a solution where each set exchanges one element with each of the other sets. In order to get a loss of -5 for C, we can also lose 3 against B (exchanging 8 against 5, or 6 against 3) and lose 2 against A (exchanging 6 against 4, or 3 against 1). Then, A has won 2 and must now lose 4 against B, e.g., exchanging its 5 against B's 1, or its 7 against a 3, or its 9 against a 5 from B. — MFH:Talk 06:42, 18 April 2019 (UTC)

Differencing algorithm does not work?

If we have S={11, 10, 8, 7, 6} so differencing algorithm will be return 4 but right answer is 0. — Preceding unsigned comment added by 93.100.160.61 (talk) 13:38, 15 March 2014 (UTC)

It's a heuristic. It's not expected to always find the optimal answer. Joule36e5 (talk) 23:08, 19 September 2018 (UTC)

Frustrating fake code

The given "karmarkarKarpPartition" code is fake. Naming it like this, the author pretends doing phase 1 of the KK algorithm, but since no bookkeeping is done, there's no way to do phase 2, i.e., (re)construct the partition. It's totally trivial to replace the two largest elements of a list with their difference, for any programmer who knows sort(). Using a priority queue makes it look more sophisticated but isn't more efficient than using a multiset which would not require any initialization. Even a standard array with repeated sort() would do for the purpose of demonstration, and might be as efficient after all. The most offending aspect is that the author tries to show off with inexistent knowledge, insulting readers by "explaining" how to do a completely trivial thing, and leaving them wondering how they could then do the "reconstruction" phase 2, which is actually impossible with this bad implementation of phase 1. — MFH:Talk 05:30, 18 April 2019 (UTC)