CODEWITHSUNDEEP
javaalgorithmsetbig-o
user5188892
user5188892

Reputation:

Obtaining the powerset of set with subsets of a certain size in Java

I'm trying to find an efficient manner to generate a powerset of a set that has the subsets of a certain size k. I have found answers of how to generate all powersets and powersets within a range, but I'm not sure how I would do it if I only wanted one certain size.

thanks!

Upvotes: 4

Views: 1537

Answers (4)

Mohammad
Mohammad

Reputation: 6138

Try this to generate the power set of the set: 

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

public class GeneratePowerSet {

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }
        List<T> list = new ArrayList<>(originalSet);
        T head = list.get(0);
        Set<T> rest = new HashSet<>(list.subList(1, list.size()));
        for (Set<T> set : powerSet(rest)) {
            Set<T> newSet = new HashSet<>();
            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);
        mySet.add(4);
        for (Set<Integer> s : powerSet(mySet)) {
            System.out.println(s);
        }
    }

}

For more information, visit https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/GeneratePowerSet.java. I hope it helps.

Upvotes: 0

Paul Boddington
Paul Boddington

Reputation: 37645

This works by converting the set into a list and iterating through all possible combinations of indices.

static <E> Set<Set<E>> subsets(Set<E> set, int n) {
    if (n < 0)
        throw new IllegalArgumentException();
    Set<Set<E>> temp = new HashSet<>();
    int size = set.size();
    if (n > size)
        return temp;
    List<E> list = new ArrayList<>(set);
    int[] indices = new int[n];
    for (int i = 0; i < n; i++)
        indices[i] = i;
    while (true) {
        Set<E> s = new HashSet<>();
        for (int i : indices)
            s.add(list.get(i));
        temp.add(s);
        int r = n - 1;
        for (int m = size; r >= 0 && indices[r] == --m; r--);
        if (r == -1)
            return temp;
        for (int c = indices[r]; r < n;)
            indices[r++] = ++c;
    }
}

Upvotes: 0

sve
sve

Reputation: 4356

You can use simple backtracking to do this. You just go over each element and either pick this element to be in your subset or not. At the same time you can keep track of the current subset your are trying to build (current_subset) and how many elements you can still pick (k). A sample implementation:

static <E> void backtrack(int index, int k, Deque<E> current_subset,
                          List<E> elements) 
{
    if (k == 0) {
        System.out.println(current_subset);
        return;
    }
    if (index == elements.size())
        return;
    current_subset.push(elements.get(index));
    backtrack(index + 1, k - 1, current_subset, elements);
    current_subset.pop();
    backtrack(index + 1, k, current_subset, elements);
}

backtrack(0, 2, new ArrayDeque<Integer>(), 
          Arrays.asList(new Integer[]{0, 1, 2, 3, 4}));
/*
[1, 0]
[2, 0]
[3, 0]
[4, 0]
[2, 1]
[3, 1]
[4, 1]
[3, 2]
[4, 2]
*/

Note that if you what to keep the subsets you can just insert them in some structure (such as a List) instead of printing them.

Upvotes: 0

user3386109
user3386109

Reputation: 34829

Create a list containing the elements of the set.

Create a second list consisting of only 1's and 0's, where

  • the total number of elements in the list is equal to the number of elements in the set
  • the number of 1's in the list is equal to k

For each permutation of the second list, the subset consists of the elements from the first list whose corresponding entry in the second list is a 1.

Upvotes: 1

Related Questions