Kombinieren mit BitSets

Hin und wieder sucht der Entwickler eine Möglichkeit alle Kombinationen einiger Werte zu generieren. Ein einfache und elegante Methode kann mit Streams und BitSets implementiert werden.

Bei zwei Farben aus einer Liste von vier Farben ergeben sich genau sechs Kombinationen.

(rot, grün, blau, gelb) \Rightarrow { (rot, grün), (rot, blau), (rot, gelb), (grün, blau), (grün, gelb), (blau, gelb) }

Auch hier wird das BitSet, ähnlich wie im Beitrag Enum Sets in JPA Entities speichern zum Speichern von Positionen verwendet. Für die Farben Rot wird das erste Bit im BitSet verwendet, für Grün das zweite Bit, u.s.w.

Alle Kombinationen aus den vier Farben erhält man, in dem alle 4 Bit Kombinationen erstellt und den gesetzten Bit Position eine Farbe zugeordnet wird.

Die Bit Kombination sind die Zahlen zwischen 1 und 2^{\text{Anzahl Farben}}. Ein entsprechender Stream kann mit einem IntStream generiert werden.

List<String> values = List.of("rot", "grün", "blau", "gelb");
Stream<Integer> stream = IntStream.range(1, (int) Math.pow(2, values.size()));

Das BitSet kann direkt aus dem Integer Wert erzeugt werden und wird direkt in den Stream integriert

List<BitSet> values = List.of("rot", "grün", "blau", "gelb");
Stream<BitSet> stream = IntStream.range(1, (int) Math.pow(2, values.size()))
    .mapToObj(x -> BitSet.valueOf(new long[]{x}));

Aus dem BitSet wird dann ein Set<String> erzeugt, in dem für jede Bit Position die Farbe von einer korrespondieren Position in einer Farbliste gewählt wird.

private Set<T> createSet(BitSet x) {
  Set<T> set = new HashSet<>();
  for (int j = 0; j < values.size(); j++) {
    if (x.get(j)) {
      set.add(values.get(j));
    }
  }
  return set;
}

Die Methode ist generisch gehalten, damit nicht nur Strings als Werte verwendet werden können.

public class Generator<T> {
  private final List<T> values;

  public Generator(List<T> values) {
    this.values = values;
  }

  public Stream<Set<T>> stream() {
    Stream<BitSet> bitSetStream = IntStream.range(1, (int) Math.pow(2, values.size()))
        .mapToObj(x -> BitSet.valueOf(new long[]{x}));
    return bitSetStream.map(this::createSet);
  }

  private Set<T> createSet(BitSet x) {
    Set<T> set = new HashSet<>();
    for (int j = 0; j < values.size(); j++) {
      if (x.get(j)) {
        set.add(values.get(j));
      }
    }
    return set;
  }
}

Die bisher implementierte Klasse erzeugt Streams mit allen 15 möglichen Kombinationen.

Generator<String> colorSetgenerator = new Generator<>(List.of("rot", "grün", "blau", "gelb"));
System.out.println(colorSetgenerator.stream().map(String::valueOf).collect(joining(", ")));
// [rot], [grün], [rot, grün], [blau], [blau, rot], [blau, grün], [blau, rot, grün], [gelb], 
// [gelb, rot], [gelb, grün], [gelb, rot, grün], [blau, gelb], [blau, gelb, rot], [blau, gelb, grün], 
// [blau, gelb, rot, grün]

Gewünscht waren aber nur die Kombinationen aus zwei Farben. Um diese zu erhalten, kann entweder ein Filter in den zurückgegebenen Stream eingefügt werden oder der Generator wird ergänzt. Der Filter im zurückgegebenen Stream würde nur die Set Instanzen passieren lassen, die genau zwei Einträge besitzen. Leider würden dadurch eine Menge Set Instanzen generiert werden, die sofort wieder entsorgt werden würden. Daher greift die hier vorgestellte Lösung schon weit vorne in den Stream ein.

public Stream<Set<T>> stream() {
  Stream<BitSet> bitSetStream = IntStream.range(1, (int) Math.pow(2, values.size()))
      .mapToObj(x -> BitSet.valueOf(new long[]{x}));
  return filter(bitSetStream).map(this::createSet);
}

private Stream<BitSet> filter(Stream<BitSet> bitSetStream) {
  if (setSize == 0) {
    return bitSetStream;
  }
  return bitSetStream.filter(x -> x.cardinality() == setSize);
}

Noch innerhalb der Generator Instanz wird ein Filter In den Stream eingefügt, der die Kardinalität des BitSets gegen einen vorgegebenen Wert prüft. Die Kardinalität ist dabei die Anzahl gesetzter Bits im BitSet. Um die Kombinationen zweier Farben zu erhalten ändert sich das Beispiel nur leicht.

Generator<String> colorSetgenerator = new Generator<>(2, List.of("rot", "grün", "blau", "gelb"));
System.out.println(colorSetgenerator.stream().map(String::valueOf).collect(joining(", ")));
// [rot, grün], [blau, rot], [blau, grün], [gelb, rot], [gelb, grün], [blau, gelb], 

Wer auch kein BitSet erzeugen möchte, kann den Filter noch früher einfügen und mit Long.bitCount die gesetzten Bits zählen.

public Stream<Set<T>> stream() {
  LongStream stream = LongStream.range(1, (long) Math.pow(2, values.size()));
  return filter(stream).mapToObj(x -> BitSet.valueOf(new long[]{x})).map(this::createSet);
}

private LongStream filter(LongStream stream) {
  if (setSize == 0) {
    return stream;
  }
  return stream.filter(x -> Long.bitCount(x) == setSize);
}