# Returning functions.
def power(e):
"""Returns a single argument function that raises the argument to e."""
# Define the function f. It is local to the function power.
def f(x):
# This is f's return value. Note it uses power's e variable.
return x**e
# This is power's return value. It's the function f.
# Note that in some sense f will live longer than power even though it's "local".
return f
# Call the power function, square is a function.
square = power(2)
# Call square.
square(5)
25
# A constant function.
def bitstobit(x0, x1, x2):
return 1
# Always returns 1.
bitstobit(1, 0, 1)
1
# Always returns 1.
bitstobit(0, 0, 0)
1
# Print all possible inputs/outputs.
print(" x0 x1 x2 f")
for x0 in [0, 1]:
for x1 in [0, 1]:
for x2 in [0, 1]:
print(f"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}")
x0 x1 x2 f 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
$ 000 \rightarrow (0 \times 2^0) + (0 \times 2^1) + (0 \times 2^2) = 0 \\ 001 \rightarrow (0 \times 2^0) + (0 \times 2^1) + (1 \times 2^2) = 1 \\ 010 \rightarrow (0 \times 2^0) + (1 \times 2^1) + (0 \times 2^2) = 2 \\ 011 \rightarrow (0 \times 2^0) + (1 \times 2^1) + (1 \times 2^2) = 3 \\ 100 \rightarrow (1 \times 2^0) + (0 \times 2^1) + (0 \times 2^2) = 4 \\ 101 \rightarrow (1 \times 2^0) + (0 \times 2^1) + (1 \times 2^2) = 5 \\ 110 \rightarrow (1 \times 2^0) + (1 \times 2^1) + (0 \times 2^2) = 6 \\ 111 \rightarrow (1 \times 2^0) + (1 \times 2^1) + (1 \times 2^2) = 7 \\ $
# A balanced function.
def bitstobit(x0, x1, x2):
# Return values.
vals = [0, 1, 0, 1, 0, 1, 0, 1]
# Get the retun value's index in vals.
# e.g. 010 -> (0 x 2^0) + (1 x 2^1) + (0 x 2^2)
i = x0 * 2**0 + x1 * 2**1 + x2 * 2**2
# Return the correct value.
return vals[i]
bitstobit(1, 0, 0)
1
bitstobit(1, 1, 1)
1
# Print all possible inputs/outputs.
print(" x0 x1 x2 f")
for x0 in [0, 1]:
for x1 in [0, 1]:
for x2 in [0, 1]:
print(f"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}")
x0 x1 x2 f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
import itertools as it
# No of bits in input.
nobits = 2
# Generate all length four binary tuples, then transpose.
funcs = list(zip(*it.product([0,1], repeat=2**nobits)))
# Generate all possible values of two bits.
bits = list(it.product([0,1], repeat=nobits))
# Print a header.
th = [f"x{i}" for i in range(nobits)] + [f"f{i}" for i in range(2**2**nobits)]
print(" ".join([(" " + h)[-5:] for h in th] ))
# Print the functions.
for i in range(len(bits)):
print(" ".join([f"{j:5d}" for j in bits[i]] + [f"{j:>5d}" for j in funcs[i]]))
x0 x1 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
import random
def f_bitstobit():
"""Creates a function mapping three bits to 1.
The function is randomly either constant or balanced."""
# Randomly decide if we're balanced or constant.
if random.random() < 0.5:
# List of eight bits, four 0's and four 1's.
vals = [0, 1] * 4
else:
# Pick 0 half the time, 1 half the time.
if random.random() < 0.5:
# Eight 1 bits.
vals = [1] * 8
else:
# Eight 0 bits.
vals = [0] * 8
# Randiomly shuffle the values.
random.shuffle(vals)
# Construct the function. Note this is a function within a function.
def f(x0, x1, x2):
# Get the retun value's index in vals.
i = x0 * 2**0 + x1 * 2**1 + x2 * 2**2
# Return the correct value.
return vals[i]
# Return the function f. Note it will live on beyond this function.
return f
# Create the function. We don't know if its constant of balanced.
bitstobit = f_bitstobit()
# Do a test run of the function.
bitstobit(1, 0, 1)
0
bitstobit
to determine if it is constant or balanced?bitstobit
to determine if it is constant or balanced?bitsttobit
, what is the probability it is balanced?Write a function called isbalanced
that takes a bitstobit
function as an input and returns True if it is definitely balanced and False otherwise.
def isbalanced(bitstobit):
"""Returns True if bitstobit is balanced, False otherwise."""
# Make this function work here.
return True
# This is how the above function will be called.
# Create a new random bitstobit function.
bitstobit = f_bitstobit()
# Check if it's balanced.
isbalanced(bitstobit)
True
# This should check that it works.
# Print all possible inputs/outputs.
print(" x0 x1 x2 f")
for x0 in [0, 1]:
for x1 in [0, 1]:
for x2 in [0, 1]:
print(f"{x0:4d} {x1:4d} {x2:4d} {bitstobit(x0, x1, x2):4d}")
x0 x1 x2 f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
def f_bitstobit(k=3):
"""Creates a function mapping k bits to 1.
The function is randomly either constant or balanced."""
# Randomly decide if we're constant or balanced.
if random.random() < 0.5:
# List of 2^k bits, 2^(k-1) 0's and 2^(k-1) 1's.
vals = [0, 1] * (2**(k-1))
else:
# Pick 0 half the time, 1 half the time.
if random.random() < 0.5:
# 2^k 1's.
vals = [1] * (2**k)
else:
# 2^k 0's.
vals = [0] * (2**k)
# Shuffle the values.
random.shuffle(vals)
# Construct the function.
def f(xs):
# Get the retun value's index in vals.
i = sum([(xs[i] * 2**i) for i in range(len(xs))])
# Return the correct value.
return vals[i]
# Return f.
return f
# Number of inputs bits.
k = 4
bitstobit = f_bitstobit(k)
# Make sure the bits are in a list or tuple.
t = [random.choice([0,1]) for i in range(k)]
t
[0, 0, 0, 1]
# Example of calling bitstobit.
bitstobit(t)
0
import itertools
print("".join([f" x{i}" for i in range(k)]) + " f")
for x in itertools.product([0,1], repeat=k):
print("".join([f"{i:4d}" for i in x]) + f" {bitstobit(x)}")
x0 x1 x2 x3 f 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0
import timeit
timeit.timeit(lambda: bitstobit([random.choice([0,1]) for i in range(k)]))
4.3679002