有可能用递归技术写一个组合函数吗?

Question

昨天，我遇到了一个问题，需要在一个范围为5的可迭代对象中计算组合。

我没有使用itertools.combination，而是尝试自己创建一个原始函数。它看起来像:

def combine_5(elements):
    """Find all combinations in elements with range 5."""
    temp_list = []
    for i in elements:
        cur_index = elements.index(i)
        for j in elements[cur_index+1 : ]:
            cur_index = elements.index(j)
            for k in elements[cur_index+1 : ]:
                cur_index = elements.index(k)
                for n in elements[cur_index+1 : ]:
                    cur_index = elements.index(n)
                    for m in elements[cur_index+1 : ]:
                        temp_list.append((i,j,k,n,m))
    return temp_list

然后我想也许我可以把它抽象一点，得到一个combine_n函数。下面是我最初的蓝图:

# Unfinished version of combine_n
def combine_n(elements, r, cur_index=-1):
    """Find all combinations in elements with range n"""
    r -= 1 
    target_list = elements[cur_index+1 : ]
    for i in target_list:
        cur_index = elements.index(i)
        if r > 0:
            combine_n(elements, r, cur_index)
            pass
        else:
            pass

然后我被困在那里一整天，主要的问题是我不能在递归函数中正确地传递值。我添加了一些代码来修复一个问题。但当它适用于每个递归循环时，新的问题就出现了。更多的修复导致更多的错误，形成一个恶性循环。

然后我去itertools.combination的源代码寻求帮助。它没有使用递归技术。

你认为有可能用递归技术将这个combine_5函数抽象成combine_n函数吗?你对它的实现有什么想法吗?

---

故障示例1:

def combine_n(elements, r, cur_index=-1):
    """Find all combinations in elements with range n"""
    r -= 1 
    target_list = elements[cur_index+1 : ]
    for i in target_list:
        cur_index = elements.index(i)
        if r > 0:
            combine_n(elements, r, cur_index)
            print i
        else:
            print i

这是我最近的尝试，经过一堆过于复杂的实验。
核心思想是:如果我可以正确打印它们，我可以稍后将它们收集到容器中。但问题是，在嵌套的for循环中，当下层for循环命中空列表时。
combine_5的temp_list.append((i,j,k,n,m))条款不起作用。
但是在FAILURE SAMPLE 1中，它仍然会打印上面for循环的内容
如combine_n([0,1]， 2)将打印2, 1, 2 .
我需要找到一种方法将这个空消息传递给上级for循环。
到目前为止我还没弄明白。

Answer 1

是的，可以通过递归来实现。您可以使combine_n返回一个元组列表，其中包含从索引cur_index开始的所有组合，并从cur_combo的部分组合开始，这是您在递归时构建的:

def combine_n(elements, r, cur_index=0, cur_combo=()):
    r-=1
    temp_list = []
    for elem_index in range(cur_index, len(elements)-r):
        i = elements[elem_index]
        if r > 0:
            temp_list = temp_list + combine_n(elements, r, elem_index+1, cur_combo+(i,))
        else:
            temp_list.append(cur_combo+(i,))
    return temp_list
elements = list(range(1,6))
print = combine_n(elements, 3)

输出:

[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]

for循环只执行到len(elements)-r，因为如果再执行，则没有足够的剩余元素来填充元组中剩余的位置。元组只在递归的最后一层使用append添加到列表中，然后通过返回temp_lists并在每一层连接到顶部，将它们传递回调用堆栈。