Truth Table Generation

Question

Anybody have thoughts on generating a row of a truth table with out creating the entire table. For example, a user would enter in a row number and that truth table row is generated. Also, this should be done without creating the table until you get to that row number. Essentially, I want to know if there is an efficient way to calculate a truth row value only based on a the truth table row as an input.

Example: Assume 3 variables printTruthTableRow(3) would produce 010

Actually, could I just convert the input-1 to a binary value to get that truth table row?

EDIT: Let me give you guys a little more background. I am wrote a basic DPLL SAT Solver in Java. My goal is to have a bunch of threads run the solver to solve the n-Queen problem. Currently, my algorithm generate a row of a truth table, one at a time, then feeds it to a thread to solve. The problem is that my truth table generation cannot be done concurrently by the threads. If a thread grabs a truth table row, it must lock the method, generate a row, and then unlock. I can increase speedup if less work is done when generating a truth table row. I can just convert an atomic count value to binary and have the thread test that. Thank you all for the answers.

Answer 1

Would the first row be row 0 or 1? If 0 then you'd basically just have to convert the row number to its binary representation, e.g. if you have 3 boolean variables do something like

0 -> 0 0 0
1 -> 0 0 1
2 -> 0 1 0
3 -> 0 1 1
...

Then use those bits and your truth function to calculate the result.

Answer 2

You would need to know the function to generate the row for and what values in the inputs correspond to that row. Once you know those two things the implementation is trivial.

For example if function is AND and row 3 is 0,1 then the row is 0, 1, 0 AND 1 - which is 0,1,0

But how do you know what values the inputs have for that row? That entirely depends on how you lay out the table but it should be possible to calculate from the row - probably using bit masking and shifting operators.

Answer 3

it seems, you are talking a little bit about a mapping.

if you are interested in truth tables, then check this out.

Answer 4

You can choose to use a data structure that only holds the rows you have created. You might consider something like HashMap<int,boolean[] truthinfo>. The rest is left as an exercise for the questioner.