一个python的组合题目

帮同学做了道题,附上自己的解答。

他的题目是:

有a,b两序列,大小相同,序列中元素均为正整数,无序。

要求实现:通过交换a,b中的元素,使得 [序列a所有元素的和] 与 [序列b所有元素的和] 之间的差值最小。

这是一个组合问题,我们需要从一个列表里取出一半的元素,然后让这些元素的和最接近原始和的一半。

对于排列组合,python提供了高效迭代器,位于itertools模块。 可以直接暴力枚举。

#coding:utf-8
import itertools

def swap_item(a, b):
    lst = a + b    # 合并两个列表
    min_diff = sum(lst)
    half_sum = min_diff / 2    # 原始和的一半

    for item in itertools.permutations(lst, len(lst)/2):
        diff = abs(half_sum - sum(item))
        if diff < min_diff:
            min_diff = diff
            result = list(item)
            if diff == 0: break    # 如果正好是原始和的一半,即最佳方案
    in_lst = []
    out_lst = []
    for item in set(a + result):
        a_num = a.count(item)
        result_num = result.count(item)
        if a_num < result_num:    # 列表A添加该元素
            in_lst.append(item * (result_num - a_num))
        elif a_num > result_num:    # 列表A移除该元素
            out_lst.append(item * (a_num - result_num))
            
    print 'A ----->'.ljust(10), '<----- B'.rjust(9)
    for x,y in zip(out_lst, in_lst):
        print str(x).ljust(10), str(y).rjust(9)
    print '\nFinal result is', result

a = [19, 90, 1, 2, 3, 52, 11]
b = [6, 66, 21, 45, 32, 17, 43]
swap_item(a, b)

输出结果:
swap-list-items

发表评论

您的电子邮箱地址不会被公开。