in reply to Re: Divide array of integers into most similar value halves
in thread Divide array of integers into most similar value halves

My lists are not really big. Almost never bigger than 100.
  • Comment on Re^2: Divide array of integers into most similar value halves

Replies are listed 'Best First'.
Re^3: Divide array of integers into most similar value halves
by moritz (Cardinal) on Sep 01, 2008 at 19:56 UTC
    For a problem with complexity O(2**$n) a value of $n == 100 is enough to make your computer work until either he or your dies. That's why I asked if an approximation is enough.
[reply]
[d/l]
[select]

      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.

[reply]
[reply]
      An approximation is more than enough. Actually i could skip the big lists and do it only with lists with less than 10 numbers, if that would help.
      The real motivation for the problem (sorry for not explaining before) is that I need both subarrays to have a sum over a not-so-big threshold (easily achieved with 2 or 3 numbers per array). So if the big array is really big I can assume that the two small ones will pass the threshold.

      Thanks for your help.
[reply]
      I'm pretty sure the brute force method (find all divisions of all permutations) is O(N3), much better than O(2N)
[reply]
        Would you care to elaborate? I admit that I only picked up the "NP complete" that Skeeve mentioned earlier.

        On thinking a bit more it seems that the problem is roughly equivalent with calculating the sum of each item of the power set, which is O(2**N), and I see no obvious way to reduce that to O(N**3).

[reply]

In Section Seekers of Perl Wisdom