我试图找到一种方法使这个函数返回组n的k大小的所有子集的2D列表 . N> = K .
该函数接受2个数,n,k,因此n> = k . 并返回组{1,2,...,n-1}的k大小的子集的所有可能性 .
例如,如果参数是:fill_k_subsets(3,2),
该函数将输出:[[0,1],[0,2],[1,2]]
这是所有可能的长度为2的子集,来自组{0,1,2} = {0,1,(3-1)} = {1,..,(n-1)}希望它足够清楚 .
诀窍是,使这项工作不通过部分列表或任何列表一般,也不是元组,字典等,或子集到任何递归函数或主函数传递列表变量或子集到非递归是允许的 . 我很高兴听到一些想法 . 非常感谢 .
def fill_k_subsets(n,k):
"""
this is the main function, can't accepts more parameters other then k and n.
accepts n,k natural numbers, and an empty list
all subsets of size k should be stored inside of the empty list
the function does not return or print anything
:param n:
:param k:
:param list:
:return:
"""
if k <= n:
set_list= list
current_subset = [False] * n
k_fill_helper(current_subset, k, 0, 0, set)
def k_fill_helper(current_subset,k,index,choose):
#this is the recursive function.
#not allowed to accepts any list as a parameter, nor part of the subset
# base case, if chose k items
if k == choose:
fill_set_list(current_subset, set_list)
return None
# if we reached to the end of the list
if index == len(current_subset):
return None
# all subset that that include this index
current_subset[index] = True
k_fill_helper(current_subset, k, index + 1, choose + 1)
# all subset without that index
current_subset[index] = False
k_fill_helper(current_subset, k, index + 1, choose)
def fill_set_list(current_subset,set_list):
work_list=[]
for index, bool_element in enumerate(current_subset):
if bool_element is True:
work_list.append(index)
set_list.append(work_list)