python - 使用递归打印 n 选择 k 组合算法

Question

这一定是一个经典的面试问题，但是，我在理解它时遇到了问题。

下面是我在 Python 中的实现，如果你运行它，它只会打印 ab, ac, ad。它不会进入 'b' (bc, bd) 级别。

def Print_nCk (the_list, k, str_builder, used):
    if len(str_builder) == k:
        print str_builder
        return 
    else:
        for i in xrange(len(the_list)):
            if used[i] !=True:
                str_builder+=the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used)
                str_builder = str_builder[:-1]


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

正确答案是 ab,ac,ad,bc,bd,cd 当上面一行通过时。

我从这里知道正确的实现而不使用 used 参数(http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/)但是我的问题是我的实现有什么问题？

你能解释一下吗？

为了调试，我每次都打印出“used”。 used 参数在打印“ad”后变为 (True, True, True, True) 然后它不会比这更深。如果我坚持使用 used，修复 used 的聪明方法是什么？

Answer 1

当您回溯时，您忘记了取消设置used[i]:

def Print_nCk (the_list, k, str_builder, used):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(len(the_list)):
            if used[i] != True:
                str_builder += the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used)
                str_builder = str_builder[:-1]
                <b>used[i] = False</b>


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

在您当前的实现中，从您选择 i 的那一刻起，您就将 used[i] 设置为 True > 作为值(value)。但是，如果稍后您决定选择另一个分支，您应该正确地进行簿记，从而取消设置 used[i]。

请注意，现在将生成 "ab" 和 "ba"。因此，您可以生成具有对称性的组合。如果您不想这样，您可以使用一个附加参数。这确保您不会使用低于先前选择的索引:

def Print_nCk (the_list, k, str_builder, used<b>, prev = 0</b>):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(<b>prev,</b>len(the_list)):
            if used[i] != True:
                str_builder += the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used, <b>i+1</b>)
                str_builder = str_builder[:-1]
                used[i] = False


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

然而，这或多或少违背了使用“已用”数组的目的。您可以简单地使用 prev:

def Print_nCk (the_list, k, str_builder, prev = 0):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(<b>prev,</b>len(the_list)):
            str_builder += the_list[i]
            Print_nCk(the_list, k, str_builder, i+1)
            str_builder = str_builder[:-1]


Print_nCk(['a','b','c','d'], 2, "")

然后打印:

>>> Print_nCk(['a','b','c','d'], 2, "")
ab
ac
ad
bc
bd
cd