Question

The Power Set of a set of (distinct) objects S is the set of all subsets of S, including S itself and an empty set. For example, let S be a set of words: S={Hello, World, Students}. Then possible subsets are: {Hello} {World} {Students} {Hello, World} {Hello, Students} {World, Students} {Hello, World, Students} From a course in Discrete Mathematics, you should know that if S contains n elements, then its power set consists of 2^n elements. Please write a recursive algorithm, which will take an array of objects as an input and return an array of arrays of objects as the power set. In the previous example, our objects were strings, and the output was an array of arrays of strings. Right? In order to do that, please develop the following method: public static Object[][] GeneratePowerSet(Object[] arr) Please do not forget to check "boundary cases" and possible invalid inputs like some objects in arr are null. If that happens, your function should print an error message and return null. (Note that in real world programming, I would suggest to throw an exception instead of printing an error message; we will talk about this later in our course.) Please also test the method by feeding it an array of integers and printing out the power set. You can do this for testing: Integer[] my_arr = {-2,7,10,23,19}; Integer[][] pSet = GeneratePowerSet(my_arr); for(int i=0; i System.out.print("{"); for(int j=0; j System.out.print(pSet[i][j]); if(j+1 System.out.print(", "); } System.out.println("}"); } Side Note: Please note that if you want to print out an object (whatever it means) by calling System.out.println(my_object); the toString() method of that object would be called inside println(). It is the same as the following call: System.out.println(my_object.toString()); I encourage you to exercise with toString() method for a simple class ComplexNumber you can easily create: class ComplexNumber { public double Re; public double Im; public ComplexNumber(double x, double y) { super(); this.Re = x; this.Im = y; } public String toString() { // your code inside returning something like (Re,Im) } }

Answer 1

The code is given below along with screenshot. Explanation is given in comments alongside code. Let me know in the comments if you have any doubts.

Code:

import java.util.*;
public class Main
{   
public static Object[][] powerSet(Object[] arr) //Generating power set for array
{   
long p_size=(long)Math.pow(2, arr.length);
Object result[][]=new Object[(int)p_size][]; //Array to store our result and return it
/*
The idea behind this approach is we will first find the number of sets in the power set
which is equal to 2^n where n is the number of elements in the set. Now the approach is as follows
Suppose we want to find the power set for the set {1,2,3}. The number of elements in the powerset
would be 2^3=8. We would run a loop from 0 to 7 i.e. <8. And we would check which bits are set for i
and the bit that is set, we would add that element to our set that would be included in the powerset.
For example, if i=6, then in binary, it would 110, so the elements that would be included in the current set
would be 1 and 2. So, {1,2} would be included in the power set. Similarly for all values of i
  
*/
for(int i=0;i<p_size;i++) //Running loop from 0 to less than size of power set
{ ArrayList<Object> temp=new ArrayList<Object>(); //Creating a temp arrayList to store elements
//that would be included in the current set
  
  
/*
This is the best way to check what bits are set in a number. We would run the inner loop for all the
elements present in our original array and for each index j, we would check if jth bit is set or not is by left shifting
1 by j bits. For example, for j=2, we would left shift bits in 1 by 2 bits which would make it 100. After that,
we would bitwise AND this with our current value of power set counter to see if jth bit is set or not. If the result is
1, it is set, otherwise jth bit is not set.
For example, suppose i is 8 in the current iteration. And value of j is 2.
8 in binary=1000
1<<2 in binary= 4 in binary=0100
1000 & 0100 ==0
So, 2nd element would not be included in the current set as jth bit is not set.
  
*/
  
for(int j=0;j<arr.length;j++)
{   
  
if((i & (1<<j))>0)
temp.add(arr[j]); //If jth bit is set, put in arrayList
  
}
result[i]=temp.toArray(); //Converting arrayList into array and storing it in our result array
}
  
return result; //Returning the result
}
   public static void main(String[] args) {
       Integer myarr[]= {-2,7,10,23,19}; //Creating array for testing
      
       Object[][] pSet = powerSet(myarr); //Calling the function for myarr
       for(int i=0;i<pSet.length;i++) //Printing the power set
       {
       for(int j=0;j<pSet[i].length;j++)
       {
       System.out.print(pSet[i][j]+" ");
       }
       System.out.println();
       }
      
   }
}

Output:

Code for toString method excercise:

class ComplexNumber
{
public double Re;
public double Im;
public ComplexNumber (double x, double y)
{
super ();
this.Re = x;
this.Im = y;
}
  
public String toString ()
{               // your code inside returning something like (Re,Im)
  
return "("+this.Re+" "+this.Im+")"; //We just return the string that we want to print for the object
//In this case, we want to print (Re, Im) when our object is passed in println function, so we just return
// a string in that format
}
  
}
public class Main
{
public static void main (String[]args)
{
ComplexNumber a =new ComplexNumber(10,12);
   System.out.println (a);
}
}
Output: