python小练习（005）：2个整数列表的均布

jerryxjr1220

刚才的小练习说太简单了，传送门，那么就加试一题。

这题据说是华为公司的面试题，争取10分钟内完成。

假设有2个列表a和b，都是由任意整数构成，无序，例如a=[1,3,5,7,9], b=[2,4,6,8,10] (假设a与b长度相等，有能力可以做加分题：a与b长度不相等）

现在要求可以任意交换a与b中的项（使原始a列和b列长度不变），使新的列表a的和 与 新的列表b的和 之间的差距最小。
例如，新的a=[1,10,3,8,5], 新的b=[2,9,4,7,6]

jerryxjr1220

动态规划解法

1. import random as r
   
2. a=[r.randint(1,100) for i in range(100)]
   
3. b=[r.randint(1,100) for i in range(100)]
   
4. a.sort()
   
5. b.sort()
   
6. newa=[a.pop()]
   
7. newb=[b.pop()]
   
8. while len(a)>0:
   
9.   c=a.pop()
   
10.   d=b.pop()
    
11.   if sum(newa)>sum(newb):
    
12.     newa.append(min(c,d))
    
13.     newb.append(max(c,d))
    
14.   else:
    
15.     newa.append(max(c,d))
    
16.     newb.append(min(c,d))
    
17. print (sum(newa),sum(newb))

复制代码

没有进行合并排序，怕列表很长会影响效率，结果其实是差不多的。

冬雪雪冬

不知我理解的对不对。

1. import itertools
   
2. a=[1,3,5,7,9]
   
3. b=[2,4,6,8,10]
   
4. c = a + b
   
5. min1 = sum(c)
   
6. for i in itertools.combinations(c, len(a)):
   
7.     if abs(sum(i) - sum(c) // 2) < min1:
   
8.         min1 = abs(sum(i) - sum(c) // 2)
   
9.         a = i
   
10. print('a = ', list(a))
    
11. print('b = ', list(set(c) - set(a)))

复制代码

1. a =  [1, 3, 5, 8, 10]
   
2. b =  [9, 2, 4, 6, 7]

复制代码

jerryxjr1220

冬雪雪冬 发表于 2016-11-15 22:27
不知我理解的对不对。

结果应该是对的，但是用排列组合的话，如果对于列表长度比较长的话，比如说长度为100的，速度就会很慢，甚至算不出来。

冬雪雪冬

jerryxjr1220 发表于 2016-11-15 22:39
结果应该是对的，但是用排列组合的话，如果对于列表长度比较长的话，比如说长度为100的，速度就会很慢， ...

我再想想。

冬雪雪冬

换个写法：

1. import random
   
2. a=[random.randint(1, 100) for i in range(100)]
   
3. b=[random.randint(1, 100) for i in range(100)]
   
4. c = a + b
   
5. c.sort(reverse = True)
   
6. a = [c[0]]
   
7. b = [c[1]]
   
8. for i in range(2, len(c) - 1, 2):
   
9.     if sum(a) > sum(b):
   
10.         b.append(c[i])
    
11.         a.append(c[i + 1])
    
12.     else:
    
13.         a.append(c[i])
    
14.         b.append(c[i + 1])
    
15. print(a, sum(a))
    
16. print(b, sum(b))

复制代码

SixPy

冬雪雪冬 发表于 2016-11-15 23:07
换个写法：

这能行？

冬雪雪冬

SixPy 发表于 2016-11-15 23:28
这能行？

我也不知道如何验证，进行100次测试，首先把randint(1, 100)改为randint(10, 100)，避免小的数据容易填平差距，再打印出sum(a)和sum(b)，我看差值都很小。

1. 5521 5521
   
2. 5224 5225
   
3. 5313 5314
   
4. 5910 5909
   
5. 5627 5626
   
6. 5349 5349
   
7. 5713 5712
   
8. 5225 5225
   
9. 5454 5454
   
10. 5840 5838
    
11. 5969 5968
    
12. 5534 5534
    
13. 5367 5365
    
14. 5591 5591
    
15. 5651 5650
    
16. 5778 5777
    
17. 5371 5371
    
18. 5415 5415
    
19. 5342 5342
    
20. 5390 5389
    
21. 5222 5221
    
22. 5474 5474
    
23. 5231 5230
    
24. 5605 5605
    
25. 5572 5571
    
26. 5714 5714
    
27. 5525 5525
    
28. 5449 5449
    
29. 5216 5216
    
30. 5318 5317
    
31. 5875 5874
    
32. 5722 5721
    
33. 5405 5405
    
34. 5485 5484
    
35. 5438 5438
    
36. 5359 5358
    
37. 5421 5419
    
38. 5761 5760
    
39. 5591 5590
    
40. 5403 5402
    
41. 5771 5771
    
42. 5491 5491
    
43. 5725 5725
    
44. 5721 5721
    
45. 5784 5784
    
46. 5348 5348
    
47. 5786 5785
    
48. 5204 5204
    
49. 5493 5493
    
50. 5604 5603
    
51. 5413 5412
    
52. 5495 5495
    
53. 5405 5406
    
54. 5486 5485
    
55. 5569 5568
    
56. 5651 5649
    
57. 5198 5198
    
58. 5347 5348
    
59. 5605 5605
    
60. 5408 5407
    
61. 5511 5511
    
62. 5410 5410
    
63. 5623 5622
    
64. 5533 5532
    
65. 5285 5283
    
66. 5233 5233
    
67. 5429 5428
    
68. 5492 5491
    
69. 5478 5478
    
70. 5432 5431
    
71. 5648 5648
    
72. 5631 5630
    
73. 5394 5394
    
74. 5558 5558
    
75. 5376 5375
    
76. 5449 5448
    
77. 5723 5723
    
78. 5522 5522
    
79. 5544 5543
    
80. 5884 5884
    
81. 5523 5523
    
82. 5613 5612
    
83. 5489 5489
    
84. 5683 5683
    
85. 5205 5205
    
86. 5321 5321
    
87. 5498 5498
    
88. 5789 5788
    
89. 4953 4951
    
90. 5535 5534
    
91. 5466 5466
    
92. 5462 5461
    
93. 5252 5252
    
94. 5162 5161
    
95. 5303 5303
    
96. 5483 5482
    
97. 5664 5664
    
98. 5477 5476
    
99. 5721 5721
    
100. 5626 5626

复制代码

SixPy

懒得写复杂算法了，用矩阵搞定~

1. import numpy as np
   
2. 
   
3. def fn_np(a,b):
   
4.     dif = abs(sum(a)-sum(b))/2
   
5.     c = abs(np.array(a).reshape(-1,1) - b)*1.0   
   
6.     c = abs(c - dif)
   
7.     coo = list(zip(*np.where(c == c.min())))[0]
   
8.     a.append(b.pop(coo[1]))
   
9.     b.append(a.pop(coo[0]))
   
10.     return a,b
    
11. 
    
12. a=[1,3,5,7,9]; b=[2,4,6,8,10]
    
13. print(fn_np(a,b))

复制代码

jerryxjr1220

冬雪雪冬 发表于 2016-11-15 23:45
我也不知道如何验证，进行100次测试，首先把randint(1, 100)改为randint(10, 100)，避免小的数据容易填平 ...

这个算法是可以的，类似于动态规划的思路。
其实华为公司出这题更看中算法的效率，结果越接近最优解越好，但是效率是第一位的。
就像搜索排序，没多少人关注是否是搜索的最匹配值的最优化排序，更多人看重的是搜索的效率。
所以你后一种方法就要比前一种要好。

SixPy

SixPy 发表于 2016-11-16 00:29
懒得写复杂算法了，用矩阵搞定~

简化~

1. from numpy import  array as nparr
   
2. from math import ceil
   
3. def fn_np(a,b):
   
4.     dif = abs(sum(a)-sum(b))/2
   
5.     c = abs(nparr(a,ndmin=2).T - b)*1.0   
   
6.     c = abs(c - dif)
   
7.     m,y = c.argmin(),c.shape[1]
   
8.     coo = (ceil(m/y)-1, m % y)
   
9.     a[coo[0]],b[coo[1]] = b[coo[1]],a[coo[0]]
   
10.     return a,b
    
11. 
    
12. a=[1,3,5,7,9]; b=[2,4,6,8,10]
    
13. print(fn_np(a,b))

复制代码

SixPy

jerryxjr1220 发表于 2016-11-16 05:36
这个算法是可以的，类似于动态规划的思路。
其实华为公司出这题更看中算法的效率，结果越接近最优解越好 ...

@冬雪雪冬 的算法相当于在一个大数组里，依次分出2个小数组。
交换次数太多了~
而且，还可以改进：
c 用 iter
sum 用 单个变量累加

jerryxjr1220

SixPy 发表于 2016-11-16 09:20
简化~

numpy的算法是不是要比单纯用python的列表计算来得效率高？

目前我numpy库用得比较少，大多还停留在简单的一维或者二维列表的计算方面，看来要好好学习一下numpy库

SixPy

jerryxjr1220 发表于 2016-11-16 10:10
numpy的算法是不是要比单纯用python的列表计算来得效率高？

目前我numpy库用得比较少，大多还停留在 ...

那当然，专为大数据而生的~

平时用 itertools 也能应付小规模的数据。

主要是避免写一些繁琐的嵌套循环~

冬雪雪冬

SixPy 发表于 2016-11-16 09:30
@冬雪雪冬 的算法相当于在一个大数组里，依次分出2个小数组。
交换次数太多了~
而且，还可以改进：

与@jerryxjr1220 相比对大数组排序更非时间，好处是两个小数组的差更小。
考虑到c需要先排序就用的列表。
sum的确效率太低了，应该每次循环再叠加。

jerryxjr1220

SixPy 发表于 2016-11-16 09:30
@冬雪雪冬 的算法相当于在一个大数组里，依次分出2个小数组。
交换次数太多了~
而且，还可以改进：

确实，每次比较的时候不应该用sum重头累加，只要叠加新的一个pop出来的数据即可，可以节省好多时间。

SixPy

jerryxjr1220 发表于 2016-11-15 22:02
动态规划解法

所谓 动态规划解法，其实就是 面多了加水，水多了加面~

jerryxjr1220

SixPy 发表于 2016-11-16 11:56
所谓 动态规划解法，其实就是 面多了加水，水多了加面~

很精辟

776667

1. from random import randint
   
2. 
   
3. def list_replace(list_a,list_b):
   
4.     list_a2 = [sorted(list_a)[0]]
   
5.     list_b2 = [sorted(list_b)[0]]
   
6.     list_a = sorted(list_a)[1:]
   
7.     list_b = sorted(list_b)[1:]
   
8.     while list_a:
   
9.         if sum(list_a2) > sum(list_b2):
   
10.             list_a2.append(min(list_a[0],list_b[0]))
    
11.             list_b2.append(max(list_a[0],list_b[0]))
    
12.             list_a = list_a[1:]
    
13.             list_b = list_b[1:]
    
14.         else:
    
15.             list_a2.append(max(list_a[0],list_b[0]))
    
16.             list_b2.append(min(list_a[0],list_b[0]))
    
17.             list_a = list_a[1:]
    
18.             list_b = list_b[1:]
    
19.     list_a = list_a2
    
20.     list_b = list_b2
    
21. 
    
22. if __name__ == '__main__':
    
23.     list_a = [randint(1,1000) for x in range(1,100)]
    
24.     list_b = [randint(1,1000) for x in range(1,100)]
    
25.     list_replace(list_a,list_b)
    
26.     print(sum(list_a))
    
27.     print(sum(list_b))
    

复制代码

上面那个版主大大用的numpy好像是很高端的玩意儿啊，好多地方都看他用这个模块

jerryxjr1220

776667 发表于 2016-12-3 16:44
上面那个版主大大用的numpy好像是很高端的玩意儿啊，好多地方都看他用这个模块

numpy的矩阵运算非常强大