generate a truth table given an input ?

Question

Hello , Is there a smart algorithm that takes a number of probabilities and generates the corresponding truth table inside a multi-dimensional array or container

Ex :

n = 3
N : [0 0 0
     0 0 1
     0 1 0 
     ...
     1 1 1] 

I can do it with for loops and Ifs , but I know my way will be slow and time consuming . So , I am asking If there is an advanced feature that I can use to do that as efficient as possible ?

Answer 1

You want to write the numbers from 0 to 2^N - 1 in binary numeral system. There is nothing smart in it. You just have to populate every cell of the two dimensional array. You cannot do it faster than that.

You can do it without iterating directly over the numbers. Notice that the rightmost column is repeating 0 1, then the next column is repeating 0 0 1 1, then the next one 0 0 0 0 1 1 1 1 and so on. Every column is repeating 2^columnIndex(starting from 0) zeros and then ones.

Answer 2

You can split his problem into two sections by noticing each of the rows in the matrix represents an n bit binary number where n is the number of probabilities[sic].

so you need to:

• iterate over all n bit numbers
• convert each number into a row of your 2d container

edit:

if you are only worried about runtime then for constant n you could always precompute the table, but it think you are stuck with O(2^n) complexity for when it is computed

Answer 3

To elaborate on jk's answer... If you have n boolean values ("probabilities"?), then you need to

• create a truth table array that's n by 2^n
• loop i from 0 to (2^n-1)
• inside that loop, loop j from 0 to n-1
• inside THAT loop, set truthTable[i][j] = jth bit of i (e.g. (i >> j) & 1)

Answer 4

If we're allowed to fill the table with all zeroes to start, it should be possible to then perform exactly 2^n - 1 fills to set the 1 bits we desire. This may not be faster than writing a manual loop though, it's totally unprofiled.

EDIT: The line std::vector<std::vector<int> > output(n, std::vector<int>(1 << n)); declares a vector of vectors. The outer vector is length n, and the inner one is 2^n (the number of truth results for n inputs) but I do the power calculation by using left shift so the compiler can insert a constant rather than a call to, say, pow. In the case where n=3 we wind up with a 3x8 vector. I organize it in this way (rather than the customary 8x3 with row as the first index) because we're going to take advantage of a column-based pattern in the output data. Using the vector constructors in this way also ensures that each element of the vector of vectors is initialized to 0. Thus we only have to worry about setting the values we want to 1 and leave the rest alone.

The second set of nested for loops is just used to print out the resulting data when it's done, nothing special there.

The first set of for loops implements the real algorithm. We're taking advantage of a column-based pattern in the output data here. For a given truth table, the left-most column will have two pieces: The first half is all 0 and the second half is all 1. Since we pre-filled zeroes, a single fill of half the column height starting halfway down will apply all the 1s we need. The second column will have rows 1/4th 0, 1/4th 1, 1/4th 0, 1/4th 1. Thus two fills will apply all the 1s we need. We repeat this until we get to the rightmost column in which case every other row is 0 or 1.

We start out saying "I need to fill half the rows at once" (unsigned num_to_fill = 1U << (n - 1);). Then we loop over each column. The first column starts at the position to fill, and fills that many rows with 1. Then we increment the row and reduce the fill size by half (now we're filling 1/4th of the rows at once, but we then skip blank rows and fill a second time) for the next column.

For example:

#include <iostream>
#include <vector>

int main()
{
    const unsigned n = 3;
    std::vector<std::vector<int> > output(n, std::vector<int>(1 << n));

    unsigned num_to_fill = 1U << (n - 1);
    for(unsigned col = 0; col < n; ++col, num_to_fill >>= 1U)
    {
        for(unsigned row = num_to_fill; row < (1U << n); row += (num_to_fill * 2))
        {
            std::fill_n(&output[col][row], num_to_fill, 1);
        }
    }

    // These loops just print out the results, nothing more.
    for(unsigned x = 0; x < (1 << n); ++x)
    {
        for(unsigned y = 0; y < n; ++y)
        {
            std::cout << output[y][x] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Answer 5

Karnaugh map or Quine-McCluskey

http://en.wikipedia.org/wiki/Karnaugh_map http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm

That should head you in the right direction for minimizing the resulting truth table.