How can I get the subset from an ArrayList?

Ezequiel Soler Perez 0
Viewed 90

I'm working on a problem that asks me to "Write a method that returns all of the subsets of the set formed by the integers 1 to N where N is passed to the method." If I pass N = 3 to the method my output should look like [[0], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]. My current output is [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]. Is there a way for me to print out the desired range like doing Arrays.copyOfRange() for the ArrayList? or is there another way of getting the subset with my desired output?;

import java.util.ArrayList;
import java.util.HashSet;

public class HW3 {

    public static void main(String[] args) {
        System.out.println(powerset(3));
    }

    public static ArrayList<HashSet<Integer>> powerset(int N) {
        ArrayList<HashSet<Integer>> arrayList = new ArrayList<HashSet<Integer>>();
        HashSet<Integer> arrayListNew = new HashSet<Integer>();
        for (int i = 0; i <= N; i++)
            arrayListNew.add(i);

        for (int i = 0; i < (int) Math.pow(2, N); i++)
            arrayList.add(arrayListNew);

        return arrayList;
    }
}
hashset subset integer arraylist java
3 Answers

"Is there a way for me to print out the desired range like doing Arrays.copyOfRange() for the ArrayList?"

yes, use sublist() read more here

However, you don't need that for your question. The algorithm you are looking for should look sth like this

//1st for loop iterate through all the possible sizes for the hash set
for(){
   //2nd for loop generate all possible combinations given the size
   for(){
   }
}
//might need to add the [0] urself at the end
Icarus0

The more suitable way to do this is Backtracking

public class BacktrackTest {

    public static void main(String[] args) {
        powerset(3);
    }

    public static void powerset(int num) {
        if (num >= 10 || num < 1) {
            throw new IllegalArgumentException();
        }
        int[] chs = new int[num];
        for (int i = 1; i <= num; i++) {
            chs[i - 1] = i;
        }
        List<List<Integer>> resultList = new ArrayList<>();
        backtrack(0, chs, new ArrayList<>(), resultList);
        Collections.sort(resultList, (a, b) -> {
           int len1 = a.size();
           int len2 = b.size();
           return len1 - len2;
        });
        System.out.println(resultList);
    }

    public static void backtrack(int index, int[] chs, List<Integer> tempList, List<List<Integer>> resultList) {
        for (int i = index; i < chs.length; i++) {
            tempList.add(chs[i]);
            resultList.add(new ArrayList<>(tempList));
            backtrack(i + 1, chs, tempList, resultList);
            tempList.remove(tempList.size() - 1);
        }
    }
}

Java Fiddle Demo

Output result:

enter image description here

lucumt0 
public class HW3 {
static void printSubsets(int set[]) {
    int n = set.length;
    for (int i = 0; i < (1 << n); i++) {
        System.out.print("{ ");
        for (int j = 0; j < n; j++)
            if ((i & (1 << j)) > 0)
                System.out.print(set[j] + " ");

        System.out.println("}");
    }
}

public static void main(String[] args) {
    int n = 3;
    int[] set = new int[n+1];
    for(int i = 0; i<=n; i++){
        set[i]=i;
    }
    printSubsets(set);
}}

The total number of subsets of any given set is equal to 2^ (no. of elements in the set). If we carefully notice it is nothing but binary numbers from 0 to 7 which can be shown as below:

000 001 010 011 100 101 110 111

Starting from right, 1 at ith position shows that the ith element of the set is present as 0 shows that the element is absent. Therefore, what we have to do is just generate the binary numbers from 0 to 2^n – 1, where n is the length of the set or the numbers of elements in the set.

Time complexity: O(n * (2^n)) as the outer loop runs for O(2^n) and the inner loop runs for O(n).

hungtv0
Related