A Boolean function of n variables can be represented by its truth table, which gives its value for all 2n combinations of the input variables. This can be represented by a string of length 2n containing only characters 0 and 1. If the n variables are x0,x1,...,xn−1, then the value of the function for an input xi = bi,bi ∈{0,1}, is given by the character in the string at position . Thus the OR function of 2 variables is represented by the string 0111 and the AND by 0001.
Two such functions f(x0,...,xn−1) and g(x0,...,xn−1) are said to be equivalent if there exists a permutation p of {0,1,...,n−1} such that for all sequences b0,...,bn−1 of n bits, f(b0,b1,...,bn−1) = g(bp[0],bp[1],...,bp[n−1]). In other words, the expression for g is obtained from that of f by permuting the input variables.
Given a sequence of boolean functions represented as strings, you have to compute the number of distinct (inequivalent) functions in the sequence.
There is no simple algorithm to check equivalence and essentially the only way is try all possible permutations. However, the number of such checks can be reduced by using hash functions. Suppose there is a function h that maps strings to integers in the range {0,...,B − 1} with the property that equivalent functions map to the same value. Then we only need to check equivalence between functions whose hash value is the same. A simple hash function is the number of 1’s in the string.
In the first part of the problem, you can use this simple function, and the brute force algorithm for checking equivalence. The inputs will be small in size for this part, and correctness should be ensured.
Input/Output The first line will specify n the number of variables and m the number of strings. The next m lines will contain a string of 0,1 of length 2n, one per line. The output should be the number of inequivalent functions among the m given. For the first part, n ≤ 8 and m ≤ 1000. For the 2nd part, you should try to do as best as possible, with say 2n ∗m ≤ 107, and n at most 20. Experiment with random strings containing the same number of 1’s. There is no time limit as such, will compare with whatever I can do with simple hash functions.
1
Sample Input Sample Output
2 5 3
0000
0100
0101
0011
0010
Submission: Submit a single file named RollNo 10.cpp
2
