Python для вложенных циклов, соответствующих всем возможным строкам пар - PullRequest
Новая
       39

Python для вложенных циклов, соответствующих всем возможным строкам пар

0 голосов
/ 12 марта 2020

Я пытаюсь составить список всех возможных маршрутов между наборами значений. Мой текущий набор данных представляет собой набор списков, каждый из которых содержит пару (вход и выход) значений 

List = [[0.5,1],[0.75,1],[0.5,1.5],[0.75,1.5],[1,1.5],[0.5,2],[0.75,2],[1,2],[1.5,2],[0.75,3],[1,3],[1.5,3],[2,3],[1,4],[1.5,4],[2,4],[3,4],[1.5,6],[2,6],[3,6],[4,6],[3,8],[2,8],[4,8],[6,8],[3,10],[4,10],[6,10],[8,10],[4,12],[6,12],[8,12],[10,12],[6,14],[8,14],[10,14],[12,14],[6,16],[8,16],[10,16],[12,16],[14,16],[10,18],[12,18],[14,18],[16,18],[10,20],[12,20],[14,20],[16,20],[18,20],[14,24],[16,24],[18,24],[20,24],[22,24],[18,26],[20,26],[22,26],[24,26],[18,28],[20,28],[24,28],[26,28],[20,30],[24,30],[26,30],[28,30],[24,32],[26,32],[28,32],[30,32],[24,34],[26,34],[30,34],[32,34],[24,36],[26,36],[30,36],[32,36],[34,36],[24,42],[26,42],[30,42],[32,42],[34,42],[36,42],[36,48],[40,48],[42,48],[44,48],[46,48]]

Мне нужно найти способ объединить их, чтобы составить большой список всех маршрутов между для всех значений, например, для всех маршрутов в диапазоне 0,5-2, будет указано что-то похожее на это: 

[0.5,2];[0.5,1][1,2];[0.5,1][1,1.5][1.5,2];[0.5,1.5][1.5,2]

Я считаю, что было бы возможно использовать циклы for в Python, но я новичок и мое единственное решение было бы через вложение столько циклов, сколько у меня есть пары, что является чрезвычайно громоздким и легко сделать ошибку при выполнении, я не уверен относительно любых альтернативных или более обтекаемых методов. Любая помощь будет принята с благодарностью

1 Ответ

1 голос
/ 12 марта 2020

Вы понимаете, что это приведет к очень большому количеству маршрутов и что вычисление может занять много времени, если ваш список станет намного больше.

Что вы можете сделать, так это постепенно построить список маршрутов, которые вы расширяете новые маршруты, образованные соединением пар в начало или конец имеющихся у вас маршрутов: 

List = [[0.5,1],[0.75,1],[0.5,1.5],[0.75,1.5],[1,1.5],[0.5,2],[0.75,2],[1,2],[1.5,2],[0.75,3],[1,3],[1.5,3],[2,3],[1,4],[1.5,4],[2,4],[3,4],[1.5,6],[2,6],[3,6],[4,6],[3,8],[2,8],[4,8],[6,8],[3,10],[4,10],[6,10],[8,10],[4,12],[6,12],[8,12],[10,12],[6,14],[8,14],[10,14],[12,14],[6,16],[8,16],[10,16],[12,16],[14,16],[10,18],[12,18],[14,18],[16,18],[10,20],[12,20],[14,20],[16,20],[18,20],[14,24],[16,24],[18,24],[20,24],[22,24],[18,26],[20,26],[22,26],[24,26],[18,28],[20,28],[24,28],[26,28],[20,30],[24,30],[26,30],[28,30],[24,32],[26,32],[28,32],[30,32],[24,34],[26,34],[30,34],[32,34],[24,36],[26,36],[30,36],[32,36],[34,36],[24,42],[26,42],[30,42],[32,42],[34,42],[36,42],[36,48],[40,48],[42,48],[44,48],[46,48]]

routes = []
for pair in List:
    inValue,outValue = pair
    newRoutes = [[pair]]
    for path in routes:
        if path[0][0] == outValue:
            newRoutes.append([pair] + path)
        if path[-1][-1] == inValue:
            newRoutes.append(path + [pair])
    routes.extend(newRoutes)

output: 

print("number of routes:",len(routes))
for route in routes[:10]:
    print(route)
print("...")
for route in routes[-10:]:
    print(route)

number of routes: 5646987
[[0.5, 1]]
[[0.75, 1]]
[[0.5, 1.5]]
[[0.75, 1.5]]
[[1, 1.5]]
[[0.5, 1], [1, 1.5]]
[[0.75, 1], [1, 1.5]]
[[0.5, 2]]
[[0.75, 2]]
[[1, 2]]
...
[[0.75, 1], [1, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.5, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.75, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[1, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.5, 1], [1, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.75, 1], [1, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[22, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[44, 48]]
[[46, 48]]

Обратите внимание, что это можно оптимизировать с помощью индексации существующие маршруты по их первому / последнему значению. Подобная оптимизация сделает это в два раза быстрее, но не уменьшит количество маршрутов в выводе: 

routesFirst = dict()
routesLast  = dict()
routes      = []
for pair in List:
    inValue,outValue = pair
    newRoutes = [[pair]]
    for path in routesFirst.get(outValue,[]):
        newRoutes.append([pair]+path)
    for path in routesLast.get(inValue,[]):
        newRoutes.append(path+[pair])
    routes.extend(newRoutes)
    routesFirst.setdefault(inValue,[]).extend(newRoutes)
    routesLast.setdefault(outValue,[]).extend(newRoutes)

[РЕДАКТИРОВАТЬ] рекурсивный подход (добавлен для хорошей меры):

Если вы не собираетесь go по всем путям, вы можете создать рекурсивную функцию генератора, которая будет возвращать их один за другим. Вы можете использовать его для l oop (например), который намереваетесь нарушить при выполнении определенного условия.

Вот очень простой пример (не оптимизированный с помощью meoization или чего-либо еще): 

def findRoutes(pairs,previous=None):
    for pair in pairs:
        inValue,outValue = pair
        if inValue != previous and previous is not None:
            continue
        yield [pair]
        for subRoute in findRoutes(pairs,outValue):
            yield [pair] + subRoute

output: 

for route in findRoutes(List):
    if len(route) == 5:
       print("first 5 step route:",route)
       break

# first 5 step route: [[0.5, 1], [1, 1.5], [1.5, 2], [2, 3], [3, 4]]

[EDIT2] Поиск пути от одного числа к другому

Чтобы помочь понять генератор, я реализовал простой вариант, который будет только возвратные пути, которые соединяют два указанных c числа. Он все еще должен использовать рекурсию, но вместо того, чтобы проходить через все возможные соединения, он смотрит только на те, которые начинаются с данного источника и заканчиваются, когда достигается пункт назначения. Для многошаговых путей одна и та же функция вызывается для каждого возможного outValue, который подключается от источника. 

def findPath(pairs,origin,destination):
    for pair in pairs:
        inValue,outValue = pair
        if inValue != origin:
            continue
        if outValue == destination :
            yield [pair]
            continue
        for subPath in findPath(pairs,outValue,destination):
            yield [pair] + subPath

output: 

List = [[0.5,1],[0.75,1],[0.5,1.5],[0.75,1.5],[1,1.5],[0.5,2],[0.75,2],[1,2],[1.5,2],[0.75,3],[1,3],[1.5,3],[2,3],[1,4],[1.5,4],[2,4],[3,4],[1.5,6],[2,6],[3,6],[4,6],[3,8],[2,8],[4,8],[6,8],[3,10],[4,10],[6,10],[8,10],[4,12],[6,12],[8,12],[10,12],[6,14],[8,14],[10,14],[12,14],[6,16],[8,16],[10,16],[12,16],[14,16],[10,18],[12,18],[14,18],[16,18],[10,20],[12,20],[14,20],[16,20],[18,20],[14,24],[16,24],[18,24],[20,24],[22,24],[18,26],[20,26],[22,26],[24,26],[18,28],[20,28],[24,28],[26,28],[20,30],[24,30],[26,30],[28,30],[24,32],[26,32],[28,32],[30,32],[24,34],[26,34],[30,34],[32,34],[24,36],[26,36],[30,36],[32,36],[34,36],[24,42],[26,42],[30,42],[32,42],[34,42],[36,42],[36,48],[40,48],[42,48],[44,48],[46,48]]

for path in findPath(List,1,3):
    print(path)


[[1, 1.5], [1.5, 2], [2, 3]]
[[1, 1.5], [1.5, 3]]
[[1, 2], [2, 3]]
[[1, 3]]
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...