Search example from "Problems every software developer should be able to solve in under an hour"

hour-problems.py

"""
From programming problems every software developer should be able to solve in
under an hour.

Given an array of integers find the largest integer they can be combined to
form.

for instance [50, 2, 1, 9, 62] would yield the answer 9625021

"""
a = [50, 2, 1, 9, 62, 999]

# ---- SOLUTION 1 --------
# The hard way(recursive) calculate all perms and store in a heap
from heapq import heappush
def get_rest(i, a):

    itm = a[i]

    left = a[0:i]
    right = a[i+1:len(a)]

    return (itm, right+left)

def recurse(a, number_so_far='', result=[]):
    if a == []:
        heappush(result, (int(number_so_far) * -1, int(number_so_far)))
        return result

    for idx, itm  in enumerate(a):
        selection, rest = get_rest(idx, a)
        num = number_so_far + str(selection)
        result = recurse(rest, num, result)

    return result

result = recurse(a)
priority, answer = result[0]
print answer

# ---- SOLUTION 2 --------
# The easy way convert to strings and sort lexically

print "".join(sorted([ str(item) for item in a ], reverse=True))