算法 - 组合和排列

Question

一个hwk问题,显然也是一个常见的面试问题,我遇到了麻烦:

" 编写一个算法(伪代码),打印出一组n个元素中三个元素的所有子集. 这个元素的元素存储在一个列表中,该列表是算法的输入."

因此,例如,如果S = {1,2,3,4},算法将打印出这四种组合:

123 124 134 234

谁能提出他们的想法/解决方案？

Answer 1

递归:

def subset (prefix, list, count):
    if count is 0:
        print prefix
        return
    for each element in list:
        subset (prefix & element, list beyond element, count - 1)

subset ("", {1,2,3,4}, 3)

Python概念证明:

def subset (prefix, list, count):
    if count is 0:
        print prefix
        return
    for i in range (len(list)):
        subset ("%s%s"%(prefix,list[i]), list[i+1:], count - 1)

subset ("", "1234", 3)

哪个输出,输入字符串的各种值(第二个参数subset):

123456   12345   1234   123   12
------   -----   ----   ---   --
123      123     123    123
124      124     124
125      125     134
126      134     234
134      135
135      145
136      234
145      235
146      245
156      345
234
235
236
245
246
256
345
346
356
456