JAVA: power generator with a subset length of 3 to max.

Question

Everything is in the title .. =)

I want to quickly create a power supply, only with a subset of the length between 3 (minimum constant length) and maximum. This maximum should be 5 in most cases, but I want it to be variable (from 3 to 5.6). The source set may be large. I need to save a subset of theses for further processing.

I have seen getting a set of set parameters in Java , but here they generate every subset of the set of power. I also saw an efficient syntax algorithm for subsets of minimum length , for C #, but I think that, as Adam C said, I ran into low performance and memory issues.

I would like to combine these ideas into the perfect one for my purpose. My last hope would be to quickly generate each subset (possibly with an algorithm in Guava ) and iterate to the required length ... but even reading it is ugly;)

Has anyone got any ideas?

Answer 1

I lent a lot to st0le .

Basically, when I repeated the bit array controlling the generation of the set, I checked that the number of bits was between the minimum and maximum.

Here is the code.

import java.util.BitSet; import java.util.Iterator; import java.util.Set; import java.util.TreeSet; public class PowerSet<E> implements Iterator<Set<E>>, Iterable<Set<E>> { private int minSize; private int maxSize; private E[] arr = null; private BitSet bset = null; @SuppressWarnings("unchecked") public PowerSet(Set<E> set, int minSize, int maxSize) { this.minSize = Math.min(minSize, set.size()); this.maxSize = Math.min(maxSize, set.size()); arr = (E[]) set.toArray(); bset = new BitSet(arr.length + 1); for (int i = 0; i < minSize; i++) { bset.set(i); } } @Override public boolean hasNext() { return !bset.get(arr.length); } @Override public Set<E> next() { Set<E> returnSet = new TreeSet<E>(); // System.out.println(printBitSet()); for (int i = 0; i < arr.length; i++) { if (bset.get(i)) { returnSet.add(arr[i]); } } int count; do { incrementBitSet(); count = countBitSet(); } while ((count < minSize) || (count > maxSize)); // System.out.println(returnSet); return returnSet; } protected void incrementBitSet() { for (int i = 0; i < bset.size(); i++) { if (!bset.get(i)) { bset.set(i); break; } else bset.clear(i); } } protected int countBitSet() { int count = 0; for (int i = 0; i < bset.size(); i++) { if (bset.get(i)) { count++; } } return count; } protected String printBitSet() { StringBuilder builder = new StringBuilder(); for (int i = 0; i < bset.size(); i++) { if (bset.get(i)) { builder.append('1'); } else { builder.append('0'); } } return builder.toString(); } @Override public void remove() { throw new UnsupportedOperationException("Not Supported!"); } @Override public Iterator<Set<E>> iterator() { return this; } public static void main(String[] args) { Set<Character> set = new TreeSet<Character>(); for (int i = 0; i < 7; i++) set.add((char) (i + 'A')); PowerSet<Character> pset = new PowerSet<Character>(set, 3, 5); int count = 1; for (Set<Character> s : pset) { System.out.println(count++ + ": " + s); } } } 

And here are the test results:

 1: [A, B, C] 2: [A, B, D] 3: [A, C, D] 4: [B, C, D] 5: [A, B, C, D] 6: [A, B, E] 7: [A, C, E] 8: [B, C, E] 9: [A, B, C, E] 10: [A, D, E] 11: [B, D, E] 12: [A, B, D, E] 13: [C, D, E] 14: [A, C, D, E] 15: [B, C, D, E] 16: [A, B, C, D, E] 17: [A, B, F] 18: [A, C, F] 19: [B, C, F] 20: [A, B, C, F] 21: [A, D, F] 22: [B, D, F] 23: [A, B, D, F] 24: [C, D, F] 25: [A, C, D, F] 26: [B, C, D, F] 27: [A, B, C, D, F] 28: [A, E, F] 29: [B, E, F] 30: [A, B, E, F] 31: [C, E, F] 32: [A, C, E, F] 33: [B, C, E, F] 34: [A, B, C, E, F] 35: [D, E, F] 36: [A, D, E, F] 37: [B, D, E, F] 38: [A, B, D, E, F] 39: [C, D, E, F] 40: [A, C, D, E, F] 41: [B, C, D, E, F] 42: [A, B, G] 43: [A, C, G] 44: [B, C, G] 45: [A, B, C, G] 46: [A, D, G] 47: [B, D, G] 48: [A, B, D, G] 49: [C, D, G] 50: [A, C, D, G] 51: [B, C, D, G] 52: [A, B, C, D, G] 53: [A, E, G] 54: [B, E, G] 55: [A, B, E, G] 56: [C, E, G] 57: [A, C, E, G] 58: [B, C, E, G] 59: [A, B, C, E, G] 60: [D, E, G] 61: [A, D, E, G] 62: [B, D, E, G] 63: [A, B, D, E, G] 64: [C, D, E, G] 65: [A, C, D, E, G] 66: [B, C, D, E, G] 67: [A, F, G] 68: [B, F, G] 69: [A, B, F, G] 70: [C, F, G] 71: [A, C, F, G] 72: [B, C, F, G] 73: [A, B, C, F, G] 74: [D, F, G] 75: [A, D, F, G] 76: [B, D, F, G] 77: [A, B, D, F, G] 78: [C, D, F, G] 79: [A, C, D, F, G] 80: [B, C, D, F, G] 81: [E, F, G] 82: [A, E, F, G] 83: [B, E, F, G] 84: [A, B, E, F, G] 85: [C, E, F, G] 86: [A, C, E, F, G] 87: [B, C, E, F, G] 88: [D, E, F, G] 89: [A, D, E, F, G] 90: [B, D, E, F, G] 91: [C, D, E, F, G] 

Answer 2

Indicate if the number of items is limited.

For 3 - 5.6 elements, an array of indices is possible, maybe short[6] .

For example, with up to 32 elements, an int can hold the set, and you can either:

 // dumb: for (int mask = 0; ; ;) { int cardinality = Integer.bitCount(mask); if (3 <= cardinality && cardinality <= 6) { ... } } 

For more than 64 elements, perhaps BitSet will offer compactness.

The solution here is related to simple statistics: how many elements, etc. For an int / long / BitSet solution, you can start with a BitSet, as it has a more convenient API. For example, you can move on to the next parameter with an equal number of bits by flipping two bits. If someone is mathematically inclined, De Bruijn loops can be interesting.

Answer 3

For sets whose size does not exceed 63 elements, and if you have a minimum size limit that is not low, this implementation may be faster:

 import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Set; import static com.google.common.base.Preconditions.checkArgument; import static java.lang.Math.min; public class PowerSet<E> implements Iterator<Iterable<E>>, Iterable<Iterable<E>> { private int minSize; private int maxSize; private E[] arr = null; private long bits = 0; private long count = 0; private long minMask = 0; /** * Build a PowerSet of the given {@link Set} to iterate over subsets whose size is between the given boundaries * @param set the set to create subsets from * @param minSize the minimal size of the subsets * @param maxSize the maximum size of the subsets */ @SuppressWarnings("unchecked") public PowerSet(Set<E> set, int minSize, int maxSize) { checkArgument(maxSize < 63); // limited to 63 because we need one additional bit for hasNext this.minSize = min(minSize, set.size()); this.maxSize = min(maxSize, set.size()); arr = (E[]) set.toArray(); for (int n = 0; n < minSize; n++) { bits |= (1L << n); } count = countBitSet(bits); } @Override public boolean hasNext() { return (bits & (1L << arr.length)) == 0; } @Override public Iterable<E> next() { // compute current subset final List<E> returnSet = new LinkedList<>(); for (int i = 0; i < arr.length; i++) { if ((bits & (1L << i)) != 0) { returnSet.add(arr[i]); } } // compute next bit map for next subset do { if (count < minSize) { long maxFree = lowestIndex(bits) - 1; long missing = minSize - count; for (int n = 0; n < min(maxFree, missing); n++) { bits |= (1L << n); } } else { bits++; } count = countBitSet(bits); } while ((count < minSize) || (count > maxSize)); return returnSet; } /** * Lowest set bit in a long word * @param i the long word * @return lowest bit set */ private static long lowestIndex(long i) { int n = 0; while (n < 64 && (i & 1L) == 0) { n++; i = i >>> 1; } return n; } /** * Compute the number of bit sets inside a word or a long word.<br/> * <a href="http://en.wikipedia.org/wiki/Hamming_weight">Hamming weight</a> * @param i the long word * @return number of set bits */ private static long countBitSet(long i) { i = i - ((i >>> 1) & 0x5555555555555555L); i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L); i = ((i + (i >>> 4)) & 0x0F0F0F0F0F0F0F0FL); return (i * (0x0101010101010101L)) >>> 56; } @Override public void remove() { throw new UnsupportedOperationException("Not Supported!"); } @Override public Iterator<Iterable<E>> iterator() { return this; } } 

It is supported by a long one, not BitSet, and it computes the next subset faster ... It can also be faster with a minimum minimum limit.

You can remove the dependency on Guava, which is used only for the checkArgument constructor ...