Solved

Create a powerset in Java

Posted on 2011-02-17
6
1,137 Views
Last Modified: 2013-12-14
Hi,

 In Java I want to create a powerset, when i give  a set and a number for the size for e.g.

{1,2,3,4} set:3
------------------
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}

or
{1,2,3} set 2
{1,2}
{1,3}
{2,3}

thanks
0
Comment
Question by:kimia_az
  • 4
6 Comments
 
LVL 47

Accepted Solution

by:
for_yan earned 500 total points
ID: 34922615
0
 
LVL 47

Expert Comment

by:for_yan
ID: 34922622
This implementation is for all sets, I guess it is easy to modify only limiting to
certain size
0
 
LVL 92

Expert Comment

by:objects
ID: 34922645
0
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

 
LVL 47

Assisted Solution

by:for_yan
for_yan earned 500 total points
ID: 34922653

This will print only sets of 2 out of {1,2,3}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SetUtils {
    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){
    Set<Integer> mySet = new HashSet<Integer>();
    mySet.add(1);
    mySet.add(2);
    mySet.add(3);
    for (Set<Integer> s : SetUtils.powerSet(mySet)) {
        if(s.size() == 2)
        System.out.println(s);
    }

    
}
}

Open in new window

0
 
LVL 47

Expert Comment

by:for_yan
ID: 34922911

This will print only sets of 3 out of {1,2,3,4}  a little bit nicer:


import java.util.*;

public class SetUtils {
    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 <T> Set<Set<T>> powerSet1( Set<T>mySet, int n){
                  Set<Set<T>> sets1 = new  HashSet<Set<T>>();
           Set originalSet =  SetUtils.powerSet(mySet);
            Iterator it = originalSet.iterator();
            while(it.hasNext()) {
                Set s = (Set) it.next();
                if(s.size() == n)sets1.add(s);
            }


            return sets1;
        }


    public static void main(String[] args){
    Set<Integer> mySet = new HashSet <Integer>();
    mySet.add(1);
    mySet.add(2);
    mySet.add(3);
     mySet.add(4);    
    for (Set <Integer> s : SetUtils.powerSet1(mySet, 3)) {
               System.out.println(s);
    }

    
}
}

Open in new window

0
 
LVL 4

Expert Comment

by:msk_apk
ID: 34923511
int setLength = 3;
		int[] array = new int[]{1,2,3,4};
		for(int i=0;i<array.length-2;i++)
		{			
			for(int j=i+1;j<array.length -1;j++)
			{
				for(int k=j+1;k<array.length;k++)
				{
					int[] temp = new int[setLength];
					temp[0] = array[i];
					temp[1] = array[j];
					temp[2] = array[k];
					
					System.out.println(temp[0]+","+temp[1]+","+temp[2]);
				}
			}
		}

Open in new window

0

Featured Post

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
V.simple question about Android packages and libraries 1 19
custom annotations 9 38
difference of if loops 23 49
java stored proc example 9 29
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

776 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question