从类似列表中创建一个有序列表

-2

我有很多巴士站的列表。每个列表都代表一辆公共汽车在一次旅程中停车。行程路线相同，但公交车可能在任何站点停车。从类似列表中创建一个有序列表

我想在ORDER中创建所有站点的完整列表。

下面是三个样品巴士旅程。

bus_1 = ["5171","1337","1341","1350","1352","1357","320","278","10","15","215","218","1623","1624","7347"] 

bus_2 = ["5171","2976","2979","2981","2991","2992","1326","1327","1329","1331","1336","1337","1339","1340","1342","1345","1350","1354","1357","1359","320","278","12","15","17","21","205","215","216","218","1624","1626","1627","7347"] 

bus_3 = ["5171","2977" "2978","2991","1325","1326","1327","1329","1330","1331","1332","1333","1337","1340","1341","1342","1344","1345","1347","1348","1352","1353","1354","1355","1357","1359","320","278","10","12","14","15","17","19","21","85","204","215","218","219","220","1622","1623","1624","1625","1626","1627","7347"]

这可能吗？

来源

2017-06-22 Gavin Hinfey

请发布预期结果。 –

复制品呢？ –

究竟是什么订单？ –

那么，这是我的解决方案 - 请检查它是否满足您的需求。我用字典替换了子路径的单独变量，希望它不是问题。

routes = { 
    'bus_1': ["5171","1337","1341","1350","1352","1357","320","278","10","15","215","218","1623","1624","7347"], 
    'bus_2': ["5171","2976","2979","2981","2991","2992","1326","1327","1329","1331","1336","1337","1339","1340","1342","1345","1350","1354","1357","1359","320","278","12","15","17","21","205","215","216","218","1624","1626","1627","7347"], 
    'bus_3': ["5171","2977", "2978","2991","1325","1326","1327","1329","1330","1331","1332","1333","1337","1340","1341","1342","1344","1345","1347","1348","1352","1353","1354","1355","1357","1359","320","278","10","12","14","15","17","19","21","85","204","215","218","219","220","1622","1623","1624","1625","1626","1627","7347"] 
} 

stops = set() 
stop_pairs = set() 
for route in routes.values(): 
    stops.update(route) 
    for i in range(1,len(route)): 
     # each pair is correctly ordered 
     stop_pairs.add(tuple(route[i-1:i+1])) 
# at this point, 'stops' is the set of all stops 
# and 'stop_pairs' is a set of tuples representing sequence of stops 
ordered_stops = [] 
while stops: 
    # let's look for the minimal elements in stops 
    minimals = set() 
    for stop in stops: 
     if not any((s, stop) in stop_pairs for s in stops): 
      # there is no such s that s precedes stop 
      minimals.add(stop) 
    ordered_stops.append(minimals) 
    stops.difference_update(minimals) 
print(ordered_stops)

我的结果是：

[{ '5171'}，{ '2977'， '2976'}，{ '2979'， '2978'}，{ '2981'}， {'2991'}，{'1325'，'2992'}，{'1326'}，{'1327'}，{'1329'}，{'1330'}，{'1331'}，，'1332'}，{'1337'}，{'1339'}，{'1340'}，{'1341'}，{'1342'}，{'1344'}，{' 1345'}，{'1347'，'1350'}，{'1348'}，{'1352'}，{'1353'}，{'1354'}，{'1355'}， {'1359'}，{'320'}，{'278'}，{'10'}，{'12'}，{'14'}，{'15'}，{'17'}，{' 19'}，{'21'}，{'205'，'85'}，{'204'}，{'215'}，{'216'}，{'218'}，{'219' {'220'}，{'1622'}，{'1623'}，{'1624'}，{'1625'}，{'1626'}，{'1627'}，{'7347'}]

UPDATE：我刚刚注意到我的程序可以很容易地推广到生成不同的解决方案，并相应地编辑它。现在，结果列表由一系列具有相同优先级的停止点组成（即每个停止点内的停止点可以重新组合）。显然，有六个这样的组：{'2977'，'2976'}，{'2979'，'2978'}，{'1325'，'2992'}，{'1336'，'1332'}，{' 1347'，'1350'}，{'205'，'85'}。

来源

2017-06-22 16:16:30

与depperm的答案一样，这看起来像提供的数据可合理实现的正确。我会去找更多的数据来进一步测试。我有一个答案，我将在下面发布。然而它并不像这样简洁。 –

这工作。我放了68辆巴士，剩下3套同等优先。有了足够的巴士，这些应该被淘汰。谢谢。 –

我能够接近，但我认为你需要更多的路线才能获得完整的路线。它不能添加的一些价值没有足够的相似的周边元素，但这可能会让你沿着正确的道路前进。

bus_1 = ["5171","1337","1341","1350","1352","1357","320","278","10","15","215","218","1623","1624","7347"] 
bus_2 = ["5171","2976","2979","2981","2991","2992","1326","1327","1329","1331","1336","1337","1339","1340","1342","1345","1350","1354","1357","1359","320","278","12","15","17","21","205","215","216","218","1624","1626","1627","7347"] 
bus_3 = ["5171","2977", "2978","2991","1325","1326","1327","1329","1330","1331","1332","1333","1337","1340","1341","1342","1344","1345","1347","1348","1352","1353","1354","1355","1357","1359","320","278","10","12","14","15","17","19","21","85","204","215","218","219","220","1622","1623","1624","1625","1626","1627","7347"] 

buses=[bus_1,bus_2,bus_3] 

added=set() 
final=bus_1[:] 
temp=bus_1+bus_2+bus_3 
i=0 
x=0 
while set(final) != set(temp): 
    # get 2 elements which we'll see if they're in final route 
    if x<len(buses): 
    t=buses[x][i:i+2] 
    else: 
    t=final[i:i+2] 
    try: 
    a=final.index(t[0]) 
    b=final.index(t[1]) 
    except: 
    a=b=-1 
    # check if in final and not next to each other, and not added yet 
    for q,bus in enumerate(buses): 
    if x!=q and t[0] in bus and t[1] in bus and a+1==b and (t[0],t[1]) not in added: 
     u=bus.index(t[0]) 
     v=bus.index(t[1]) 
     final[a:b]=bus[u:v] 

     added.add((t[0],t[1])) 
     i=0 
     x=0 

    if x<len(buses): 
    for q,bus in enumerate(buses): 
     if q==x and i+2<len(bus): 
     i+=1 
     elif q==x and i+2==len(bus): 
     x+=1 
     i=0 
    elif x==len(buses)+1 and i+2<len(final): 
    i+=1 
    else: 
    x+=1 
    i=0 

    if x>len(buses)+1: 
    break 

print("final route(incomplete)") 
print(final) 
print('unique stops') 
print(set(temp)) 
#this is my result 
#mine=['5171', '2976', '2979', '2981', '2991', '2992', '1326', '1327', '1329', '1330', '1331', '1336', '1337', '1339', '1340', '1341', '1350', '1352', '1353', '1354', '1355', '1357', '1359', '320', '278', '10', '12', '14', '15', '17', '19', '21', '205', '215', '216', '218', '219', '220', '1622', '1623', '1624', '1625', '1626', '1627', '7347'] 
#this is what you probably want 
#goal=['5171', '2976', '2977', '2978', '2979', '2981', '2991', '2992', '1325', '1326', '1327', '1329', '1330', '1331', '1332', '1333', '1336', '1337', '1339', '1340', '1341', '1342', '1344', '1345', '1347', '1348', '1350', '1352', '1353', '1354', '1355', '1357', '1359', '320', '278', '10', '12', '14', '15', '17', '19', '21', '85','204', 205', '215', '216', '218', '219', '220', '1622', '1623', '1624', '1625', '1626', '1627', '7347'] 

#unable to add 
#['204', '85', '1348', '1347', '1342', '1344', '1345', '1333', '1332', '1325', '2978']

来源

2017-06-22 15:36:11 depperm

让我仔细看看，但它看起来不错。 –

# All three buses in 1 2d list. 
route = ["5171","1337","1341","1350","1352","1357","320","278","10","15","215","218","1623","1624","7347"],["5171","2976","2979","2981","2991","2992","1326","1327","1329","1331","1336","1337","1339","1340","1342","1345","1350","1354","1357","1359","320","278","12","15","17","21","205","215","216","218","1624","1626","1627","7347"],["5171","2977","2978","2991","1325","1326","1327","1329","1330","1331","1332","1333","1337","1340","1341","1342","1344","1345","1347","1348","1352","1353","1354","1355","1357","1359","320","278","10","12","14","15","17","19","21","85","204","215","218","219","220","1622","1623","1624","1625","1626","1627","7347"] 

temp = set() 
out = {} 

# remove dupes by adding each stop to a set. 
for journey in route: 
    for stop in journey: 
     temp.add(stop) 

# create a dictionary where the key is a unique stop 
# the value is a list of two empty sets. 
for i in temp: 
    out[i] = [set(),set()] 

for i in temp: 
    for journey in route: 
     if i in journey: 

      # add stops which occur before this stop to one dictionary 
      for before in journey[0:journey.index(i)]: 
       out[i][0].add(before) 

      # and stops which occur after this stop to the other dictionary 
      for after in journey[journey.index(i):-1]: 
       out[i][1].add(after) 

# create a template final list of unique stops from the set. 
final_list = list(temp) 

# iterate ove the dictionary 
for key, value in out.items(): 

    # get list of what stops should be ordered before the current stop 
    before_set = value[0] 
    # and a list of those that should be after. 
    after_set = value[1] 


    for b in before_set: 

     # if the current value is not where is should be move it. 
     if final_list.index(b) > final_list.index(key): 

      temp = final_list.index(key) 
      final_list.insert(final_list.index(b), key) 
      final_list.pop(temp) 

    for a in after_set: 

     # if the current value is not where is should be move it. 
     if final_list.index(a) < final_list.index(key): 

      temp = final_list.index(key) 
      final_list.insert(final_list.index(a), key) 
      final_list.pop(temp+1) 

# and run again in the opposite direction. 
final_list = final_list[::-1] 

for key, value in out.items(): 

    before_set = value[0] 
    after_set = value[1] 

    for b in before_set: 

     if final_list.index(b) > final_list.index(key): 

      temp = final_list.index(key) 
      final_list.insert(final_list.index(b), key) 
      final_list.pop(temp) 

    for a in after_set: 

     if final_list.index(a) < final_list.index(key): 

      temp = final_list.index(key) 
      final_list.insert(final_list.index(a), key) 
      final_list.pop(temp+1) 

print(final_list)

来源

2017-06-22 16:57:40

从类似列表中创建一个有序列表

回答

相关问题