从相似列表创建有序列表

Question

我有许多公共汽车站的名单。 每一个列表代表一辆公共汽车在一次旅程中所经过的站点。 旅行路线是一样的，但公共汽车可以停在任何一站。你知道吗

我要按顺序创建所有站点的完整列表。你知道吗

下面是三个巴士旅行的例子。你知道吗

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"]

这可能吗？你知道吗

Answer 1

好吧，这是我的解决方案-请检查它是否满足您的需要。我已经用字典替换了子路由的独立变量，希望这不是问题。你知道吗

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'}, {'1336', '1332'}, {'1333'}, {'1337'}, {'1339'}, {'1340'}, {'1341'}, {'1342'}, {'1344'}, {'1345'}, {'1347', '1350'}, {'1348'}, {'1352'}, {'1353'}, {'1354'}, {'1355'}, {'1357'}, {'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'}]

更新：我刚刚注意到，我的程序可以很容易地通用化，生成各种解决方案，并相应地进行编辑。现在，结果列表由具有相同优先级的停止集组成（即，可以重新排列每个集中的停止）。显然，有六个这样的集合：{2977'，2976'}，{2979'，2978'}，{1325'，2992'}，{1336'，1332'}，{1347'，1350'}，{205'，85'}。你知道吗

Answer 2

我能够接近，但我认为你需要更多的路线来获得一个完整的路线。它无法添加的某些值没有足够的类似周围元素，但这可能会使您走上正确的道路。你知道吗

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']

Answer 3

# 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)