算法 - 组合和排列

发布于 2024-10-17 19:22:14 字数 219 浏览 7 评论 0原文

一个 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

︶葆Ⅱㄣ 2024-10-24 19:22:14

递归地:

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

Recursively:

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)

A Python proof of concept:

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)

which outputs, for various values of the input string (second parameter to 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
中性美 2024-10-24 19:22:14

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

維他命╮ 2024-10-24 19:22:14

递归地思考。您想要长度为 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).

青衫儰鉨ミ守葔 2024-10-24 19:22:14

我首先尝试解决 S = {1,2,3,4} 且 n=3 时的特定情况,但后来我决定只对 S = m 个元素的列表和 n 任意数字 >= 进行解决1.另外,这是我用 Java 编写的第一个程序:)所以我希望你喜欢!

import java.util.Arrays;

public class Combinari {

    public static void combinari(int[] array, int n, int[] toPrint){
        if(n==1){
            for(int i=0;i<array.length;i++){
                for(int j=0;j<toPrint.length;j++) System.out.print(toPrint[j]);
                System.out.println(array[i]);
            }
        }
        else {
            for(int i=0;i<array.length-n+1;i++){
                int [] newToPrint = Arrays.copyOf(toPrint, toPrint.length+1);
                newToPrint[toPrint.length] = array[i];
                int [] new_array =  Arrays.copyOfRange(array, i+1, array.length);
                combinari(new_array,n-1,newToPrint);
            }
        }
    }



    public static void main(String[] args) {
        int [] array = {1,2,3,4,5,6,7};
        int [] iaka={}; // iaka est for printing :)
        combinari(array, 3, iaka);
        System.out.println("");

    }

}

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!

import java.util.Arrays;

public class Combinari {

    public static void combinari(int[] array, int n, int[] toPrint){
        if(n==1){
            for(int i=0;i<array.length;i++){
                for(int j=0;j<toPrint.length;j++) System.out.print(toPrint[j]);
                System.out.println(array[i]);
            }
        }
        else {
            for(int i=0;i<array.length-n+1;i++){
                int [] newToPrint = Arrays.copyOf(toPrint, toPrint.length+1);
                newToPrint[toPrint.length] = array[i];
                int [] new_array =  Arrays.copyOfRange(array, i+1, array.length);
                combinari(new_array,n-1,newToPrint);
            }
        }
    }



    public static void main(String[] args) {
        int [] array = {1,2,3,4,5,6,7};
        int [] iaka={}; // iaka est for printing :)
        combinari(array, 3, iaka);
        System.out.println("");

    }

}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文