2

I want to print all subsets of the generated arrays recursively in the main method.

The following lines show my Code. I don't know how to implement the method subsets() recursively.

public class Main {

    // Make random array with length n
    public static int[] example(int n) {
        Random rand = new Random();
        int[] example = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            example[i] = rand.nextInt(100);
        }
        Arrays.sort(example, 1, n + 1);
        return example;
    }

    // Copy content of a boolean[] array into another boolean[] array
    public static boolean[] copy(boolean[] elements, int n) {
        boolean[] copyof = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            copyof[i] = elements[i];
        }

        return copyof;
    }

    // Counts all subsets from 'set'
    public static void subsets(int[] set, boolean[] includes, int k, int n) {

       // recursive algo needed here!

    }

    public static void main(String[] args) {
        // index starts with 1, -1 is just a placeholder.
        int[] setA = {-1, 1, 2, 3, 4};
        boolean[] includesA = new boolean[5];
        subsets(setA, includesA, 1, 4);

    }

}
herrh
  • 1,328
  • 1
  • 16
  • 33
  • "subsets" can be a bit ambiguous. Given the array `[1,2,3,4]`, what "subsets" would you expect? – tobias_k May 03 '16 at 14:42
  • 1
    You might want and implement `subsets()` non-recursively (i.e. implement it for _one_ subset), then think about what a recursive call should do (how do you define subsets, are they permutations?) and tell us. In the process you just might realize how you'd implement the recursion yourself. – Thomas May 03 '16 at 14:42
  • 1
    @tobias_k like here {}, {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4}, {1,2,3,4} – herrh May 03 '16 at 14:48
  • The [power set](https://en.wikipedia.org/wiki/Power_set)? See also [Power set: Algorithms](https://en.wikipedia.org/wiki/Power_set#Algorithms) – trashgod May 03 '16 at 14:54
  • Possible duplicate of [this](http://stackoverflow.com/q/1670862/230513). – trashgod May 03 '16 at 15:02
  • And how to handle duplicates? I.e., what about the array `[1,1]`? `[[], [1]]` or `[[], `[1]`, [1,1]]` or `[[], [1], [1], [1,1]]`? – tobias_k May 03 '16 at 15:16
  • 1
    @tobias_k like so `[[], [1]]`. – herrh May 03 '16 at 15:42

2 Answers2

0

If it's an option to use a third party library, the Guava Sets class can give you all the possible subsets. Check out the powersets method.

TheEllis
  • 1,666
  • 11
  • 18
0

Here's a non-recursive technique:

public List<Set<Integer>> getSubsets(Set<Integer> set) {
    List<Set<Integer>> subsets = new ArrayList<>();

    int numSubsets = 1 << set.size(); // 2 to the power of the initial set size

    for (int i = 0; i < numSubsets; i++) {
        Set<Integer> subset = new HashSet<>();
        for (int j = 0; j < set.size(); j++) {
            //If the jth bit in i is 1
            if ((i & (1 << j)) == 1) {
                subset.add(set.get(i));
            }
        }
        subsets.add(subset);
    }
    return subsets;
}

If you want only unique (and usually unordered) subsets, use a Set<Set<Integer>> instead of List<Set<Integer>>.

Chill
  • 1,093
  • 6
  • 13