算法 - 组合和排列

Question

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

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

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

123124134234

任何人都可以提供他们的想法/解决方案吗？

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