Conversion of iterative algorithm to recursive

This is the fastest version I can come up with:

def foo(lst):
    edges = {x: [y for y in lst if x != y and y % x == 0] for x in set(lst)}
    return sum(len(edges[y]) for x in lst for y in edges[x])

This should be significantly faster (1/7th the time in my test of lists with 100 elements).

The algorithm is essentially to build a directed graph where the nodes are the numbers in the list. Edges go from node A to node B iff the integer values of those nodes are different and A divides evenly into B.

Then traverse the graph. For each starting node A, find all the nodes B where there's an edge from A to B. On paper, we would then go to all the next nodes C, but we don't need to... we can just count how many edges are leaving node B and add that to our total.

EDIT

Depending on the distribution of values in the list, this is probably faster:

def foo(lst):
    counts = Counter(lst)
    edges = {x: [y for y in counts if x != y and y % x == 0] for x in counts}
    return sum(counts[x] * counts[y] * sum(counts[z] for z in edges[y]) for x in counts for y in edges[x])

Here, you can think of nodes as having a numeric value and a count. This avoids duplicate nodes for duplicate values in the input. Then we basically do the same thing but multiply by the appropriate count at each step.

EDIT 2

def foo(lst):
    counts = collections.Counter(lst)
    edges = collections.defaultdict(list)
    for x, y in itertools.combinations(sorted(counts), 2):
        if y % x == 0:
            edges[x].append(y)
    return sum(counts[x] * counts[y] * sum(counts[z] for z in edges[y]) for x in counts for y in edges[x])

Slight improvement thanks to @Blckknght. Sorting the unique values first saves some time in enumeration.

EDIT 3

See comments, but the original code in this question was actually wrong. Here's code that (I think) does the right thing based on the problem description which can be found in the comments:

def foo3(lst):
    count = 0

    for x, y, z in itertools.combinations(lst, 3):
        if y % x == 0 and z % y == 0:
            count += 1

    return count

print(foo3([1, 2, 3, 4, 5, 6]))  # 3
print(foo3([6, 5, 4, 3, 2, 1]))  # 0

EDIT 4

Much faster version of the previous code:

def foo4(lst):
    edges = [[] for _ in range(len(lst))]

    for i, j in itertools.combinations(range(len(lst)), 2):
        if lst[j] % lst[i] == 0:
            edges[i].append(j)

    return sum(len(edges[j]) for i in range(len(lst)) for j in edges[i])

EDIT 5

More compact version (seems to run in about the same amount of time):

def foo5(lst):
    edges = [[j for j in range(i + 1, len(lst)) if lst[j] % lst[i] == 0] for i in range(len(lst))]
    return sum(len(edges[j]) for i in range(len(lst)) for j in edges[i])