4

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!

  • 1
    Any chance you've tried to do it? Perhaps you have an inefficient implementation? – Sesame Oct 03 '15 at 03:02
  • How many elements does the set have? – user3386109 Oct 03 '15 at 03:03
  • @Sesame, I'm currently using a method where I generate the entire powerset, and then iterate through this and delete the subsets that do not match the length I want. –  Oct 03 '15 at 03:14
  • A 'formula' for the usual case would be `2^S = flatten([[x U Y for Y in 2^(S-{x})] for x in S])`. You want subsets of size `n` so you want each `Y` to be size `n-1`. So just take an existing implementation and add an extra size parameter to the function and use `size-1` when you call recursively. – Alex Hall Oct 03 '15 at 03:14
  • @user3386109, the set has between 2 and 31 elements. I want to generate subsets of length 3. –  Oct 03 '15 at 03:14
  • Check out this library: https://github.com/dpaukov/combinatoricslib – Alex Hall Oct 03 '15 at 03:18
  • Possible duplicate: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – someguy Oct 03 '15 at 14:24

4 Answers4

1

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.

user3386109
  • 34,287
  • 7
  • 49
  • 68
  • Not permutation, but combination. Elements in a set are not ordered. – someguy Oct 03 '15 at 14:25
  • @someguy Create a **list**, not a set, and compute all of the permutations of the list. – user3386109 Oct 03 '15 at 16:34
  • The underlying data structure isn't relevant. You want all the combinations, not permutations, of size `k`. For example, the set {x, y} has only one subset of size 2. Your method would return two subsets, as if {x, y} and {y, x} were unequal. – someguy Oct 03 '15 at 21:20
  • @someguy I guess we disagree on the definition of a permutation. For example, I define the permutations of `{0,1,1} as {{0,1,1}, {1,0,1}, {1,1,0}}` See [this answer](https://stackoverflow.com/a/31885811/3386109) for a method that computes the permutations of an array without any repeats. – user3386109 Oct 04 '15 at 06:46
  • There can be no disagreement on the definition of permutation. It's a mathematical concept! Your example is flawed, because that 'set' isn't actually a set. Elements must be unique. If they were, you'd find that there are in fact 6 different permutations. However, like I said, we're interested in the different combinations, not permutations. Please read this small entry: https://en.wikipedia.org/wiki/Power_set#Relation_to_binomial_theorem. It's elementary set/probability theory. – someguy Oct 04 '15 at 13:40
  • Also, if you want a real answer to this question, see the link I've posted in a comment to the OP. For convenience: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n. – someguy Oct 04 '15 at 13:43
0

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;
    }
}
Paul Boddington
  • 37,127
  • 10
  • 65
  • 116
0

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.

sve
  • 4,336
  • 1
  • 19
  • 30
0

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.

Mohammad
  • 6,024
  • 3
  • 22
  • 30