Как эффективно подсчитать все конкатенации двух кортежей в более длинные цепочки в Python

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

from collections import defaultdict, Counter

def count_chains(links):
    chains = defaultdict(lambda: 1)
    for position in links:
        temp = Counter()
        for a, b in position:
            temp[b] += chains[a]
        chains = temp
    return sum(chains.values())

Он делает почти то же самое, что и ваш, за исключением того, что вместо список цепочек, оканчивающихся на некоторые b-значения, я использую Прилавок цепочек, оканчивающихся на некоторые b-значения: chains говорит мне, сколько цепочек оканчивается на chains[b]. А Counters (и defaultdict) — это словари, поэтому мне не нужно искать и проверять для сопоставления коннекторов, я просто искать их.

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

Например, для b вычисление количества цепочек занимает около 2 мс, а именно:

21430172143725346418968500981200036211228096234110672148875007767407021022498722449863967576313917162551893458351062936503742905713846280871969155149397149607869135549648461970842149210124742283755908364306092949967163882534797535118331087892154125829142392955373084335320859663305248773674411336138752

Попробуйте онлайн!

Вот мое решение с подходом к структуре данных Graph, которое будет более эффективным, чем ваше, имеющее кубическую временную сложность O (n3).

import timeit

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next if next else []
        self.visited = False
        self.mem = None
    def __repr__(self):
        return f'<{self.val} {self.mem}>'
        
def epsi_sol(links, len_):
    nodes = {}
    start_nodes = set(i[0] for i in links[0]) # {'a', 'b'}

    # constructiong the graph
    for i in links:
        for j in i:
            if j[0] not in nodes:
                nodes[j[0]] = Node(j[0])
            if j[1] not in nodes:
                nodes[j[1]] = Node(j[1])

            nodes[j[0]].next.append(nodes[j[1]])

    def find_chain_with_length(node, length, valid_length):
        if length +1 == valid_length:
            return 1

        # if already visited just return
        if node.visited:
            return 0 
        
        if node.mem is not None:
            return node.mem

        # if this is not leaf node
        # we will mark it visited
        node.visited = True
        temp_count = 0
        for each_neighbor in node.next:
            temp_count += find_chain_with_length(each_neighbor, length+1, valid_length)
        # after visiting mark it unvisited
        node.visited = False
        node.mem = temp_count
        return temp_count

    solution_count = 0
    for each_start_node in start_nodes:
        solution_count += find_chain_with_length(nodes[each_start_node],0, len_)
    return solution_count

from collections import defaultdict, Counter

def kelly_sol(links, len_):
    chains = defaultdict(lambda: 1)
    for position in links[:len_]:
        temp = Counter()
        for a, b in position:
            temp[b] += chains[a]
        chains = temp
    return sum(chains.values())

def mac_sol(links, len_):
    chains = links[0]
    
    # seach for all possible paths:
    # iterate over all positions
    for position in links[1:]:
        
        # temp array to help me grow the chain
        temp = []
            
        # over each chain in the current set of chains
        for chain in chains:

            # over each link in a given position
            for link in position:
                
                # check if the chain and link are chainable
                if chain[-1] == link[0]:
                    
                    # append new link to a pre-existing chain
                    temp.append(chain + tuple([link[1]]))
        
        # overwrite the current list of chains
        chains = temp
    return len(chains)

# tests
for n in range(100, 1000, 100):
    links = [[(f'1_{i}', f'1_{i+1}'), (f'1_{i}', f'2_{i+1}'), (f'2_{i}', f'1_{i+1}'), (f'2_{i}', f'2_{i+1}')] for i in range(n)]
    print('-'*50)
    print(f'kelly_sol({n}) => {timeit.timeit(lambda: kelly_sol(links, n+1), number=2)} seconds')
    print(f'epsi_sol({n}) => {timeit.timeit(lambda: epsi_sol(links, n+1), number=2)} seconds')
    if n <50:
        print(f'mac_sol({n}) => {timeit.timeit(lambda: mac_sol(links, n+1), number=2)} seconds')
    print('-'*50)

--------------------------------------------------
kelly_sol(100) => 0.0013752000000000209 seconds
epsi_sol(100) => 0.0022567999999996147 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(200) => 0.0026332999999993945 seconds
epsi_sol(200) => 0.004522500000000207 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(300) => 0.003924899999999454 seconds
epsi_sol(300) => 0.006861199999999457 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(400) => 0.005278099999999952 seconds
epsi_sol(400) => 0.012999699999999947 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(500) => 0.006728900000000593 seconds
epsi_sol(500) => 0.01406989999999908 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(600) => 0.00828249999999997 seconds
epsi_sol(600) => 0.015398799999999824 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(700) => 0.009703200000000578 seconds
epsi_sol(700) => 0.01597070000000045 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(800) => 0.009961999999999804 seconds
epsi_sol(800) => 0.0196051999999991 seconds
--------------------------------------------------
--------------------------------------------------
kelly_sol(900) => 0.014800799999999725 seconds
epsi_sol(900) => 0.02183789999999952 seconds
--------------------------------------------------