0

我正在尝试递归地找到一个集合的幂集，然后打印我非常坚持的结果，任何帮助将不胜感激。

public static ArrayList<String> getpowerset(int a[],int n, ArrayList<String> power){
    if(n<0)
    {
        return null;
    }

    if(n==0)
    {
        if(power==null)
            power=new ArrayList<String>();
        power.add(" ");
        return power;
    }

    power=getpowerset(a, n-1, power);
    ArrayList<String> tmp=new ArrayList<String>();
    for(String s:power)
    {
        if(s.equals(" "))
            tmp.add(""+a[n-1]);
        else
            tmp.add(s+a[n-1]);
    }

    power.addAll(tmp);
    return power;
for (int i = 0; i<power.size();i++){
    System.out.println(power);
    }
4

1 回答 1

2

尝试递归思考：

  • 基本情况）空集的幂集是空集
  • 推荐。case) 这样 [ firstElemnt] +的列表restOfTheList的restOfTheList幂集是restOfTheList与firstElemnt

例子：

给定一个列表 [a,b,c]：

  • [] -> [[]] 的幂集（用空集设置）
  • [a] -> [[], [a] ] 的幂集（添加a到前一个幂集的每个元素）
  • [a,b] -> [[], [a], [b], [a,b] ] 的幂集（添加b到前一个幂集的每个元素）
  • [a,b,c] -> [[], [a], [b], [a,b], [c], [a,c], [a,b,c] ] 的幂集（添加c到前一个 powerset 的每个元素）

算法

public static List<List<String>> powerset(final LinkedList<String> originalSet) {
    final List<List<String>> powerset = new LinkedList<List<String>>();
    //Base case: empty set
    if ((originalSet == null) || (originalSet.size() == 0)) {
        final List<String> set = new ArrayList<String>();
        //System.out.println(set);
        powerset.add(set);
    } else { 
        //Recursive case:
        final String firstElement = originalSet.removeFirst();
        final List<List<String>> prevPowerset = powerset(originalSet);
        powerset.addAll(prevPowerset);
        //Add firstElement to each of the set of the previuos powerset
        for (final List<String> prevSet : prevPowerset) {
            final List<String> newSet = new ArrayList<String>(prevSet);
            newSet.add(firstElement);
            //System.out.println(newSet);
            powerset.add(newSet);
        }
    }
    return powerset;
}

测试

public static void main(final String[] args) {
    final LinkedList<String> originalSet = new LinkedList<String>();
    originalSet.add("a");
    originalSet.add("b");
    originalSet.add("c");
    System.out.println("The powerset of " + originalSet + " is:");
    System.out.println(powerset(originalSet));
}

输出

The powerset of [a, b, c] is:
[[], [c], [b], [c, b], [a], [c, a], [b, a], [c, b, a]]

请注意，我已导入以下类：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
于 2013-12-13T00:19:56.087 回答