Saturday 12 April 2014

Program to find power set in Java


import java.util.*;
import java.io.*;
import java.util.Map;

public class PowerSet {
    
    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<Set<T>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }
        List<T> list = new ArrayList<T>(originalSet);
        T head = list.get(0);
        Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
        for (Set<T> set : powerSet(rest)) {
            Set<T> newSet = new HashSet<T>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }  
        return sets;
    }
    
    public static void main(String args[])throws Exception{
        
        int num;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        System.out.println("Enter a number to calculate power set");
        num = Integer.parseInt(br.readLine());
        
        Set<Integer> mySet = new HashSet<Integer>();
        
        for(int i = 1; i <= num; i++)
         mySet.add(i);

        long time1 = System.currentTimeMillis();
        Set<Set<Integer>> powSet= PowerSet.powerSet(mySet);
        long time2 = System.currentTimeMillis();
        
        for (Set<Integer> s :powSet ) {
            System.out.println(s);
         }
        
        System.out.println("Total time to calculate power set of Numbers " + num + " is " + (time2-time1) +" milli seconds");
    }
    
    
}




Home

No comments:

Post a Comment