1

为了获得列表的幂集，我实现了以下内容：

public static ArrayList<ArrayList<Integer>> getAllSubsets(ArrayList<Integer> set, int index, ArrayList<Integer> subset){
    ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();

    if(index == set.size()){
        subsets.add(new ArrayList<Integer>(subset));
        return subsets;
    }

    subsets.addAll(getAllSubsets(set, index + 1, subset));
    subset.add(set.get(index));
    subsets.addAll(getAllSubsets(set, index + 1, subset));
    subset.remove(subset.size()-1);
    return subsets;
}

这是使用递归获取列表幂集的最佳方法吗？我已经看到了很多关于如何在互联网上实现这一点的不同方法，但它们似乎比我的复制（使用新的）更多。

例如，这个StackOverlow 帖子出现在我的 Google 搜索中，但他的实现 (Joao Silva) 使用了大量的复制，并且似乎不是最佳的。但是，我经常看到他的实现，这让我很困惑。该实现是否比我正在使用的更好（当然，他正在使用泛型这一事实）？

他的代码：

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

1 回答 1

2

您可能会发现此页面很有用。它包含各种语言和使用不同方法的 powerset 实现。对于Java，有三种方法：

  1. 迭代
  2. 递归的
  3. 并使用二进制字符串

其实我最喜欢第三种方式，因为里面有好主意。不同之处在于，他们假设输入是一个String.

顺便提一句。如果要在生产中使用任何代码，我宁愿避免使用递归，因为堆栈可能存在问题（不幸的是，Java 中仍然不支持尾递归）

于 2013-07-26T22:09:10.350 回答