Нахождение набора мощности универсального c набора

Question

Мне задали вопрос об использовании java обобщений и создании класса Set. Я был в состоянии выполнять другие функции, такие как объединение, пересечение, дополнение и т. Д. c, используя этот класс 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

Вы можете попробовать следующее:

Сначала создать и массив целых чисел с длиной установленной вами основы c, установив каждое целое число в ноль. Имейте в виду, что каждый элемент пронумерован из-за его положения в вашем базисе c set +1, потому что вам нужен пустой элемент, который затем равен нулю. Затем, конечно, сначала создайте набор наборов, который вы собираетесь вернуть в качестве своего powerset. После этого переберите ваш массив целых чисел следующим образом: Создайте набор из текущего целочисленного массива, проанализировав каждое целое число в соответствующем элементе набора. Затем добавьте один к первому целому числу вашего целочисленного массива. Если число превышает длину вашего базового набора c, добавьте его к следующему целому числу вашего массива, установив целое число «переполнение» равным следующему целому числу в массиве + 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]

Хотя это, возможно, не самый элегантный способ решения проблемы, похоже, он работает. Я также не знаю требований этого вопроса. Так что, возможно, этот ответ даже не подходит.