Problem 32

Problem 32

06 December 2002

The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
    

def fun32():
    s = range(1, 10)
    result = []
    for i in permutation(s, 9):
        t = "".join(map(str, i))
        (a, b, c) = map(int, [t[0], t[1:5], t[5:]])
        if b < c and a*b == c:
            print a, b, c
            result.append(c)
        (a, b, c) = map(int, [t[0:2], t[2:5], t[5:]])
        if a*b == c:
            print a, b, c
            result.append(c)
    return reduce(add, set(result))

直接遍历所有的1-9的排列进行判断，获取排列函数permutation为    

def permutation(s, n):
    #从s中选取n进行排列
    if (n > len(s)) or (n <= 0) or (len(s) == 0):
        return
       
    if n == 1:
        for i in range(len(s)):
            yield [s[i]]
    else:
        for i in s:
            #print i, len(s), r
            st = list(s)
            st.remove(i)
            for j in permutation(st, n-1):
                yield [i] + j

  
answer is 45228
time:13.6879999638, 花费时间太长了

我们可以判断出a*b=c的c只能是4或5位数，这样我们只遍历[1-9]组成的4或5位数，可以减少计算量。