如何将“for循环”转换为“递归”？

Question

我做了一个函数如下

下面的“列表”包含12个列表元素

def calLen(lists):
    my_array = []
    count = 0
    for item0 in lists[0]:
        my_array.append(item0)
        for item1 in lists[1]:
            my_array.append(item1)
            for item2 in lists[2]:
                my_array.append(item2)
                for item3 in lists[3]:
                    my_array.append(item3)
                    for item4 in lists[4]:
                        my_array.append(item4)
                        for item5 in lists[5]:
                            my_array.append(item5)
                            for item6 in lists[6]:
                                my_array.append(item6)
                                for item7 in lists[7]:
                                    my_array.append(item7)
                                    for item8 in lists[8]:
                                        my_array.append(item8)
                                        for item9 in lists[9]:
                                            my_array.append(item9)
                                            for item10 in lists[10]:
                                                my_array.append(item10)
                                                for item11 in lists[11]:
                                                    my_array.append(item11)
                                                    my_set = set(my_array)
                                                    if len(my_set) > 7 :
                                                        count += 1
                                                    my_array.pop()
                                                my_array.pop()
                                            my_array.pop()
                                        my_array.pop()
                                    my_array.pop()
                                my_array.pop()
                            my_array.pop()
                        my_array.pop()
                    my_array.pop()
                my_array.pop()
            my_array.pop()
        my_array.pop()
    print(count)
    if count > 0 :
        return True
    else :
        return False

assert calLen([[0,1],[1],[2,3,4],[5],[1,4,7],[3,5],[6],[1,2,3,4],[5,6],[1,7],[2,5,7],[0,3,4]]) == True, "Error-1!"
assert calLen([[1,3],[2,7],[5],[6],[7],[2],[4,5],[2,3,4,5,6],[2,3,7],[1,4,5],[3],[6]]) == False, "Error-2!"

我知道。。。看起来很愚蠢

幸运的是，“n（列表的长度）”这次固定为12，但是如果n的值不同，如何将其更改为递归函数

---

这个问题是我想解决的

给定12个列表，每个列表的随机数范围为0到7，如[0], [1,4,6], [6,7]

您只需从每个列表中获取一个数字，然后将它们全部放在一个集合中

如果可以使{0,1,2,3,4,5,6,7}，则返回True或False

参见assert示例

Answer 1

是的，这确实是一个可以用递归来解决的问题。您有更多的控制权在代码中进行正确的检查，并且只遵循列表中可能有正确答案的路径。执行12个嵌套for循环并获取12个列表的乘积将不是一个有效的解决方案

以下是我的解决方案：

def find_range(end, lists):
    def find_range_inner(index, se):
        # Return false if there are more numbers that have to be found
        # then there are lists to be searched for.
        if len(lists) - index - 2 < end - len(se):
            return False
        # Found all the numbers. 
        if len(se) == end + 1:
            return True
        # Check the options and return if any of them is True.
        # `any` will make sure it won't continue searching if
        # it already has found a True.
        return any(
            find_range_inner(index + 1, se | {el})
            for el in lists[index]
            if el not in se
        )
    return find_range_inner(0, set())


if __name__ == '__main__':
    li = [
        [0, 2],
        [0, 1],
        [3]
    ]
    end = 3
    print(find_range(end, li))
    li.append([1, 2])
    print(find_range(end, li))

如果找到了解决方案，即使有更多列表，它也会提前返回。此外，它的效率也得到了提高，因为any如果在迭代中发现“any”为True，它将直接停止进一步的迭代

Answer 2

这可以递归完成，但有更好的方法。标准库有一个函数可以实现这一点：itertools.product（请参见https://docs.python.org/3/library/itertools.html#itertools.product）

import itertools

def calLen(lists):
    count = 0
    for my_array in itertools.product(*lists):
        my_set = set(my_array)
        if len(my_set) > 7:
            count += 1
    print(count)
    if count > 0:
        return True
    else:
        return False

也许可以举一个简单的例子来说明itertools.product的作用：

>>> for combination in itertools.product([1, 2], ['a', 'b', 'c']):
    print(combination)

    
(1, 'a')
(1, 'b')
(1, 'c')
(2, 'a')
(2, 'b')
(2, 'c')