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

• September 25th, 2012, 04:18 PM
LittleGreenMidget
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.

Code :

```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.```
• September 25th, 2012, 04:40 PM
Norm
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
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.
• September 25th, 2012, 04:54 PM
LittleGreenMidget
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
I'm afraid so. That is precisely what I'm trying to do. Would using the hex numbers system still allow me to store the value of each point on the array however? I need to maintain the true / false value of each point.
• September 25th, 2012, 05:00 PM
Norm
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
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.
• September 25th, 2012, 05:20 PM
LittleGreenMidget
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
I think I see where you're going with this but the problem I have is not so much the creation of the tables as the algorithm to do so. What I mean by that is this :

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 [ ] [ ] [ ] [ ]

And so forth. What algorithm is there to generate these tables besides a preposterously ugly bunch of for loops?
• September 25th, 2012, 05:27 PM
Norm
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
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?

Quote:

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?
• September 25th, 2012, 05:30 PM
copeg
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
Quote:

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
• September 25th, 2012, 05:50 PM
LittleGreenMidget
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
To clarify the reason I need 2^16 arrays is because I am trying to create every possible variation of a 4x4 2d boolean array. That is where the tables come in, they are a sample of the 65536 tables I actually need to make.
That is to say in each table the true and false value will not be the same.
• September 25th, 2012, 05:54 PM
Norm
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
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?
• September 25th, 2012, 06:00 PM
LittleGreenMidget
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
First comment edited.
• September 25th, 2012, 06:13 PM
Norm
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
Quote:

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?
• September 25th, 2012, 07:26 PM
LittleGreenMidget
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
Because there are 7 criteria and some criteria are interdependent which leads me to believe that an algorithm which generates only tables which meet the criteria is immeasurably more complex than generating all tables and testing the ones that match. If you would like me to elaborate further I would absolutely love to. Thank you for your time btw.
• September 25th, 2012, 08:23 PM
Norm
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
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.
• September 25th, 2012, 08:52 PM
pbrockway2
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
Quote:

// Rule 1 Dana Likes Cody in terms of table values it is necessary that likeTable[3][0] is always true.
...
// Rule 3 Cody does not like Abby, therefore likeTable[2][0] is always False
I'm having a hard time figuring out these tables. Does Cody correspond to 3 or 2? Or zero in which case should rule 3 say Table[0][2] is false?

---

In any case I agree with Norm. A four by four boolean table corresponds naturally to a 16 bit number. (you have a certain amount of choice about whether you read off the bits across the rows or down the columns, left/right vs right/left etc). Every such number - that is every number between 0 and 64K - corresponds to a table and vice versa. There's no reason to create these numbers in advance.

If you want to check by brute force which numbers (tables) satisfy a bunch of conditions, the problem would seem to be how to express the *conditions*, not the tables. The conditions are also tables, but three valued ones: must be true, must be false, or can be either. One way of expressing such a condition is with a pair of numbers 0-64K. Basically a given likes table satisfies a condition if for each bit it matches the corresponding bit in either (or both) condition tables.

There is no work needed to construct the likes tables. They are just a number 0->64K and probably occur as the index variable in a for loop. The work is in expressing the seven conditions as seven pairs of tables ie as seven pairs of 16 bit numbers.
• September 25th, 2012, 08:59 PM
pbrockway2
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
 forget what I said about conditions being pairs of numbers. That not expressive enough to capture rule 4.
• September 26th, 2012, 12:56 AM
LittleGreenMidget
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
Bump for thank you note and revised code.
• September 26th, 2012, 10:47 AM
Tjstretch
Re: Need algorithm for generation of all variations of a 4x4 boolean table.
Instead of making 64k arrays and checking them, make the arrays such that they will always follow the rules, and cancel the array when it fails.