Nice problem! I tried to find an algorithm that would solve the general case with arbitrarily many digits, some of them equal. Here's what I ended up with:
def maximize_product(m, n, digits):
if m < 1 or n < 1 or m + n != len(digits):
raise Exception
flipped = m > n
if flipped:
m, n = n, m
digits = sorted(digits)
a, b = [], []
while len(a) < m:
a.append(digits.pop())
b.append(digits.pop())
if a[-1] != b[-1]:
break
while len(a) < m:
b.append(digits.pop())
a.append(digits.pop())
while len(b) < n:
b.append(digits.pop())
if flipped:
a, b = b, a
return a, b
print maximize_product(3, 2, [8, 4, 2, 7, 5])
I think I have a proof that it gives the right answer, but won't spell it out here.
My code runs in O(n log n) time and can deal with repeated digits. You converted it to something that takes exponential time and chokes on repeated digits.
(BTW, I just realized that my code can be made O(n), by replacing the default sort with a counting sort :-))
Hm, embarrassing, I just assumed you were doing the naive brute force. You're de-interleaving the digits with an order swap when the digits first start to differ.
It's nice to have this version for testing the faster, more complicated one from OP. I can attest that they indeed produce the same answers.
Two fixes:
- If you use `(Counter(digits)-Counter(e)).elements()` in the last line, you can support repeated digits.
- Reduce is `reduce(function, sequence[, initial]) -> value` so you should move the lambda to the first argument.
All in all I think this is a very nice, succinct use of Python. The combinatorial parts of `itertools` are extreamly handy :)
I don't mean this as a criticism -- as you are absolutely correct, your code does cut out a lot of the boilerplate and makes for a more compact function -- but I vastly prefer @cousin_it's function to yours in terms of readability. I think Python is a very pretty language but I always have a hard time reading Python code when it's heavy on the functional paradigms.
