# Random selections.
import random
# Permutations and combinations.
import itertools
# Constant function.
def f_a(x):
return 1
f_a(0)
1
f_a(1)
1
# Constant function.
def f_b(x):
return 0
f_b(0)
0
f_b(1)
0
# Balanced function.
def f_c(x):
return x
f_c(0)
0
f_c(1)
1
# Balanced function.
def f_d(x):
return ((x + 1) % 2)
f_d(0)
1
f_d(1)
0
x | f_a(x) | f_b(x) | f_c(x) | f_d(x) |
---|---|---|---|---|
0 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 0 |
# Put the four functions in a list.
funcs = [f_a, f_b, f_c, f_d]
# Select a function from the list at random.
random.choice(funcs)
<function __main__.f_c(x)>
f = random.choice(funcs)
f(0)
0
f(1)
1
We had to check 2 inputs to determine whether the function was balanced or constant.
x1 | x2 | f | f | f | f | f | f | f | f | f | f | f | f | f | f | f | f |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 |
# Number of input bits.
n = 2
# The zeros constant function.
[0] * 2**n
[0, 0, 0, 0]
# The ones constant function.
[1] * 2**n
[1, 1, 1, 1]
# Generate the balanced functions.
# Adapted from https://stackoverflow.com/a/43817007
def balanced_functions(noinputbits):
# The length of the list is 2 to power of noinputbits.
size = 2**noinputbits
# The nubmer of ones is half the length of that list.
count = size // 2
# Generate all positions for 1's.
for positions in itertools.combinations(range(size), count):
# Create a list of zeros.
p = [0] * size
# Set positions to 1's.
for i in positions:
p[i] = 1
# Generate the list.
yield p
list(balanced_functions(2))
[[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1]]
# Generate all the constant and balanced functions.
def generate_functions(n):
return list(balanced_functions(n)) + [[0] * 2**n, [1] * 2**n]
# Generate all functions.
generate_functions(n)
[[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1], [0, 0, 0, 0], [1, 1, 1, 1]]
def randomf(n):
# Get all balanced and constant functions as lists.
funcs = generate_functions(n)
# Return a random function as a list.
return random.choice(funcs)
# Call randomf for two input bits.
f = randomf(2)
# It's just a list for now.
f
[1, 0, 0, 1]
# Let's make it a function.
def randomf(n):
# Get all balanced and constant functions as lists.
funcs = generate_functions(n)
# Pick one at random.
retvals = random.choice(funcs)
# Create a function from the list.
def f(*x):
# Reverse the bits.
x = x[::-1]
# Running total for position in list for output bit.
retpos = 0
# Loop through the elements in x (reversed).
for i in range(len(x)):
# Multiply i pos of x by 2^i.
retpos = retpos + (x[i] * 2**i)
# List position.
return retvals[retpos]
# Function returns a function.
return f
# Get a random function that takes two bits as input.
randomf(2)
<function __main__.randomf.<locals>.f(*x)>
# Get a random function that takes two bits as input.
f = randomf(2)
# Sample calls.
f(1, 1)
1
# Sample calls.
f(0, 1)
1
# Number of input bits.
n = 2
# Generate a random constant or balanced function
# with n in put bits.
f = randomf(n)
# Adapted from: https://stackoverflow.com/a/35313967
list(itertools.product(*[(0, 1)] * n))
[(0, 0), (0, 1), (1, 0), (1, 1)]
def balanced_or_constant(f, n):
# Presume f is constant.
constant = True
# Last returned value.
last = None
# Keep track of number of iterations.
i = 0
# Loop through all possible inputs.
for inputs in itertools.product(*[(0, 1)] * n):
# Try this input on f.
current = f(*inputs)
# Print a debug message.
print(f"Trying: {inputs} Return: {current} Last: {last}")
# Compare last to current.
if last is not None and current != last:
# Tell the user f is balanced.
constant = False
break
last = current
# Increment the iteration count.
i = i + 1
# Have we performed 2**(n-1) + 1 iterations.
if i > 2**(n-1):
break
if constant:
print("Constant")
else:
print("Balanced")
balanced_or_constant(f, n)
Trying: (0, 0) Return: 0 Last: None Trying: (0, 1) Return: 0 Last: 0 Trying: (1, 0) Return: 0 Last: 0 Constant
# Five input bits.
n = 4
# Generate random function.
f = randomf(n)
# Test if balanced.
balanced_or_constant(f, n)
Trying: (0, 0, 0, 0) Return: 1 Last: None Trying: (0, 0, 0, 1) Return: 0 Last: 1 Balanced