产生给定输入的真值表? [英] generate a truth table given an input?

问题描述

是否存在一种智能算法，该算法需要多个概率并在多维数组或容器内生成相应的真值表

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

例如:

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

我可以使用for循环和Ifs来做到这一点，但是我知道我的方法会很慢而且很耗时.因此，我问是否有一项高级功能可以用来使该功能尽可能高效?

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 ?

推荐答案

如果允许我们使用全零填充表，那么应该可以完全执行2^n - 1填充来设置我们的1位欲望.不过，这可能并不比编写手动循环快，因为它完全没有轮廓.

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.

第std::vector<std::vector<int> > output(n, std::vector<int>(1 << n));行声明了向量的向量.外部向量的长度为n，内部向量的长度为2^n(n个输入的真结果的数量)，但是我使用左移进行了幂计算，因此编译器可以插入一个常数而不是调用，例如， pow.在n=3的情况下，我们以3x8向量结束.我以这种方式组织它(而不是习惯将行作为第一个索引的8x3)，因为我们将在输出数据中利用基于列的模式.以这种方式使用vector构造函数还可以确保向量vector的每个元素都初始化为0.因此，我们只需要担心将想要的值设置为1，而不必担心剩下的值.

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.

第二套嵌套的for循环仅用于在完成后打印出结果数据，那里没什么特别的.

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

第一组for循环实现了实算法.我们在这里利用输出数据中基于列的模式.对于给定的真值表，最左边的列将包含两部分:前半部分全为0，后半部分全为1.由于我们预先填充了零，因此将应用一半填充的列高度的一半开始填充我们需要的所有1.第二列将具有行1/4th 0、1/4th 1、1/4th 0、1/4th1.因此，两个填充将应用我们需要的所有1.重复此操作，直到到达最右边的列，在这种情况下，每隔一行为0或1.

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.

我们开始说我需要一次填充一半的行"(unsigned num_to_fill = 1U << (n - 1);).然后，我们遍历每一列.第一列从要填充的位置开始，然后用1填充那么多行.然后我们增加该行并将填充大小减小一半(现在，我们一次填充了1/4行，但随后跳过了空白行，然后填充第二次).

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.

例如:

#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;
}

这篇关于产生给定输入的真值表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！