Thread: Need algorithm for generation of all variations of a 4x4 boolean table.

Hello everyone, I am currently try to solve a problem which requires the generation of all 2^16 arrays each with different values and I'm afraid I have no clue how to do so efficiently. Could anyone please point me to an algorithm which could be utilized for such a task?

What my problem is : I need to generate 4x4 True/False tables that meet certain criteria. These criteria are listed in my code and preceded by //Rule.
What I believe I need : Every possible variation of a 4x4 boolean array. Each one having a distinctive pattern of True/False compared to the other.
What I am asking for here : A method with which to generate these distinctive tables.


Sorry for my lack of specificity everyone.

EDIT : I have now added a way to generate my tables. I find the binary value of every number from 0-665536. I then convert this binary value to a string. if this less string is less than 16 chars in length then I add 0's until that condition is satisfied. I then convert that string into usable information using an if statement and the charAt method of the string class (line 9).
Some of the rules were terribly written but happened to work when I put in perfect tables ( I learned a valuable lesson regarding testing today.)

To the person who was confused by the rules, I apologize for the confusion, I made a quite a few mistakes ( I've been programming for less than 2 year and it shows, I apologize ).
Thank you everyone for helping me.
If anyone has any improvement please do tell me, I seek nothing more than to better myself!

For those interested. This was all for the sake of computing a solution to this problem :
https://class.coursera.org/intrologi...mpt?quiz_id=23

The tables below are example of the distinctive tables I need to generate where.
x : true
: false
This is table 1:
null [x] [x] [ ] [x]
null [x] [ ] [ ] [ ]
null [ ] [ ] [ ] [x]
null [x] [ ] [x] [ ]

This is table 2
null [x] [x] [ ] [x]
null [x] [x] [ ] [ ]
null [ ] [ ] [x] [x]
null [x] [ ] [x] [ ]

This is table 3
null [ ] [ ] [ ] [ ]
null [ ] [ ] [x] [ ]
null [ ] [ ] [ ] [ ]
null [ ] [ ] [ ] [ ]

Though I have no bugs at the moment I'll include the code so far anyway.

public class logicp1
{
  public static boolean[][] convertToTable(String s){
    int c = 0;
    boolean[][] dog = new boolean[4][4];
    for ( int k = 0; k < 4; k++)
    {
      for ( int i =0; i < 4; i++)
      { if(s.charAt(c) == '1'){
        dog[k][i] = true;
        c++;
      }
      else{  c++;}
      }
 
    }
    return dog;
  }
  public static boolean compareArray(boolean[][][] s, boolean[][] k)
  {
    for ( int i = 0; i < s.length; i++)
    { if (compareTable(s[i],k) == true ) return true;
      i++;
    }
    return false;
  }
 
  public static boolean compareTable(boolean[][] s, boolean[][] p){
 
    for ( int k = 0; k < 4; k++)
    {
      for ( int i =0; i < 4; i++)
      { 
        if (s[k][i] != p[k][i]) return false;
      }
    }return true;
  }
 
  public static void sop(Object s){
    System.out.println(s);
  }
  public static boolean checkFor(String[] s,String k)
  { int i = 0;
    while(s[i] != null )
    { if (s[i].equals(k))
      return true;
    i++;}
    return false;
  }
  public static boolean checkRules(boolean[][] likeTable)
  { boolean isTrue = false;
 
    // Rule 1 Dana Likes Cody in terms of table values it is necessary that likeTable[3][2] is always true. Thus :
 
    if ( likeTable[3][2] == false ) return false;
    // Rule 2 Bess does not Like Dana. Therfore likeTable[1][3] is always false. Thus :
    if ( likeTable[1][3] == true) return false;
 
    // Rule 3 Cody does not like Abby, therefore likeTable[2][0] is always False
    if ( likeTable[2][0] == true ) return false;
 
// Rule 4 Nobody likes someone who does not like her. This translates to an if statement.
    // if likeTable[x][y] == true then likeTable[y][x] must be true
    for ( int i = 0; i < 4; i++)
    {
      for ( int c = 0; c < 4; c++)
      {
        if (likeTable[i][c] != likeTable[c][i]) return false;
      }
    }
 
    // Rule 5 Abby like everyone who likes Bess . This means that if [x][1] == true, then likeTable[3][x] == true
    for ( int i = 0; i < 4; i++){
      if ( likeTable[i][1] == true && likeTable[0][i] == false ) return false;
    }
 
    // Rule 6 Dana likes  everyone Bess likes. This can be ensured through a for loop which takes the values of Bess and 
    // replaced the values of Dana with them. e.g for i < 3; likeTable[3][i] gets likeTable[1][i] This also means that the dana array does not need to be manipulated during generation.
    for ( int i = 0; i < 4; i++){
      if (likeTable[1][i] == true && likeTable[3][i] == false ) return false;
    }
 
    // Rule 7 Everybody likes somebody Meaning that for any likeTable[i][0-3] one of htese values must be true.
boolean[][] ffs = new boolean[4][1];
    for ( int i = 0; i < 4; i++)
    { 
      for ( int c = 0; c < 4; c++)
      {
        if (likeTable[i][c] == true)ffs[i][0] = true;          
        }
      } 
      boolean allTrue = true;;
    for ( int i = 0;i<ffs.length;i++)
    { if (ffs[i][0] == false)
      allTrue = false;
 
  }
    return allTrue;
  }
 
  public static void printTable(boolean[][] likeTable)
  { String[] lines = new String[4];
    for ( int i = 0; i < 4; i++){
      for ( int c = 0; c < 4; c++){
        if ( likeTable[i][c] == true) lines[i] += " [x] ";
        else{ lines[i] += " [ ] "; }
      }
    }
 
    for ( int i = 0; i <4;i++)
    {
      System.out.println(lines[i]);}
  }
 
 
 
 
  public static void main (String[] args){
    boolean[][] likeTable = new boolean[4][4];
    // boolean table created, true = like, false = dislike
    /*  Abby Bess  Cody Dana
     *  Abby
     *  Bess
     *  Cody
     *  Dana
     /* Algorithm : I will load the rules of the world into the program and store them as constant rules. I will then generate variations of the truth table and test against the states
     * below is the initialization of each rule */
 
    System.out.println(likeTable[2][0]);
    likeTable[0][0] = true;
    likeTable[1][0] = true;
    likeTable[0][1] = true;
    likeTable[0][3] = true;
    likeTable[2][3] = true;
    likeTable[3][0] = true;
    likeTable[3][2] = true;
    boolean[][][] wtf = new boolean[2][2][2];
    wtf[0] = likeTable;
    printTable(wtf[0]);
    String dog = "1011001010011000";
    sop("woof");
    printTable(convertToTable(dog));
    int a = 0;
    boolean[][] temp;
    final int n = 16;
    String[] woof = new String[100];
 
    for (int i = 0; i < Math.pow(2, n); i++) {
      String bin = Integer.toBinaryString(i);
      while (bin.length() < n)bin = "0" + bin;
      temp = convertToTable(bin);
      if(checkRules(temp)==true){ woof[a] = bin; a++;}}
 
 
    sop(a);
    for ( int i = 0; i < a; i ++)
    {printTable(convertToTable(woof[i]));
    sop("_____________________________");}
    // Rule 7 Everybody likes somebody. Meaning that for any likeTable[i][0-3] one of htese values must be true.
 
  }
}  // The algorithm will complete its task by going through each rule and fulfilling it by altering the values of the Table. It will however ruleCheck after each alteration to ensure that the world's adherence ot the rules is maintained.

Are you trying to generate 64K arrays?
A point of view: each array has 16 elements. If they were regarded as hex numbers they would range in value from 0x0000 to 0xFFFF. If you have a way to convert each number to a 4x4 array that would solve the problem.

The number would be converted to a 4x4 array of booleans. Say there was a method that would return an boolean[][] array with true elements where the number had a bit set to 1.

My idea would create 64K arrays from containing all false to all true to correspond with the numbers from 0 to 64K.

Where do tables 1,2,3, etc fit in this?

the problem I have is not so much the creation of the tables as the algorithm to do so

Can you explain what that means? If you can create 64K boolean[][] what is the algorithm you are talking about? Is there something else involved besides creating 64K arrays?

Originally Posted by LittleGreenMidget

And so forth. What algorithm is there to generate these tables besides a preposterously ugly bunch of for loops?

If I understand, you wish to generate all 2^16 forms of a 4x4 boolean array. I'm not sure why you wish to do so, but you can use recursion. In pseudo-code:

1) create an empty value (eg array)
2) Pass empty value to fill method, with index set to 0
3) fill method (value, index):
3a) if index is the max (eg value is full), then save the value and return.
3b) deep copy value twice, set index of first to false, index of second to true
3c) increment index, pass values from 3b and new index to fill method (3)
end fill method

Can you explain why you need 64k arrays? Each array has a one to one correspondence to a number from 0 to 64k. Given any number in that range, a unique 2D array can be created. Why do you need to create them before they are needed?

I need to generate 4x4 True/False tables that meet certain criteria.

If you only need a few that meet a criteria, why generate 64K of them?

Seems like a waste of resources to create 64K.
My approach was to set the values in the array from the 16 bits in the lower part of an int variable.
Test each bit by ANDing it with an int variable that has a 1 in the location to test. If results are not 0, set the array element true. Start with 0x8000 and shift right 1 bit after each test.
There are 16 bits and 16 elements in an array. Use nested loops.