Calculating all of the subsets of a set of numbers

by

What you want is called a Powerset. Here is a simple implementation of it:

public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
        Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<Integer>());
            return sets;
        }
        List<Integer> list = new ArrayList<Integer>(originalSet);
        Integer head = list.get(0);
        Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
        for (Set<Integer> set : powerSet(rest)) {
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

I will give you an example to explain how the algorithm works for the powerset of {1, 2, 3}:

  • Remove {1}, and execute powerset for {2, 3};
    • Remove {2}, and execute powerset for {3};
      • Remove {3}, and execute powerset for {};
        • Powerset of {} is {{}};
      • Powerset of {3} is 3 combined with {{}} = { {}, {3} };
    • Powerset of {2, 3} is {2} combined with { {}, {3} } = { {}, {3}, {2}, {2, 3} };
  • Powerset of {1, 2, 3} is {1} combined with { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.

More Related Contents:

  1. best way to pick a random subset from a collection?
  2. Modulus of a very large number
  3. O(3^n) exponential time complexity [closed]
  4. Showing the order of growth of the function
  5. Good Java graph algorithm library? [closed]
  6. Sparse matrices / arrays in Java
  7. Which Java Collection should I use?
  8. Quickest way to find missing number in an array of numbers
  9. How to calculate elapsed time from now with Joda-Time?
  10. Java, find intersection of two arrays
  11. Stack with find-min/find-max more efficient than O(n)?
  12. Java – Removing duplicates in an ArrayList
  13. Fast algorithm for searching for substrings in a string
  14. Generating all possible permutations of a list recursively
  15. Why does Java’s Arrays.sort method use two different sorting algorithms for different types?
  16. Find top N elements in an Array
  17. How to generate a random permutation in Java?
  18. Java – Sort one array based on values of another array?
  19. What is the sorting algorithm for Java [closed]
  20. In Java, how do I efficiently and elegantly stream a tree node’s descendants?
  21. Flatten nested arrays in java
  22. How to generate the power-set of a given List?
  23. How to iteratively generate k elements subsets from a set of size n in java?
  24. How to restore the PriorityQueue to its initial state before the method call?
  25. How to determine if binary tree is balanced?
  26. What is the algorithm for finding the center of a circle from three points?
  27. Finding the shortest path nodes with breadth first search
  28. Mergesort in java
  29. Time complexity of System.arraycopy(…)?
  30. StackOverflowError computing factorial of a BigInteger?

Leave a Comment