是否有通过过滤某些子组从一个主要组中查找所有子组的功能？

Question

我正在使用 java 编写代码，所以如果您可以与 java 共享代码，那就太好了:)

假设我有一组 (1,2,3,4,5)，我想创建该组的所有子组，其最大大小为给定的自然数（例如 3）。

我已经找到了 returns 所有子组的代码但是，在我的项目中我的组大小可以达到 40 因此我需要花费太多时间来计算并且它非常有问题。我也更喜欢它是一个函数而不是一个对象。效率也很重要，我不能创建所有可能的组然后过滤掉它们。

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<>());
            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;
    }

我在这里找到了它： Obtaining a powerset of a set in Java.

Answer 1

我大学的时候也研究过类似的问题，看一下：

  static Set<String> setA = new HashSet<>();

  public static Set<String> permutation(String prefix, String str, int len) {
    int n = str.length();
    if (prefix.length() == len) {
      setA.add(prefix);
    } else {
      for (int i = 0; i < n; i++) {
        permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), len);
      }
    }
    return setA;
  }

以上将 return String str = 12345 与大小 int len=3 的所有可能组合，现在你的工作是过滤唯一元素，因为 123 等于 312 来自 Powerset 定义。

  public static void main(String[] args) {
    Set<String> setB = new HashSet<>();
    setB.addAll(permutation("", "12345", 3));
    Set<String> collect = setB.stream().map(
        s -> {
          Optional<String> reduce = Arrays.stream(s.split("")).sorted(Comparator.naturalOrder())
              .reduce((a, b) -> a + b);
          return reduce.get();
        })
        .collect(Collectors.toSet());
    System.out.println(collect);
  }

这应该毫无疑问地工作，如果您有任何疑问，请告诉我。

完整代码，我在 Github: https://github.com/vishwaratna/Practice-Codes/blob/master/src/main/java/BenchmarkingWithJMH.java

Answer 2

我看了你的代码，稍微调整了一下。

您现在输入内部集合的最大大小，它将是最大集合的大小。

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet, int size) {
        Set<Set<T>> sets = new HashSet<>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<>());
            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, size)) {
            if(set.size() <= size-1 ){
                Set<T> newSet = new HashSet<>();
                newSet.add(head);
                newSet.addAll(set);
                sets.add(newSet);
                sets.add(set);
            }

        }

        return sets;
    }

是否有通过过滤某些子组从一个主要组中查找所有子组的功能？

Is there a function for finding all subgroups from one main group with filtering some of the subgroups?

java

set

powerset