这一定是一个经典的面试问题,但是,我在理解它时遇到了问题。
下面是我在 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
的聪明方法是什么?
最佳答案
当您回溯时,您忘记了取消设置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
关于python - 使用递归打印 n 选择 k 组合算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44914234/