|
发表于 2017-6-17 02:41:50
|
显示全部楼层
心累啊,方法有点笨,接近十二个小时
丫的,今天还要考四级,要是得不到这100鱼币,我就要崩溃了。
- # 基列表挑选准则:挑选含不同字母多的字符串
- def base(a):
- c = []
- for i in range(len(a)):
- c.append(len(set(a[i])))
- return (c.index(max(c))) #返回符合要求的字符串在列表中的位置
- # 次列表的挑选准则:挑选字母在基列表中位置靠前的字符串,如果没有则选择第一个字符串
- def less(a,a_base):
- if len(a) == 1:
- return 0
- else:
- temp = []
- for i in a_base:
- for j in range(len(a)):
- try:
- temp.append(a[j].index(i))
- except ValueError:
- temp.append(len(a[j]))
- if min(temp)<len(a[j]):
- return(temp.index(min(temp))) #返回符合要求的字符串在列表中的位置
- return 0 #如果没有与基列表重复的字母,则选择第一个字符串
- # 寻找所有的匹配组合,返回匹配超度最长的组合。
- def seek_index(a_base,a_less):
- #返回在主列表中的位置T=[组合1,..,组合n] 组合1=[位置0,...,位置n]
- T = []
- for i in range(len(a_less)):
- temp = []
- for j in range(i,len(a_less)):
- if temp==[]:
- k=0
- try:
- k = a_base.index(a_less[j],k)
- temp.append(k) #偶数位置是对应元素在基列表中的位置
- temp.append(j) #奇数位置是对应元素在次列表中的位置
- k += 1
- except ValueError:
- pass
-
- T.append(temp)
- #返回最长组合
- temp = []
- for k in T:
- temp.append(len(k))
- return (T[temp.index(max(temp))])
- #利用得到的最优匹配位置进行匹配,在基列表中插入不满足次列表的元素
- def match(a_base,a_less,index):
- temp_base = []
- temp_less = []
- for i in range(len(index)):
- if not i % 2:
- temp_base.append(index[i])#得到对应元素在基列表中的位置
- else:
- temp_less.append(index[i])#得到对应元素在次列表中的位置
- for i in range(len(temp_less)):
- if temp_less[i] != 0:
- if i == 0:
- temp = a_less[:temp_less[i]]
- temp.reverse()
- for j in range(len(temp)):
- a_base.insert(temp_base[i],temp[j])
- elif i != len(a_less) - 1 and temp_less[i] - temp_less[i-1] > 1:
- temp = a_less[temp_less[i-1]+1:temp_less[i]]
- temp.reverse()
- for j in range(len(temp)):
- a_base.insert(temp_base[i],temp[j])
- elif i == len(temp_less) -1 and i != len(a_less) - 1 and temp_less[i] - temp_less[i-1] == 1:
- temp = a_less[temp_less[i]+1:]
- for j in range(len(temp)):
- a_base.append(temp[j])
- return a_base
-
-
- L = ['ACBD','ADBC','CBDD','CABD']
- list_base = list(L[base(L)]) # 挑选基列表
- L.remove(''.join(list_base)) # 在L中移除选中的基列表所对应的字符串
- for i in range(len(L)):
- list_less = list(L[less(L,list_base)]) #挑选次列表
- L.remove(''.join(list_less))# 在L中移除选中的次列表中对应的字符串
- nice_index = seek_index(list_base,list_less) #查找最佳匹配顺序
- list_base = match(list_base,list_less,nice_index) #进行匹配
- print (len(list_base))
-
复制代码 |
|