迭代算法到递归算法的转换

Question

嗨，我正在尝试转换我的迭代算法递归解决方案，以实现动态规划后，它做了（请建议我其他方法，以减少这种三重嵌套迭代的时间复杂度）。我不擅长递归。我曾试图转换它，但它给我的索引超出范围的错误。你知道吗

迭代法：

def foo(L):
          L=sorted(L)
          A = 0
          for i,x in enumerate(L):
            for j,y in enumerate(L):
                if x != y:
                    if (y%x ==0):
                        for k,z in enumerate(L):
                            if y != z:
                                if (z%y==0) and (y%x==0):
                                    A= A+1

          return A

递归方法：

A =i =j= k =0 #Initializing globals
def foo(L):
              L=sorted(L)
              global A ,i,j,k
              x=y=z=L
              luckyOne(x,y,z)
              return A

def luckyOne(x,y,z):
    global i,j,k
    while(i< len(x) and j < len(y) and k < len(z)):
        while(x[i] != y[j]):
            luckyTwo(x[i:],y[j:],z[k:])
            i+=1 
            luckyOne(x[i:],y[j:],z[k:])
            # i+=1 
            # return A
        i+=1 
        luckyOne(x[i:],y[j:],z[k:])
    return 0

def luckyTwo(x,y,z):
    global i,j,k
    while (i< len(x) and j < len(y) and k < len(z)):
        while(y[j]%x[i]==0):
            luckyThree(x[i:],y[j:],z[k:])
            j+=1 
            luckyTwo(x[i:],y[j:],z[k:])
        j+=1 
        luckyTwo(x[i:],y[j:],z[k:])
    return 0

def luckyThree(x,y,z):
    global A ,i,j,k
    while (i< len(x) and j < len(y) and k < len(z)):
        while (y[j]!=z[k]):
            while((z[k]%y[j]==0) and (y[j]%x[i]==0)):
                A+=1
                print 'idr aya'
                k+=1 
                luckyThree(x[i:],y[j:],z[k:])
        k+=1 
        luckyThree(x[i:],y[j:],z[k:])
    return 0

输入应该像L=['1'，'2'，'3']

Answer 1

为了加快速度（而不是进行递归），使用1000个条目进行测试，在每个级别对排序的列表进行切片，从而使我的时间缩短了一半以上（在各个级别上去掉小于y, z的数字：

def foo(L):
    assert 0 not in L
    L=sorted(L)
    A = 0
    for i,x in enumerate(L):
        for j,y in enumerate(L[i + 1:]):
            if x != y and not y % x:
                for k,z in enumerate(L[i + j + 2:]):
                    if y != z and not z % y:
                        A = A + 1

    return A

Answer 2

这是我能想到的最快版本：

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

这应该要快得多（是我测试100个元素的列表的七分之一）。你知道吗

该算法本质上是建立一个有向图，其中节点是列表中的数字。如果这些节点的整数值不同，则边从节点A到节点B，并且A均匀地划分为B

然后遍历图形。对于每个起始节点A，找到从A到B有一条边的所有节点B。在纸上，我们将转到所有下一个节点C，但我们不需要。。。我们可以计算出有多少边离开节点B，然后把它加到总数中。你知道吗

编辑

根据列表中值的分布情况，这可能更快：

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

在这里，可以将节点视为具有数值和计数。这样可以避免输入中重复值的重复节点。然后，我们基本上做同样的事情，但乘以适当的计数在每一步。你知道吗

编辑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])

由于@Blckknght，略有改善。首先对唯一值进行排序可以节省一些枚举时间。你知道吗

编辑3

请参阅注释，但此问题中的原始代码实际上是错误的。下面的代码（我认为）基于问题描述做了正确的事情，可以在注释中找到：

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

编辑4

以前代码的更快版本：

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

编辑5

更紧凑的版本（似乎运行时间大致相同）：

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

Answer 3

我来解决你的问题。它应该使用O(N**2)时间。你知道吗

def count_triple_multiples(lst):
    count = collections.Counter(lst)
    double_count = collections.defaultdict(int)
    for x, y in itertools.combinations(sorted(count), 2):
        if y % x == 0:
            double_count[y] += count[x] * count[y]
    triple_count = 0
    for x, y in itertools.combinations(sorted(double_count), 2):
        if y % x == 0:
            triple_count += double_count[x] * count[y]
    return triple_count

我的算法与smarx在他的答案中使用的算法非常相似，但是我记录了与给定值相关的边的数量，而不是一个列表。你知道吗