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.

In reply to Re^4: Divide array of integers into most similar value halves by gone2015
in thread Divide array of integers into most similar value halves by Pepe

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.