查找通用集的幂集

Question

我被问到一个利用Java泛型并创建Set类的问题。使用此Set类，我已经能够执行其他功能，例如并集，交集，补码等。

但是我一直面临的问题是找到所有电源。我需要退还一套（即动力套）。从昨天开始，我一直在尝试解决此问题，但无济于事。我尝试实现二进制方法来查找功率集。到目前为止，我所做的一切都是基于问题的要求！

public class Set<T extends Comparable> {

private ArrayList<T> theSet;

public Set(T[] theElements){
    theSet = new ArrayList<>();
    for(int i=0; i < theElements.length; i++){
        if(!checker(theElements[i]))
            theSet.add(theElements[i]);
    }
}

public ArrayList<T> getTheSet() {
    return theSet;
}

public Set powerSet(){
    long powerSetSize = (long)Math.pow(2, theSet.size());
    int counter, j;
    Set[] powerSet = new Set[(int)Math.pow(2, theSet.size())];
    T[] currentArray = null;

    for(counter=0; counter<powerSetSize; counter++){
        for(j=0; j<theSet.size(); j++){
            currentArray = (T[]) new Comparable[j+1];
            if((counter & (1 << j)) > 0)
                currentArray[j] = theSet.get(j);
        }
        powerSet[counter] = new Set<>(currentArray);
    }

    return new Set<>((T[])powerSet);
}

public String toString(){
    String str = "{";
    for(int i=0; i<theSet.size(); i++){
        if(i < theSet.size()-1)
            str += theSet.get(i)+", ";
        else
            str += theSet.get(i)+"}";
    }
    return str;
}

}

Answer 1

您可以尝试以下操作：

首先使用基本集合的长度创建和整数数组，将每个整数设置为零。请记住，每个元素都根据其在基本集合+1中的位置进行编号，因为您需要一个空的元素，然后该元素为零。然后，当然要先创建一组Set，然后将其作为幂集返回。之后，按以下步骤遍历整个Integer数组：通过将每个Integer解析为其对应的Set元素，从当前Integer-Array中创建一个Set。然后将一个添加到Integer-Array的第一个Integer中。如果该数字大于基本Set的长度，则将其添加到数组的下一个整数，并将“溢出”整数设置为等于数组+1中的下一个整数。]

这将使您可以循环选择电源集的所有可能组合，并将它们添加到电源集中。

public Set<Set<T>> powerSet(){
    int[] num = new int[list.size()];
    Arrays.fill(num,0);
    Set<Set<T>> powerSet = new Set<>();
    do{
        powerSet.list.add(parse(num));
    }while (addNum(num)); //Loops through every possibility 
    powerSet.list.add(parse(num)); 
    //Because the method returns false when this was the last possible increment
    return powerSet;
}

//Transforms a int[] into the corresponding Set
private Set<T> parse(int[] e){
    Set<T> s = new Set<>();
    for (int i = 0; i < e.length; i++) {
        if(e[i]!=0){
            s.list.add(list.get(e[i]-1)); //Every Element has its number
        }
    }
    return s;
}

//Increments the counter
//Returns false if this was the last possible increment
private boolean addNum(int[] e){
    e[0]++;
    for (int i = 0; i < e.length; i++) {
        if(e[i]>e.length-i){
            e[i] = 0;
            e[i+1]++;
        }
    }
    for (int i = e.length-1; i != 0; i--) {
        if(e[i]>=e[i-1]&&e[i]!=0){
            e[i-1] = e[i]+1;
        }
    }
    if(e[e.length-1]==1){
        return false;
    }
    return true;
}
[3,43,65,32]的输出（打印出功率集的每组）：

[]
[3]
[43]
[65]
[32]
[43, 3]
[65, 3]
[32, 3]
[65, 43]
[32, 43]
[32, 65]
[65, 43, 3]
[32, 43, 3]
[32, 65, 3]
[32, 65, 43]
[32, 65, 43, 3]
尽管这可能不是解决问题的最优雅的方法，但似乎可行。我也不知道这个问题的要求。因此，也许这个答案甚至不合适。