Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 17 of 17

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

  1. #1
    Junior Member
    Join Date
    Sep 2012
    Posts
    8
    My Mood
    Yeehaw
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.
    Last edited by LittleGreenMidget; September 26th, 2012 at 12:56 AM.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2012
    Posts
    8
    My Mood
    Yeehaw
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Sep 2012
    Posts
    8
    My Mood
    Yeehaw
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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?

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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?

    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?
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

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

    Quote Originally Posted by LittleGreenMidget View Post
    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

  8. #8
    Junior Member
    Join Date
    Sep 2012
    Posts
    8
    My Mood
    Yeehaw
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.

  9. #9
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  10. #10
    Junior Member
    Join Date
    Sep 2012
    Posts
    8
    My Mood
    Yeehaw
    Thanks
    2
    Thanked 0 Times in 0 Posts

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

    First comment edited.

  11. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

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

    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?
    If you don't understand my answer, don't ignore it, ask a question.

  12. #12
    Junior Member
    Join Date
    Sep 2012
    Posts
    8
    My Mood
    Yeehaw
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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.

  13. #13
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  14. The Following User Says Thank You to Norm For This Useful Post:

    LittleGreenMidget (September 26th, 2012)

  15. #14
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

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

    // 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.

  16. #15
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

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

    [Edit] forget what I said about conditions being pairs of numbers. That not expressive enough to capture rule 4.

  17. The Following User Says Thank You to pbrockway2 For This Useful Post:

    LittleGreenMidget (September 26th, 2012)

  18. #16
    Junior Member
    Join Date
    Sep 2012
    Posts
    8
    My Mood
    Yeehaw
    Thanks
    2
    Thanked 0 Times in 0 Posts

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

    Bump for thank you note and revised code.

  19. #17
    Forum VIP
    Join Date
    Oct 2010
    Posts
    275
    My Mood
    Cool
    Thanks
    32
    Thanked 54 Times in 47 Posts
    Blog Entries
    2

    Default 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.

Similar Threads

  1. pdf generation
    By deependeroracle in forum File I/O & Other I/O Streams
    Replies: 5
    Last Post: July 22nd, 2012, 01:11 AM
  2. PDF generation
    By deependeroracle in forum JDBC & Databases
    Replies: 2
    Last Post: June 26th, 2012, 10:29 AM
  3. [SOLVED] Help with password generation
    By Dr.Code in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 25th, 2012, 06:36 AM
  4. Okay Here Goes...World and Map Generation.
    By rooster5105 in forum Algorithms & Recursion
    Replies: 1
    Last Post: October 30th, 2011, 02:45 PM
  5. Boolean method returning a boolean value
    By Deprogrammer in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 21st, 2010, 10:56 AM