在Java中获取指定大小的子集的幂集

Question

我正在尝试找到一种高效的方法来生成一个集合的幂集，其中包含特定大小k的子集。我已经找到了如何生成所有幂集和范围内的幂集的答案，但是如果我只想要一个确定大小的幂集，我不确定该怎么做。谢谢！

- user5188892

---

你有没有尝试过做这件事？也许你的实现方式不够高效？ - Sesame

集合中有多少个元素？ - user3386109

@Sesame，我目前使用的方法是生成整个幂集，然后遍历它并删除不符合我想要长度的子集。 - user5188892

通常情况下，“公式”为2^S = flatten([[x U Y for Y in 2^(S-{x})] for x in S])。您想要大小为n的子集，因此您希望每个Y的大小为n-1。因此，只需使用现有实现并向函数添加额外的大小参数，并在递归调用时使用size-1即可。 - Alex Hall

@user3386109，该集合包含2到31个元素。我想生成长度为3的子集。 - user5188892

Answer 1

创建一个包含集合元素的列表。

创建第二个列表，仅由1和0组成，其中：

- 列表中元素的总数等于集合中元素的数量 - 列表中1的数量等于k

对于第二个列表的每个排列，子集由第一个列表中相应条目为1的元素组成。

- user3386109

---

不是排列，而是组合。集合中的元素没有顺序。 - someguy

@someguy 创建一个列表（list），而不是集合（set），并计算列表的所有排列组合。 - user3386109

底层数据结构并不重要。你想要所有大小为 k 的组合而非排列。例如，集合 {x, y} 只有一个大小为 2 的子集。您的方法会返回两个子集，好像 {x, y} 和 {y, x} 是不相等的一样。 - someguy

@someguy，我猜我们对排列的定义有所不同。例如，我将 {0,1,1} 的排列定义为 {{0,1,1}, {1,0,1}, {1,1,0}}。请参见此答案，其中提供了一种计算数组排列而没有重复项的方法。 - user3386109

排列的定义是没有争议的，它是一个数学概念！你的例子有缺陷，因为那个“集合”实际上并不是一个集合。元素必须是唯一的。如果它们是唯一的，你会发现实际上有6种不同的排列方式。然而，正如我所说，我们感兴趣的是不同的组合，而不是排列。请阅读这篇小文章：https://en.wikipedia.org/wiki/Power_set#Relation_to_binomial_theorem。这是基本的集合/概率理论。 - someguy

此外，如果您想要这个问题的真正答案，请查看我在评论中发布的链接。为了方便：https://dev59.com/9nVC5IYBdhLWcg3w-mVO。 - someguy

Answer 2

这个方法通过将集合转换为列表，并迭代所有可能的索引组合来实现。

static <E> Set<Set<E>> subsets(Set<E> set, int n) {
    if (n < 0)
        throw new IllegalArgumentException();
    Set<Set<E>> temp = new HashSet<>();
    int size = set.size();
    if (n > size)
        return temp;
    List<E> list = new ArrayList<>(set);
    int[] indices = new int[n];
    for (int i = 0; i < n; i++)
        indices[i] = i;
    while (true) {
        Set<E> s = new HashSet<>();
        for (int i : indices)
            s.add(list.get(i));
        temp.add(s);
        int r = n - 1;
        for (int m = size; r >= 0 && indices[r] == --m; r--);
        if (r == -1)
            return temp;
        for (int c = indices[r]; r < n;)
            indices[r++] = ++c;
    }
}

- Paul Boddington

Answer 3

你可以使用简单的回溯算法来实现这个功能。你只需要遍历每个元素，然后选择将该元素包含在你的子集中或者不包含。同时，你可以记录当前正在构建的子集（current_subset）以及还可以选择多少个元素（k）。以下是一个示例实现：

static <E> void backtrack(int index, int k, Deque<E> current_subset,
                          List<E> elements) 
{
    if (k == 0) {
        System.out.println(current_subset);
        return;
    }
    if (index == elements.size())
        return;
    current_subset.push(elements.get(index));
    backtrack(index + 1, k - 1, current_subset, elements);
    current_subset.pop();
    backtrack(index + 1, k, current_subset, elements);
}

backtrack(0, 2, new ArrayDeque<Integer>(), 
          Arrays.asList(new Integer[]{0, 1, 2, 3, 4}));
/*
[1, 0]
[2, 0]
[3, 0]
[4, 0]
[2, 1]
[3, 1]
[4, 1]
[3, 2]
[4, 2]
*/

请注意，如果您想保留子集，可以将它们插入到某个结构（例如List）中，而不是打印它们。

- sve

Answer 4

尝试这个方法以生成一个集合的幂集：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class GeneratePowerSet {

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }
        List<T> list = new ArrayList<>(originalSet);
        T head = list.get(0);
        Set<T> rest = new HashSet<>(list.subList(1, list.size()));
        for (Set<T> set : powerSet(rest)) {
            Set<T> newSet = new HashSet<>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

    public static void main(String args[]) {
        Set<Integer> mySet = new HashSet<Integer>();
        mySet.add(1);
        mySet.add(2);
        mySet.add(3);
        mySet.add(4);
        for (Set<Integer> s : powerSet(mySet)) {
            System.out.println(s);
        }
    }

}

更多信息，请访问https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/GeneratePowerSet.java。希望能对您有所帮助。

- Mohammad