從類似列表中創建一個有序列表

-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

從類似列表中創建一個有序列表

回答

相關問題