Re^4: Divide array of integers into most similar value halves

[gone2015]

So... 2**100 is ~ 10**30. If the computer can try one combination in (just for the sake of argument) ~3 micro-secs, it can try ~ 10**13 combinations per annum. So a result may be expected in 10**17 years. Perhaps we should spend more on the hardware ?

Actually, it's not as bad as 2**n. 2**n - 1 is the number of different combinations of n things. However, we have two partitions, A & B, and there is some symmetry, which reduces the number of combinations.

Consider: there are n possible partition A's containing 1 number -- but this is the same arrangement as the n possible partition A's containing n-1 numbers (but with A & B exchanged). So we don't count both of A with 1 number and A with n-1 numbers, and we don't count both A with 2 numbers and A with n-2 numbers, and so on.

The effect of this is to halve the number of possible arrangements[1].

Also: we can discount the 1 possible partition A with all the numbers in it.

Phew. We only have wait half the time we expected. There, that's made a difference :-)

Mind you, we're not taking into account the doubling of processor speed every 18 months or so. Which makes this sort of problem a kind of inverted Xeno's paradox. Let me see, if in 18 months I can buy a machine that will do twice as much work as the one I have: in 36 months time I can have done the same amount of work by waiting 18 months, and starting then with the faster machine. Also, that machine will be cheaper than one I can buy now ! Of course, in 36 months time I will be able to buy an even cheaper machine which is four times as fast. For maximum efficiency, it is clear: I should do nothing, indefinitely !

[1] If n is odd, the number of distinct partitions is exactly 2**(n-1) - 1.
If n is even it's a bit trickier to work out, you have to add (1/2) * (n!/(2*(n/2)!) to that.

[BrowserUk]

Could you discuss the effect of duplicates in the dataset? Is it as simple as making n = no of unique values?