Java: Generator of true's & false's combinations by giving the number N;

Question

I tied to simplify the task as much as possible, so I could apply it to my algorithm.

And here is the challenge for mathematicians and programmers:

I need to create a method where I pass parameter int n:

public void optionality_generator(int n){
  //some kind of loops, or recursions...to make it workable
  System.out.println("current combination: ...");
}

The output should show all possible combinations of true's and false's.

Here is examples where N=1; N=2; N=3; N=4; N=5 where x=false and 0=true; Please note, empty break lines is just for you to recognise easier the patterns. Hopefully, I included all possible combinations):

Combination of 1:
0
x

Combination of 2:
00
x0
0x
xx

Combination of 3:
000
X00
0X0
00X
XX0
0XX
XXX

Combination of 4:
0000

X000
0X00
00X0
000X

XX00
X0X0
X00X

0XX0
0X0X

00XX

XXX0
XX0X
X0XX
0XXX

XXXX

Combination of 5:
00000
X0000
0X000
00X00
000X0
0000X

XX000
X0X00
X00X0
X000X

X0X00
X00X0
X000X

0XX00
0X0X0
0X00X

00XX0
00X0X

000XX

XXX00
XX0X0
XX00X

X0XX0
X0X0X
X00XX

0XXX0
0XX0X

00XXX

XXXX0
XXX0X
XX0XX
X0XXX
0XXXX

XXXXX

Also, If you see the output, here is the pattern I recognized, that all combinations are inverted on half (e.g first combination is 00000 last one will be XXXXX, second one X0000, one before the last one will be 0XXXX etc..). Maybe, this pattern will help to make the whole algorithm more efficient, not sure about this. Thank you in advance!

Cochineal

This is why everyone should learn assembly first! Or at least bit math and two's complement. – Oversew

Answer 1

Here is a really basic way using only Java APIs:

final int n = 3;
for (int i = 0; i < Math.pow(2, n); i++) {
    String bin = Integer.toBinaryString(i);
    while (bin.length() < n)
        bin = "0" + bin;
    System.out.println(bin);
}

Result:

000
001
010
011
100
101
110
111

Of course, you can set n to whatever you like. And, with this result, you can pick the nth character from the string as true/false.

If you only need to check if a bit is true, you don't need to convert it to a string. This is just to illustrate the output values.

Jess

your code fails if int n = 5 because 2^5 = 32 is greater than n*n, perhaps use the Math.pow(2,n); instead? – Stanhope

I've updated my code... my brain had confused n^2 with 2^n! Thank you! – Jess

Answer 2

Just a clue but think about the bits that are set for a number with at most 'n' bits. You'll see if you go from 0 to 'n' number of bits (3 in this case); the bits are 000, 001, 010, 011, 100, 101, 110, 111. You can figure out the max number that can fit in 'n' bits by using the ((n*n)-1) formula.

Kindergartner

Answer 3

This should do the trick

int cols = 3;
int rows = (int) Math.pow(2, cols);
for (int row = 0; row < rows; row++)
    System.out.println(String.format("%" + cols + "s", 
            Integer.toBinaryString(row)).replace(' ', '0').replace('1', 'X'));

out:

000
00X
0X0
0XX
X00
X0X
XX0
XXX

Omentum

it's a little pity that String.format does not support %0s format, while C/C++ support it. – Phalanger

Answer 4

Using recursion is not as easy as using the Java Integer.toBinaryString() API for generating binary strings. But the code below gives you the flexibility to generate any base representation, e.g. base 3: "000" "001" "002" "010" "011" "012"

For base 2 (i.e. binary) strings, you call it like this:

getBinaryStrings(2, 3);

For base 3 strings, you call it like this:

getBinaryStrings(3, 3);

Here is the code:

public static List<String> getBinaryStrings(int base, int n){
    ArrayList<String> result = new ArrayList<>();
    getBinaryStringsCore(base, n, "", result);
    return result;
}

private static void getBinaryStringsCore(int base, int n, String tempString, List<String> result){
    if (tempString.length() == n) {
        result.add(tempString);
        return;
    }

    for (int i = 0; i < base; i++) {
        tempString += i;
        getBinaryStringsCore(base, n, tempString, result);
        tempString = tempString.substring(0, tempString.length() - 1);
    }
}

Partiality

The code for base-2 and base-3 strings are identical (i.e. getBinaryStrings(2, 3);). Is that intended? – Serafinaserafine

Thanks @entpnerd. I had a typo in my description of usage. It's now corrected. – Partiality

Answer 5

Here's a simple version implemented using recursion

public void optionality_generator(int n){
    ArrayList<String> strings = generatorHelper(n); 
    for(String s : strings){
        System.out.println(s);
    }
}

private ArrayList<String> generatorHelper(int n){
    if(n == 1){
        ArrayList<String> returnVal = new ArrayList<String>();
        returnVal.add("0");
        returnVal.add("X");
        return returnVal;
    }
    ArrayList<String> trueStrings = generatorHelper(n-1);
    for(String s : trueStrings){
        s += "0";
    }
    ArrayList<String> falseStrings = generatorHelper(n-1);
    for(String s : falseStrings){
        s += "X";
    }
    trueStrings.addAll(falseStrings);
    return trueStrings;
}

Stanhope

Note for others: maybe it works, but the output format is different, where everything is in single column, so it is impossible to distinguish where each combination starts and where it finishes. Anyway, thanks! – Cochineal

Answer 6

Here's a test-driven version:

import static org.junit.Assert.assertEquals;

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

import org.junit.Test;

public class OptionalityTest {

    @Test
    public void testOptionality0() throws Exception {
        assertEquals("[]", optionality(0).toString());
    }

    @Test
    public void testOptionality1() throws Exception {
        assertEquals("[0, x]", optionality(1).toString());
    }

    @Test
    public void testOptionality2() throws Exception {
        assertEquals("[00, x0, 0x, xx]", optionality(2).toString());
    }

    @Test
    public void testOptionality3() throws Exception {
        assertEquals("[000, x00, 0x0, xx0, 00x, x0x, 0xx, xxx]", optionality(3).toString());
    }

    private List<String> optionality(int i) {
        final ArrayList<String> list = new ArrayList<String>();
        if (i == 1) {
            list.add("0");
            list.add("x");
        }
        if (i > 1) {
            List<String> sublist = optionality(i - 1);
            for (String s : sublist) {
                list.add("0" + s);
                list.add("x" + s);
            }
        }
        return list;
    }

}

Redeemer

Answer 7

Here is a modification from Erics code above, that uses c# and allows input of any number of boolean variable names. It will output all possible combinations in c# code ready for insert into an if statement. Just edit the 1st line of code with var names, and then run in LINQpad to get a text output.

Output example...

!VariableNameA && !VariableNameB && !VariableNameC 
!VariableNameA && !VariableNameB &&  VariableNameC 
!VariableNameA &&  VariableNameB && !VariableNameC 
!VariableNameA &&  VariableNameB &&  VariableNameC 
 VariableNameA && !VariableNameB && !VariableNameC 
 VariableNameA && !VariableNameB &&  VariableNameC 
 VariableNameA &&  VariableNameB && !VariableNameC 
 VariableNameA &&  VariableNameB &&  VariableNameC 

    //To setup edit var names below
    string[] varNames = { "VariableNameA", "VariableNameB", "VariableNameC" };

    int n = varNames.Count();        
    for (int i = 0; i < Math.Pow(2, n); i++) {
      String bin = Convert.ToString(i, 2);
      while (bin.Length < n) {
          bin = "0" + bin;
      }        
      string and = " && ";
      string f = "!";
      string t = " ";
      var currentNot = bin[0] == '0' ? f : t;
      //string visual = bin[0].ToString();
      string visual = currentNot + varNames[0];
        for (var j = 1; j < n; j++) {
        currentNot = bin[j] == '0' ? f : t;
        //visual = visual + and + bin[j].ToString();
        visual = visual + and + currentNot + varNames[j];
      }		
      Console.WriteLine(visual);	
    }

Bogor