整数接力问题

千年沉寂

问题：
    所谓整数接力是指将n个正整数前后拼接成一个数。不同的接力方式将得到不同的结果。例如n=3时，3个正整数的接力结果有：123，132，213，231，312，321。

任务：
    对于给定的n个正整数，找出一种最佳的接力方式，使得接力结果最大。

千年沉寂

代码：

def strcmp(a,b):     return -1 if a+b>b+a else 1 def conint(lst):     for i in range(len(lst)):         lst[i]=str(lst[i])     lst=sorted(lst,strcmp)     intstr=""     for i in lst:         intstr+=i     print intstr def main():     lst=[93,13,21,50,109]     conint(lst) if __name__ == '__main__':     main()

结果：93502113109

julyzergcn

二楼的简化版代码：

#coding=cp936 '''问题：     所谓整数接力是指将n个正整数前后拼接成一个数。不同的接力方式将得到不同的结果。例如n=3时，3个正整数的接力结果有：123，132，213，231，312，321。 任务：     对于给定的n个正整数，找出一种最佳的接力方式，使得接力结果最大。 ''' lst = [93,13,21,50,109] lst = [str(i) for i in lst] lst.sort(lambda a,b:-1 if a+b>b+a else 1) print ''.join(lst)

julyzergcn

基于全排列的算法：

#coding=cp936 '''问题：     所谓整数接力是指将n个正整数前后拼接成一个数。不同的接力方式将得到不同的结果。例如n=3时，3个正整数的接力结果有：123，132，213，231，312，321。 任务：     对于给定的n个正整数，找出一种最佳的接力方式，使得接力结果最大。 ''' lst = [93,13,21,50,109] def perm(lst, lst2):     '''a generator function that demonstrate full permutation algorithm'''     if len(lst) == len(lst2):         yield lst2     else:         for i in lst:             if i in lst2:continue             lst2.append(i)             for j in perm(lst, lst2):                 yield j             lst2.pop() max = 0 for i in perm(lst, []):     tmp = int(''.join([str(i) for i in lst]))     if tmp > max:         max = tmp print max

千年沉寂

哈哈 简化，学习了。。

千年沉寂

对yield 生成器表达式还不太懂

julyzergcn

关于yield，我的理解是，分2种情况吧：
1，产生器函数没有递归的情况，yield跟print差不多，只不过输出的地方不一样而已；
2，产生器函数有递归的情况，例如递归函数为foo，要用这种形式：for i in foo():yield i 来代替foo()；
总之yield使得传统的函数返回不止一个地方（return）了，可以yield很多次；
产生器使得缓存大大减小，就像上面的那个求解最大排列的算法，我们不用预先把所有的排列缓存到一个list里，然后max(list)求最大值；而是“现做现吃”，一边产生排列，一边把刚生成的排列和最大的比较一下，这样，当产生完所有的排列（全排列）之后，就可以得到最大的那一个。

千年沉寂

说明的很详细，谢谢 哈哈

victorlee129

别枚举，贪心即可。