算法 - 组合和排列
一个 hwk 问题,显然也是一个常见的面试问题,我遇到了麻烦:
“编写一个算法(伪代码),打印出一组 n 个元素的三个元素的所有子集。 的元素该集合存储在一个列表中,该列表是算法的输入。”
例如,如果 S = {1,2,3,4},算法将打印出这四种组合:
123 124 134 第234章
谁能提供他们的想法/解决方案?
A hwk question and apparently also a common interview question I'm having trouble with:
"Write an algorithm (pseudocode) that prints out all the subsets of three elements of a set of n elements. The elements of this set are stored in a list that is the input to the algorithm."
So for example if S = {1,2,3,4} the algorithm would print out these four combinations:
123
124
134
234
Can anyone offer their thoughts / a solution?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
递归地:
Python 概念证明:
对于输入字符串的各种值(
subset
的第二个参数),其输出:Recursively:
A Python proof of concept:
which outputs, for various values of the input string (second parameter to
subset
):Knuth 的第 4 卷第 2 卷有一个优雅的解决方案。
http://cs.utsa.edu/~wagner/knuth/
编辑:它是分册3A
http://cs.utsa.edu/~wagner/knuth/fasc3a.pdf
Knuth's fascile 2 from volume 4 has an elegant solution.
http://cs.utsa.edu/~wagner/knuth/
Edit: it is fascicle 3A
http://cs.utsa.edu/~wagner/knuth/fasc3a.pdf
递归地思考。您想要长度为 3 的子集。我能做的是,对于子集中的所有 n,我将简单地将长度为 2 的所有子集附加到 n。在考虑长度 2 时,我不会考虑 1 到 n 的任何元素,因为这些元素已经被处理过。
对于所有 n,S(3,n) = nS(2,n+1);
例如,当 n = 1 时,我将使用剩余元素创建长度为 2 的所有子集。 (2,3),(3,4),(2,4)。现在附上 1,我将得到 (1,2,3),(1,3,4),(1,2,4)。我将继续 2。只有 2 在创建长度为 2 的子集时,我不会考虑 1。所以我只有一个长度为 2 (3,4) 的子集。将其附加到 2 我得到 (2,3,4) 并结合我得到的所有内容
(1,2,3),(1,3,4),(1,2,4),(2,3,4)。
Think recursively. You want subsets of length 3. What I can do is that for all n in subsets I will simply attach all the subsets of length 2 to n. While considering the length 2 I will not consider any elements for 1 to n, as these are already processed.
S(3,n) = n.S(2,n+1) for all n;
e.g. when n = 1, I will create all the subsets of length 2 with remaining elements. (2,3),(3,4),(2,4). Now attaching 1 I will get (1,2,3),(1,3,4),(1,2,4). I will continue this for 2. Only that for 2 while creating the subsets of length 2 I will not consider 1. So I have only one subset of length 2 (3,4). Attaching this to 2 I get (2,3,4) and combining all I get
(1,2,3),(1,3,4),(1,2,4),(2,3,4).
我首先尝试解决 S = {1,2,3,4} 且 n=3 时的特定情况,但后来我决定只对 S = m 个元素的列表和 n 任意数字 >= 进行解决1.另外,这是我用 Java 编写的第一个程序:)所以我希望你喜欢!
I first tried to solve it for the specific case when S = {1,2,3,4} and n=3, but then I decided to just do it for S = a list of m elements and n an arbitrary number>=1. Also, this is my first program in Java :) so I hope u enjoy!