CODEWITHSUNDEEP
javamemory-managementcollectionsmemory-leakssubset
flyleaf
flyleaf

Reputation: 995

How to make all possible power subsets from an arrayList including a particular item?

Say I have an arrayList of strings like [a, b, c, d, ....]. Can anybody help me with a sample code that how can I come out with a result that contains all possible power subsets form this list which are including a particular string from that list(except the single and empty subset)?

For example: if I like to get all the power subsets including a from the example list then the output will be:

[a,b], [a,c], [a,d], [a,b,c], [a,b,d], [a,c,d] without the empty and single subset([a])

Similarly if I want for b then the output will be:

[b,a], [b,c], [b,d], [b,a,c], [b,a,d], [b,c,d] without the empty and single subset([b])

As all of the items in the example list are string then their might be a memory problem when the subsets will be too rich. Because I need to keep this subsets in memory for a single string at a time. So I also need help about what would be the optimized solution for this scenario?

I need the help in Java. As I am not that much good at Java please pardon me if I made any mistake!

Thanks!

Upvotes: 1

Views: 318

Answers (1)

DGH
DGH

Reputation: 11539

If your initial arraylist of strings has 30 or fewer items, you can use the set method powerSet (http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Sets.html#powerSet%28java.util.Set%29 - Thanks, Jochen). The documentation claims the memory usage is only O(n) for the set-of-sets returned by that method. You can then iterate over that, with an if condition to only consider sets which contain "A" and are of size 2 or greater.

I recommend you try the above or a similar simple solution first and see if you run into memory problems.

If you do run into memory issues, you can try to optimize by minimizing the number of copies of the strings you hold in memory. For example, you can use lists of bytes, shorts, or ints (depending on how long your arraylist is) where each is an index into your arraylist of strings.

The ultimate way to reduce memory usage, however, would be to only hold one subset in memory at a time (if possible). I.e. generate (A, B), process it, discard it, then generate (A, C), process it, discard it, etc.

Upvotes: 2

Related Questions