java List with all combinations of 8 booleans

Question

Let's say I pass in 3 trues and 5 falses, how can I code the getAllCombos method to return a List that includes:

• A 1 SampleForSO object with the 3 chosen
• The 3 "Three Choose Two" combinations
• The 3 "Three Choose One" combinations
• The 1 SampleForSO object with none chosen

So I'd return a List with:

• SampleForSO(T, T, T, F, F, F, F, F)
• SampleForSO(T, T, F, F, F, F, F, F)
• SampleForSO(T, F, T, F, F, F, F, F)
• SampleForSO(F, T, T, F, F, F, F, F)
• SampleForSO(T, T, F, F, F, F, F, F)
• SampleForSO(F, T, T, F, F, F, F, F)
• SampleForSO(T, F, T, F, F, F, F, F)
• SampleForSO(F, F, F, F, F, F, F, F)

---

public class SampleForSO {

private boolean b0;
private boolean b1;
private boolean b2;
private boolean b3;
private boolean b4;
private boolean b5;
private boolean b6;
private boolean b7;

public SampleForSO(boolean b0, boolean b1, boolean b2, boolean b3, boolean b4, boolean b5, boolean b6, boolean b7) {
    this.b0 = b0;
    this.b1 = b1;
    this.b2 = b2;
    this.b3 = b3;
    this.b4 = b4;
    this.b5 = b5;
    this.b6 = b6;
    this.b7 = b7;
}

public boolean equals(Object o) {
    if(o instanceof SampleForSO) {
        SampleForSO outer = (SampleForSO) o;
        return outer.b0 == this.b0 && outer.b1 == this.b1 && outer.b2 == this.b2 && outer.b3 == this.b3 && outer.b4 == this.b4 && outer.b5 == this.b5 && outer.b6 == this.b6 && outer.b7 == this.b7;
    }
    return false;
    
}

public static List<SampleForSO> getAllCombos(boolean b0, boolean b1, boolean b2, boolean b3, boolean b4, boolean b5, boolean b6, boolean b7){
    // How to get all the combos?
    return new ArrayList<SampleForSO>();
}

}

---

Here's a JUnit test that would show green if that method worked:

---

public class SampleForSOTest {

    public SampleForSOTest() {
        super();
    }
    
    @Test
    public void testGetAllCombinations() throws Exception {
        
        // 3 true, 5 false, but need this to work for all possibilities
        boolean b0_ = true;
        boolean b1_ = true;
        boolean b2_ = true;
        boolean b3_ = false;
        boolean b4_ = false;
        boolean b5_ = false;
        boolean b6_ = false;
        boolean b7_ = false;

        int numCombosWithAllThree = 1;
        int numCombosWithTwo = 3;
        int numCombosWithOne = 3;
        int numCombosWithZero = 1;

        int expectedSize = numCombosWithAllThree + numCombosWithTwo + numCombosWithOne + numCombosWithZero;
        
        List<SampleForSO> allCombos = SampleForSO.getAllCombos(b0_, b1_, b2_, b3_, b4_, b5_, b6_, b7_);

        assertEquals(expectedSize, allCombos.size());
    }

    

}

The combos I'd want would be:

• b0, b1, b2 all true, all else false
• b0 b1 true, all else false
• b1 b2 true, all else false
• b2 b0 true, all else false
• b0 true, all else false
• b1 true, all else false
• b2 true, all else false
• all false

Answer 1

Following Code generates all combinations

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

  public static List<List<Boolean>> generateAllCombinations(List<Boolean> input) {
    var combinations = new ArrayList<List<Boolean>>();
    if (input.isEmpty()) {
      return combinations;
    }

    // add combination seed
    combinations.add(new ArrayList<>());
    for (var inputIndexValue : input) {
      var nextCombinations= new ArrayList<List<Boolean>>();

      for (var indexCombination : combinations) {
          
        if (inputIndexValue) {
           // true is only valid if inputIndexValue is true
          var newCombination = new ArrayList<>(indexCombination);
          newCombination.add(true);
          nextCombinations.add(newCombination);
        }
        
        // false is always a valid value
        var newCombination = new ArrayList<>(indexCombination);
        newCombination.add(false);
        nextCombinations.add(newCombination);
      }

      combinations = nextCombinations;
    }

    return combinations;
  }

  public static void main(String[] args) {
    var input = List.of(true, true, true, false, false, false, false, false);
    var allCombinations = generateAllCombinations(input);
    for (var combination : allCombinations) {
      System.out.println(combination);
    }
  }
}

Answer 2

My approach to this was to treat the list of booleans as 1's and 0's packed into a byte. So true,true,false would be 110.

It should also be noted that the number if n is the number of true values in the original list, then the number of combinations that actually contain a true boolean is 2ⁿ-1. Adding an additional combination takes care of the combinations containing only false values.

Ideally, one would like to increment across all non-consecutive one bits as though they were contiguous. For example, consider 1101. The low order second bit is ignored.

0000
0001
0100
0101
1000
1001
1100
1101

This is easily done by making use of the methods Integer.expand and Integer.compress introduced in Java 19. By specifying a bit mask of the 1 bit's current positions, they can be compressed to the low order position as a single stream of 1 bits. This can be reversed by using expand to put them back.

Example:

int a = 0b101010;
int mask = 052;  // octal
int compress = Integer.compress(a,mask);
System.out.println(Integer.toBinaryString(compress)); //0111;
int expand = Integer.expand(compress,mask);
System.out.println(Integer.toBinaryString(expand)); //101010

To allow this to work with I added the following constants.

static int NBITS = 8;
static int HIGHBITMASK = 1<<(NBITS-1); // x80 for 8 bits
static int ALLBITMASK = (1<<NBITS)-1;  // xFF for 8 bits

Additional, I created some helper lambdas to pack and unpack the booleans to and from an int.

static Function<Integer, List<Boolean>> unpack = a -> {
    List<Boolean> list = new ArrayList<>();
    for (int i = 0; i < NBITS; i++) {
        list.add((a & HIGHBITMASK) == HIGHBITMASK);
        a <<= 1;
    }
    return list;
};

static Function<List<Boolean>, Integer> pack = list -> 
    list.stream().mapToInt(a -> a ? 1 : 0).reduce(0,
            (a, b) -> a << 1 | b);

Here is the working generateCombinations() method.

public static List<List<Boolean>> generateCombinations(List<Boolean> list) {
    // not certain how you wish to handle null or empty
    // submission but here is one way.
    if (list == null || list.isEmpty()) {
            return new ArrayList<List<Boolean>>();
    }

    int mask = pack.apply(list);
    int nCombos = Integer.compress(ALLBITMASK, mask) + 1;
    List<List<Boolean>> combos = IntStream.range(0, nCombos)
            .mapToObj(c -> unpack.apply(Integer.expand(c, mask))).toList();
    return combos;
}

Other stuff

If you want to see the frequency count of various combinations, you can do this (using your original list) where the key/value pairs show the number count of true values (key) and the number of combinations which had that count (value).

List<List<Boolean>> combos = generateCombinations(list);

Map<Integer, Long>  map = combos.stream().mapToInt(pack::apply).boxed()
        .collect(Collectors.groupingBy(Integer::bitCount, Collectors.counting()));

map.entrySet().forEach(System.out::println);

prints

0=1
1=3
2=3
3=1

Note that the counts follow Pascal's triangle.

To make your class more versatile, you can change the constructor to use the varargs operator.

public SampleForSO(Boolean... bArray) {
    this.bArray = bArray; // 
}

bArray will be an array containing the number of elements passed. Then you can check for equality in your equals method by doing Arrays.equals(bArray, this.bArray);

But of course, this depends on your use case since you would have to access the booleans via an array index.

Answer 3

Another completely different alternative is to just treat the true values as bits directly, incrementing in binary. To avoid iterating over the entire list each time, an array of the indices of the true values is obtained.

List<List<Boolean>> combos = new ArrayList<>();

List<Boolean> values = new
         ArrayList<>(List.of(true, false, true, false, true));
     
int[] indices = IntStream.range(0, values.size())
            .filter(i -> values.get(i)).toArray(); // [0, 2, 4] for example

values changes each time so it must be resubmitted as is changed to continue the next iteration.

for (int i = 0; i < 1 << indices.length; i++) {
            combos.add(increment(indices, values));
}

combos.foreach(System.out::println);

in this example, prints

[false, false, false, false, false]
[false, false, false, false, true]
[false, false, true, false, false]
[false, false, true, false, true]
[true, false, false, false, false]
[true, false, false, false, true]
[true, false, true, false, false]
[true, false, true, false, true]

The increment method

public static List<Boolean> increment(int indices[], List<Boolean> values) {
    for (int i = indices.length - 1; i >= 0; i--) {
        if (!values.get(indices[i])) {
            values.set(indices[i], true);
            return new ArrayList<>(values);
        } else {
            values.set(indices[i], false);
        }
    }
    return new ArrayList<>(values);
}