时间戳

首页 > 解决方案 > 如何使用递归返回集合的所有大小为 k 的子集？

java - 如何使用递归返回集合的所有大小为 k 的子集？

问题描述

我正在完成一项实验任务，其中我需要使用递归返回特定大小 k 的所有子集。该函数接受集合 S 和这个 k 值。我在 Java 中这样做；我已经看到了这个问题的答案，但它们是用 C 语言编写的，我正在努力在两种语言之间建立联系。

我已经编写了一个函数来使用递归查找给定集合 S 的幂集，并了解该代码的工作原理（如下所示）。我在找出这个问题的基本和递归案例方面最努力，所以我在编写有效的代码方面并没有真正取得任何成功。对于这个问题，我们不允许从我们已经编写的函数中创建一个幂集，然后选择正确大小的子集；我们必须更有效地做到这一点。

public static Set<Set<String>> allSubsets(Set<String> s) {
    Set<Set<String>> pSet = new HashSet<>();
    Set<String> temp = new HashSet<>();
    temp.addAll(s);

    // base case
    // if temp is empty set, add the empty set to the powerset
    if (temp.isEmpty()) {
        pSet.add(temp);
    }

    // recursive case
    else {
        Iterator<String> itr = temp.iterator();
        String current = itr.next();
        temp.remove(current);
        Set<Set<String>> pSetTemp = allSubsets(temp);
        for (Set<String> x : pSetTemp) {
            pSet.add(x);
            Set<String> copySubset = new HashSet<>();
            copySubset.addAll(x);
            copySubset.add(current);
            pSet.add(copySubset);
        }
    }

    return pSet;

}

就像我说的，这段代码有效，我只是无法解决实验室的第二部分要求找到特定大小 k 的子集的函数。

标签： javarecursionset

解决方案

这是 JavaScript 中的一个示例，应该会给您一些提示。

function f(S, k){
  if (S.size == k)
    return [S]
  if (k == 0)
    return [new Set]

  let result = []

  for (let e of S){
    S.delete(e)
    let smaller = f(new Set(S), k - 1)
    for (let s of smaller){
      s.add(e)
      result.push(s)
    }
  }

  return result
}

var S = new Set([1, 2, 3, 4, 5])

console.log(JSON.stringify(
  f(S, 3).map(s => Array.from(s))))

推荐阅读