算法-组合和排列
算法-组合和排列
提问于 2011-02-15 05:07:01
一个hwk问题，也是一个常见的面试问题，我很难回答：
“编写一种算法(伪码)，它打印出n个元素集的三个元素的所有子集。该集合的元素存储在一个列表中，该列表是该算法的输入。”
例如，如果S= {1,2,3,4}，算法会打印出以下四个组合：
123 124 134 234
有人能给出他们的想法/解决方案吗？
回答 4
Stack Overflow用户
回答已采纳
发布于 2011-02-15 05:16:28
递归地：
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
456Stack Overflow用户
发布于 2011-02-15 05:26:39
Knuth第4卷中的专册2有一个优雅的解决方案。
http://cs.utsa.edu/~wagner/knuth/
编辑:这是分册3A http://cs.utsa.edu/~wagner/knuth/fasc3a.pdf
Stack Overflow用户
发布于 2011-02-15 06:47:10
反复思考。你想要长度3的子集。我能做的是，对于子集中的所有n个子集，我只需要附加长度2到n的所有子集。当考虑长度2时，我不会考虑1到n的任何元素，因为这些元素已经被处理过了。S(3，n) = n.S(2，n+1)；
例如，当n=1时，我将用剩余的元素创建长度为2的所有子集。(2,3)，(3,4)，(2,4)现在附加1 i将得到(1,2,3)，(1,3,4)，(1,2,4)。在创建长度2的子集时，我不会考虑1，所以我只有长度2 (3,4)的一个子集。把这个附加到2得到(2,3,4)，并结合所有我得到的(1,2,3)，(1,3,4)，(1,2,4)，(2,3,4)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5000084
复制相关文章
相似问题
腾讯云开发者
