小练习：20160815 找出所有能写成 pandigital 数字乘积的数字之和

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

好了言归正传，我们开始做小练习。




题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即8.22 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

----除列出程序外，请给出输出的结果。----


题目：

如果一个 n 位数使用了 1 到 n 中每个数字且只使用了一次，我们称其为 pandigital。例如，15234 这个五位数，是 1 到 5 pandigital 的。

7254 是一个不寻常的数，因为：39 × 186 = 7254 这个算式的乘数，被乘数和乘积组成了一个1到 9 的 pandigital 组合。

找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。

提示: 有的乘积数字能够被多个乘法算式得到，所以在计算时要记得只计算它们一次。

冬雪雪冬

答案是：45228
我的思路是：
利用排列函数将1~9的排列列出，做循环。
下一步就是乘号放在哪里？
考虑了一下只有几个可能：
1位*4位=4位
2位*3位=4位
3位*3位=3位（犯了个低级错误，这个怎么能成立呢！，应该去掉！，程序先不改了，好在没影响最终的结果。）
（反过来的4位*1位，因排列时会出现与1位*4位相同的结果，故忽略，其他类似）
相同的乘积只计一次，所以用set来存放。

1. from time import time
   
2. from itertools import permutations
   
3. start = time()
   
4. data = permutations('123456789')
   
5. set1 = set()
   
6. for i in data:
   
7.     product = int(i[5] + i[6] + i[7] + i[8])
   
8.     if int(i[0]) * int(i[1] + i[2] + i[3] + i[4]) == product:
   
9.         set1.add(product)
   
10.     product = int(i[5] + i[6] + i[7] + i[8])
    
11.     if int(i[0] + i[1]) * int(i[2] + i[3] + i[4]) == product:
    
12.         set1.add(product)
    
13.     product = int(i[6] + i[7] + i[8])
    
14.     if int(i[0] + i[1] + i[2]) * int(i[3] + i[4] + i[5])== product:
    
15.         set1.add(product)
    
16. print(sum(set1))
    
17. print(time() - start)
    
18.               
    

复制代码

wangzhenas

答案： 45228
思路： 要求1-9的数字各出现一次，那么符合形式的乘法如下：
x * xxxx = xxxx
xx * xxx = xxxx
而xx * xx 不可能得到5位数，xxx * xxx 不可能得到3位数， 因此缩小了迭代法的范围

1. import time
   
2. t,num_s = time.time(),set()
   
3. 
   
4. for i in range(1,99):
   
5.     for j in range(1000//i,10000//i):
   
6.         s = str(i)+str(j)+str(i*j)
   
7.         if len(s)==9:
   
8.             s = set(s)
   
9.             if len(s)==9 and '0' not in s:
   
10.                 num_s.add(i*j)
    
11.                 print(i,j,i*j)
    
12.                
    
13. print(sum(num_s),time.time()-t)

复制代码

yanghua

好有意思的样子

飘飞的白杨

1. import itertools
   
2. list0 = []
   
3. def a(l):
   
4.     x1 = l[0]
   
5.     x2 = l[0]*10+l[1]
   
6.     y1 = l[1]*1000+l[2]*100+l[3]*10+l[4]
   
7.     y2 = l[2]*100+l[3]*10+l[4]
   
8.     z = l[5]*1000+l[6]*100+l[7]*10+l[8]
   
9.     if x1*y1 == z or x2*y2 == z:
   
10.         return z
    
11.     else:
    
12.         return False
    
13. for l in itertools.permutations([1,2,3,4,5,6,7,8,9],9):
    
14.     n =a(l)
    
15.     if n != False and n not in list0:
    
16.         list0.append(n)
    
17. print(sum(list0))
    

复制代码

答案：45228

bacon6581

1. from time import time
   
2. start=time()
   
3. 
   
4. a=set()
   
5. result=0
   
6. #用的是穷举法，即先获取每一个9位数，再去判断是否属于pandigital 组合
   
7. #P9取9 即9！=362880种取法
   
8. #第一位数字有9种取法（1-9）
   
9. #取出来的数字放在列表‘c’里（这时c里只有刚放进来的一个数字）
   
10. for i1 in range(0,9):
    
11.     b=[1,2,3,4,5,6,7,8,9]
    
12.     c=[]
    
13.     c.append(b.pop(i1))
    
14.     b1=b[:]
    
15.     c1=c[:]
    
16. #第二位数字有8种取法(第一位数字已取走的那个数字，就不能再取了)
    
17. #取出来的数字放在列表‘c’里（这时c里有两个数字了）
    
18.     for i2 in range(0,8):
    
19.         b=b1[:]
    
20.         c=c1[:]
    
21.         c.append(b.pop(i2))        
    
22.         b2=b[:]
    
23.         c2=c[:]
    
24. #第三位数字有7种取法(第一、二位数字已取走的那个数字，就不能再取了)
    
25. #取出来的数字放在列表‘c’里（这时c里有三个数字了）
    
26. #下同
    
27.         for i3 in range(0,7):
    
28.             b=b2[:]
    
29.             c=c2[:]
    
30.             c.append(b.pop(i3))
    
31.             b3=b[:]
    
32.             c3=c[:]
    
33.             for i4 in range(0,6):
    
34.                 b=b3[:]
    
35.                 c=c3[:]
    
36.                 c.append(b.pop(i4))
    
37.                 b4=b[:]
    
38.                 c4=c[:]
    
39.                 for i5 in range(0,5):
    
40.                     b=b4[:]
    
41.                     c=c4[:]
    
42.                     c.append(b.pop(i5))
    
43.                     b5=b[:]
    
44.                     c5=c[:]
    
45.                     for i6 in range(0,4):
    
46.                         b=b5[:]
    
47.                         c=c5[:]
    
48.                         c.append(b.pop(i6))
    
49.                         b6=b[:]
    
50.                         c6=c[:]
    
51.                         for i7 in range(0,3):
    
52.                             b=b6[:]
    
53.                             c=c6[:]
    
54.                             c.append(b.pop(i7))
    
55.                             b7=b[:]
    
56.                             c7=c[:]
    
57.                             for i8 in range(0,2):
    
58.                                 b=b7[:]
    
59.                                 c=c7[:]
    
60.                                 c.append(b.pop(i8))
    
61. #前面8个数字都确定了，那最后一位只有一种取法了：P1取1=1
    
62. #直接把剩余的一个数字，放入列表‘c’里边
    
63.                                 c.append(b[0])
    
64. #产生pandigital 组合的只可能会是以下4种情况：
    
65. #1位数 * 4位数 = 5位数
    
66. #2位数 * 3位数 = 5位数
    
67. #4位数 * 1位数 = 5位数
    
68. #3位数 * 2位数 = 5位数
    
69. #如果有123456789组合，则必有234516789组合
    
70. #即1*2345==5678（第一个组合的第一种判断） 与2345*1==5678（第二个组合的第3种判断）属重复判断
    
71. #故注释掉后两种判断
    
72. #判断成立，即该数值属pandigital 组合，并将结果放入集合'a'中（不用操心会有重复值）
    
73.                                 if(((c[0]*(c[1]*1000+c[2]*100+c[3]*10+c[4]))==c[5]*1000+c[6]*100+c[7]*10+c[8])
    
74.                                    or ((c[0]*10+c[1])*(c[2]*100+c[3]*10+c[4])==c[5]*1000+c[6]*100+c[7]*10+c[8])):
    
75.                                    #or ((c[0]*100+c[1]*10+c[2])*(c[3]*10+c[4])==c[5]*1000+c[6]*100+c[7]*10+c[8])
    
76.                                    #or ((c[0]*1000+c[1]*100+c[2]*10+c[3])*(c[4])==c[5]*1000+c[6]*100+c[7]*10+c[8])):
    
77.                                     a.add(c[5]*1000+c[6]*100+c[7]*10+c[8])
    
78. #将集合a里的所有数值累加一遍，即所求之结果！
    
79. for k in a:
    
80.     result+=k
    
81. print(result)
    
82. print(time()-start)
    

复制代码

1. >>> ================================ RESTART ================================
   
2. >>>
   
3. 45228
   
4. 22.254349946975708
   
5. >>> ================================ RESTART ================================
   
6. >>>
   
7. 45228
   
8. 15.573134183883667
   
9. >>>

复制代码

中文注释后加的，要是注释有报错，麻烦版主删掉再试！
注释掉两行，速度快了7秒

无下限HENTAI

1. #12*798为4位数，79*123为4位数
   
2. #范围为（12~79），（798~123）
   
3. import itertools as it
   
4. count = 0
   
5. a = list(it.permutations(range(1,10),3))
   
6. b = list(it.permutations(range(1,10),2))
   
7. for i in a:
   
8.     for j in b:
   
9.         if set(i) & set(j) == set():
   
10.             c = int(str(i[0])+str(i[1])+str(i[2]))
    
11.             d = int(str(j[0])+str(j[1]))
    
12.             if c <798 and d <79:
    
13.                 mult = c * d
    
14.                 if mult < 10000:
    
15.                     mult_str = str(mult)
    
16.                     mult_set = {int(mult_str[0]),int(mult_str[1]),int(mult_str[2]),int(mult_str[3])}
    
17.                     if 0 not in mult_set and len(mult_set) == 4:
    
18.                         union = set(i).union(set(j))
    
19.                         if union & mult_set == set():
    
20.                             count += 1
    
21.                             print('%d x %d = %d'%(c,d,mult))
    
22.             else:
    
23.                 continue
    
24. print('共有%d个这样的结果'%count)

复制代码

结果：
138 x 42 = 5796
157 x 28 = 4396
159 x 48 = 7632
186 x 39 = 7254
198 x 27 = 5346
297 x 18 = 5346
483 x 12 = 5796
共有7个这样的结果

无下限HENTAI

看错了，原来是求和的

1. import itertools as it
   
2. total = []
   
3. a = list(it.permutations(range(1,10),3))
   
4. b = list(it.permutations(range(1,10),2))
   
5. for i in a:
   
6.     for j in b:
   
7.         if set(i) & set(j) == set():
   
8.             c = int(str(i[0])+str(i[1])+str(i[2]))
   
9.             d = int(str(j[0])+str(j[1]))
   
10.             if c <798 and d <79:
    
11.                 mult = c * d
    
12.                 if mult < 10000:
    
13.                     mult_str = str(mult)
    
14.                     mult_set = {int(mult_str[0]),int(mult_str[1]),int(mult_str[2]),int(mult_str[3])}
    
15.                     if 0 not in mult_set and len(mult_set) == 4:
    
16.                         union = set(i).union(set(j))
    
17.                         if union & mult_set == set():
    
18.                             total.append(mult)
    
19. total_set = set(total)        
    
20. print('所有乘积的和是：%d'%sum(total_set))

复制代码

结果：
所有乘积的和是：30424

yyongl

有时候就盲目了，可能就标点错了也看不出来

老忘

思路：
1、要能够组合成 1 到 9 pandigital 的乘法算式，也就是说乘数、被乘数、积的位数之和必须要是9，要满足这一点，则只有1位数乘4位数、2位数乘3位数（重复的不考虑）二种情况。
2、分别从1-9中，按1-4位取出其pandigital数，存入对应列表，再按条件1进行判断。

开始采用从1到9999全部循环处理，36秒左右出结果，后改成用itertools模块取出1-4位的pandigital数再全部循环处理，14左右秒出结果，最后改成提交的这个版本，仅0.2秒左右出结果。所以在此不得不再次感叹一下，编程时的思路会影响程序效率，思路真的十分重要，要多想想啊！

1. # -*- coding:Utf-8 -*-
   
2. import itertools
   
3. import time
   
4. start = time.clock()
   
5. 
   
6. def check_pd(x):#检测是否为仅含1 到 9 的pandigital数，是返回1，否返回0
   
7.     for eachone in x:
   
8.         if  x.count(eachone)>1 or eachone=='0':
   
9.             return 0
   
10.     return 1
    
11. 
    
12. list_rel=[]
    
13. for i in range(1,5):
    
14.     locals()['list_'+str(i)]=[] #动态生成list_1、list_2、list_3、list_4的空列表，存放1 到 9 的分别取1-4位的pandigital数
    
15.     for each in list(itertools.permutations([1,2,3,4,5,6,7,8,9],i)):
    
16.         s=''
    
17.         for eachone in each:
    
18.             s=s+str(eachone)
    
19.         locals()['list_'+str(i)].append(int(s))
    
20. #要使乘数和积满足9位的pandigital数，只能是1位数乘4位数或者2位数乘3位数二种情况
    
21. for i in range(1,3):
    
22.     for each in locals()['list_'+str(i)]:
    
23.         for eachone in locals()['list_'+str(5-i)]:
    
24.             if len(str(each)+str(eachone)+str(each*eachone))==9 and  check_pd(str(each)+str(eachone)+str(each*eachone)) and (each*eachone not in list_rel):
    
25.                 list_rel.append(each*eachone)
    
26. 
    
27. print(sum(list_rel))
    
28. 
    
29. end = time.clock()
    
30. print ("read: %f s" % (end - start))

复制代码

计算结果：

1. 45228

复制代码

mather

1. s = [1,2,3,4,5,6,7,8,9]
   
2. 
   
3. def be_nums(j):#定义一个可以将组合变换为数字的函数
   
4.     res = 0
   
5.     for ji in j:
   
6.         res = res*10 + ji
   
7.     return res
   
8. #可能的情况是1位乘4位等于4位
   
9. #或者2位乘3位等于4位的情况
   
10. product = set()
    
11. import itertools
    
12. #先求1位乘4位的，再求2位乘4位的
    
13. for i in range(2,10):
    
14.     #不可能是1乘的所以只计算2以上的乘
    
15.     for j in itertools.permutations([x for x in s if x!=i],4):
    
16.         temp = be_nums(j)
    
17.         may_product = i*temp
    
18.         if (may_product)//10000>0:
    
19.             break#直接跳出内层循环？不知道有没有问题
    
20.         sets = set(j)
    
21.         sets.add(i)
    
22.         is_break = False
    
23.         while may_product>0:
    
24.             te = may_product%10
    
25.             if  te==0 or te in sets:
    
26.                 is_break = True
    
27.                 break
    
28.             else:
    
29.                 sets.add(te)
    
30.                 may_product = may_product//10
    
31.         if (not is_break) and (len(sets)==9):
    
32.             product.add(i*temp)
    
33. for i in itertools.permutations(s,2):
    
34.     #2位乘3位的
    
35.     temp1 = be_nums(i)
    
36.     for j in itertools.permutations([x for x in s if x not in i],3):
    
37.         temp2 = be_nums(j)
    
38.         may_product = temp1*temp2
    
39.         if (may_product)//10000>0:
    
40.             break
    
41.         sets = set(list(i)+list(j))
    
42.         is_break = False
    
43.         while may_product>0:
    
44.             te = may_product%10
    
45.             if te==0 or te in sets:
    
46.                 is_break = True
    
47.                 break
    
48.             else:
    
49.                 sets.add(te)
    
50.                 may_product = may_product//10
    
51.         if (not is_break) and (len(sets)==9):
    
52.             product.add(temp1*temp2)
    
53. print(product)
    
54. print(sum(product))

复制代码

结果：{5346, 5796, 6952, 7852, 4396, 7632, 7254}
45228

过河的小卒

1. def func():
   
2.     l1 = []
   
3.     k = 0
   
4.     for i in range(1000,10000):
   
5.         if len(set(str(i))) == 4 and '0' not in str(i):
   
6.             for j in range(1,100):
   
7.                 if i%j == 0:
   
8.                     if len(set(str(i)+str(j)+str(i//j))) == 9:
   
9.                         l1.append(i)
   
10.                         break
    
11.     return l1
    
12. list1 = func()
    
13. print(list1,'\n',sum(list1))
    

复制代码

输出：
[3876, 4396, 4827, 5278, 5346, 5427, 5724, 5796, 6158, 6174, 6372, 6952, 7236, 7254, 7362, 7452, 7632, 7638, 7852, 7854, 8156, 8316, 8463]
151541
所以结果为151541

过河的小卒

过河的小卒 发表于 2016-8-21 17:40
输出：
[3876, 4396, 4827, 5278, 5346, 5427, 5724, 5796, 6158, 6174, 6372, 6952, 7236, 7254, 7362, ...

哎，没考虑i//j得到的数中是否包含0
改进后：

1. def func():
   
2.     l1 = []
   
3.     k = 0
   
4.     for i in range(1000,10000):
   
5.         if len(set(str(i))) == 4 and '0' not in str(i):
   
6.             for j in range(1,100):
   
7.                 if i%j == 0:
   
8.                     if len(set(str(i)+str(j)+str(i//j))) == 9:
   
9.                         if '0' not in str(i//j):
   
10.                             l1.append(i)
    
11.                             print(i,j,i//j)
    
12.                             break
    
13.     return l1
    
14. list1 = func()
    
15. print(list1,'\n',sum(list1))

复制代码

输出：
4396 28 157
5346 18 297
5796 12 483
6952 4 1738
7254 39 186
7632 48 159
7852 4 1963
[4396, 5346, 5796, 6952, 7254, 7632, 7852]
45228
这下对了
貌似我的代码行数最少