Java中的组合组合

Question

Java中的组合组合

javaalgorithmmathcombinatoricscombinations

3

我需要在JAVA中找到组合的组合。

例如，我班上有6个学生。从中选择4人组成小组，并为每个小组选择一个亲密小组，以此创建组合。

我必须确保没有重复（顺序不重要）。并且需要打印出这4个人的小组。

然而，这是困难的一部分：

因此，将学生定义为数字：

如果我打印1234作为其中一个组合，我不能也打印1256，因为12既出现在1234中，也出现在1256中。

如何在Java中编写它？

编辑过的内容

（[1,2,3,4,5]，3，2）的输出结果将是：

没有重复的组合（n = 5，r = 3） {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5}
删除重复的2元素组，只会留下： {1,2,3} {1,4,5}（我删除了那些已经出现在前两个组合中的12、13、23、45、14、15的组合）。

- Dejell

2

对于所有沉迷于作业的人：她有点年龄大了 :) - Nikita Rybak

2

给_Odelya_：你能否发布6个学生（或更少）的预期输出？我现在不确定如何解释问题（特别是关于“亲密”小组的问题）。 - Nikita Rybak

2

只是为了确保我理解：给定N个项目，您想生成一些大小为M的子集S集合，使得一个子集中的任意两个项目都不出现在其他子集中？那么S的大小如何？此外，解决方案并不唯一。 - Eyal Schneider

1

@Odelya：例如对于N=5，M=4和Z=2，解的大小为1（例如{{1,2,3,4}}），因为任何两个大小为4的子集至少有2个项目的交集。对吧？ - Eyal Schneider

1

@Odelya，你提供的解释含糊不清，因为最终结果取决于步骤1中生成组合的顺序。例如，如果我按相反的顺序迭代组合，最终结果将是{3,4,5} {1,2,5}。您可能希望定义一个严格的迭代顺序，以使结果明确无误。 - Péter Török

显示剩余8条评论

2个回答

0

假设你有一个学生对象，其中使用equals比较他们的主键。在你的例子中，学生1将返回1，2将返回2，依此类推。

将它们全部放入集合中，这将确保不会有重复。

遍历整个集合，先以4为步长，再以2为步长，就能得到你想要的结果。

- mezzie

我需要以最有效的方式返回4个元素的集合，其中没有2个相同的元素。我认为你的方法不是理想的。 - Dejell

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikita Rybak · Accepted Answer

好的，这里是您所描述过程的简单模拟。但我使用二进制数字来表示集合，这样操作更容易。例如，数字19在二进制形式下为10011：这意味着选择了学生0、3和4（这些位置上有1）。

首先是一个小助手。

// return all subsets of 'set', having size 'subsetSize'
Set<Integer> allSubsets(int set, int subsetSize) {
    Set<Integer> result = new HashSet<Integer>();
    if (subsetSize == 0) {
        result.add(0);
        return result;
    }
    if (set == 0) {
        return result;
    }

    // check if 1st element is present
    if (set % 2 == 1) {
        // use 1st element, one less element to collect
        for (Integer i : allSubsets(set / 2, subsetSize - 1)) {
            result.add(i * 2 + 1);
        }
    }
    // not use 1st element
    for (Integer i : allSubsets(set / 2, subsetSize)) {
        result.add(i * 2);
    }

    return result;
}

还有主程序。欢迎提出建议。

    int N = 5;
    int M = 3;
    int Z = 2;

    List<Integer> result = new ArrayList<Integer>();

    // get all groups of M elements from 'wholeSet'
    int wholeSet = (1 << N) - 1;
    for (int s : allSubsets(wholeSet, M)) {
        // Check all subsets of 'Z' elements from set 's'
        boolean valid = true;
        for (int t : allSubsets(s, Z)) {
            // check if this Z-element subset already was used
            for (int past : result) {
                // check if 't' is subset of 'past' set
                if ((past|t) == past) {
                    valid = false;
                    break;
                }
            }
            if (!valid) {
                break;
            }
        }

        if (valid) {
            // none of Z-element subsets of 's' were used before
            result.add(s);
        }
    }

但是对于大量的输入可能需要进行改进（例如记忆化）。但目前来看，由于您没有说明期望的输入类型，我认为这已经足够好了。