1
\$\begingroup\$
  • Input: Set of elements (String)
  • Output: Printing the elements of the power set of the given set

public class PrintPowerSet {
public static List<String> permuteSet(String inputSet){

    List<String> powerSet = new ArrayList<String>();
    int n = inputSet.length(); //size for binary

    for(int i=0;i<Math.pow(2,n);i++){
        if(i==0){
            powerSet.add("Ø"); //empty set Case
            continue;
        }
        String binaryOfIndex = getBinaryString(i, n);
        StringBuffer subset = new StringBuffer();
        for(int j=0;j<binaryOfIndex.length();j++){
            if(binaryOfIndex.charAt(j)=='1'){
                subset.append(inputSet.charAt(j));
            }
        }
        powerSet.add(subset.toString());
    }
    return powerSet;
}

public static String getBinaryString(int i, int size) {
    String bin = Integer.toBinaryString(i);
    bin = String.format("%0" + size + "d", Integer.parseInt(bin));
    return bin;
}
public static void main(String args[]){
    String set = "gle";
    List<String> result;
    result = permuteSet(set);
    for(String word: result){
        System.out.print(word+" ");
    }
}
}
\$\endgroup\$
1
\$\begingroup\$

The integer to string to integer representation of string to string conversion is very wasteful. You can just do bit shifts.

private static String getSubset(String inputSet, int mask) {
    StringBuffer subset = new StringBuffer();

    for (int i = 0; i < inputSet.length(); i++) {
        // Check if ith bit is set
        if ((mask & (1 << i)) != 0) {
            subset.append(inputSet.charAt(i));
        }
    }

    return subset.toString();
}

public static List<String> permuteSet(String inputSet) {
    List<String> powerSet = new ArrayList<String>();
    int n = inputSet.length(); // size for binary
    int powerSetLength = 1 << n; // you should check that n is small enough

    for (int i = 0; i < powerSetLength; i++) {
        powerSet.add(getSubset(inputSet, i));
    }

    return powerSet;
}

Demo

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.