Find all points $\vec{x} \in \mathbb{R}^3$ such that $f(\vec{x}) = \sum_i x_i \vec{b}_i < C$ where $x_i$ are integers and $C$ is a real positive constant.
In [1]:
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
%matplotlib notebook
In [2]:
def neighbors(x, C, b):
sol_n = []
all_n = [x + np.array([ 1, 0, 0]),
x + np.array([-1, 0, 0]),
x + np.array([ 0, 1, 0]),
x + np.array([ 0, -1, 0]),
x + np.array([ 0, 0, 1]),
x + np.array([ 0, 0, -1])]
for y in all_n:
if np.linalg.norm(y[0]*b[0] + y[1]*b[1] +y[2]*b[2]) < C:
sol_n.append(tuple(y)) # must be hashable
return sol_n
# Depth-first search
def dfs(neighbors, root, C, b):
visited, stack = set(), [root]
while stack:
x = stack.pop()
if x not in visited:
visited.add(x)
stack.extend(neighbors(x, C, b))
return visited
In [3]:
b = [np.array([3., 0, 0]),
np.array([0, 2., 0]),
np.array([0, 0, 1]),]
solutions = dfs(neighbors, (0, 0, 0), 10., b)
In [4]:
fig = plt.figure()
ax = fig.add_subplot(111, projection="3d")
for x in solutions:
ax.scatter(x[0], x[1], x[2], c="r", marker="o")
print(solutions)
{(1, 2, 8), (0, -1, 9), (0, -2, 9), (-1, -2, -8), (-1, -1, -8), (-3, 0, -3), (0, 0, 8), (-3, -1, 3), (1, 4, 4), (1, 1, -3), (1, -3, 1), (3, 0, 3), (0, -1, -3), (0, -2, -3), (0, 2, 1), (2, 1, -4), (-1, -3, -4), (-2, -3, -4), (-1, 3, 2), (-2, 3, 2), (-1, 0, -5), (2, 0, 7), (-2, 0, -5), (0, -3, 0), (0, 3, -2), (0, 3, -1), (1, 2, 0), (1, -4, -1), (1, -4, -2), (0, 1, 8), (2, -1, 5), (2, -2, 5), (-2, 2, 5), (-1, 2, 5), (0, 0, -6), (-1, 4, 1), (0, 4, 2), (1, 3, 7), (-1, 1, 1), (-2, 1, 1), (2, -3, 1), (1, 0, -1), (1, 0, -2), (1, -1, 0), (1, -2, 0), (0, 1, -3), (0, 1, 0), (1, -1, -3), (1, 0, 3), (1, -2, -3), (-1, 1, -8), (1, 3, -6), (-1, 1, 9), (-1, 4, -4), (0, 0, 7), (1, -1, 8), (2, -1, -4), (2, -2, -4), (1, 1, 8), (1, -2, 8), (-2, 2, -4), (-1, 2, -4), (-1, -1, 9), (1, 2, -3), (1, -4, 3), (3, 1, -3), (0, -3, -3), (0, 3, 3), (-1, 0, 2), (2, 0, -2), (2, 0, -1), (-1, -4, -1), (-1, -4, -2), (-2, 0, 2), (-1, -3, 5), (-2, -3, 5), (-1, 3, -5), (2, 1, 5), (-2, 3, -5), (0, -1, 0), (0, -2, 0), (0, 2, -4), (1, 1, 0), (1, -3, -4), (1, 4, -3), (-1, -2, 1), (-1, -1, 1), (-2, -1, 1), (-2, -2, 1), (-3, 0, 4), (0, 2, 8), (2, 2, 1), (0, -1, 8), (0, -2, 8), (1, 4, 5), (3, 0, 4), (1, 1, -4), (1, -3, 0), (0, -1, -4), (0, -2, -4), (0, 2, 0), (2, 1, -3), (-1, -3, -3), (-2, -3, -3), (-1, 3, 3), (-2, 3, 3), (-1, 0, -6), (2, 0, 6), (-2, 0, -6), (0, -3, 1), (3, 1, 3), (1, 2, 1), (-1, -1, -9), (0, 1, 9), (2, -1, 4), (1, 0, 8), (2, -2, 4), (-2, 2, 4), (-1, 2, 4), (0, 0, -7), (-1, 4, 0), (3, -1, -3), (0, 4, 1), (1, 3, 6), (-1, 1, 6), (-2, 1, 6), (1, -1, 1), (1, -2, 1), (0, 1, -2), (0, 1, -1), (0, 1, 1), (1, 0, 0), (1, -1, -2), (1, -1, -1), (1, -2, -1), (1, -2, -2), (-1, 1, -7), (-2, 1, -7), (1, 3, -7), (0, 4, -1), (0, 4, -2), (0, 0, 6), (1, 0, -9), (1, -1, 9), (2, -1, -5), (2, -2, -5), (-2, 2, -5), (-1, 2, -5), (-1, -1, 8), (-1, -2, 8), (1, 2, -2), (1, 2, -1), (1, -4, 0), (0, -3, -1), (0, -3, -2), (0, 3, 0), (-1, 0, 5), (2, 0, -7), (-2, 0, 5), (2, 1, 2), (-1, -3, 2), (-2, -3, 2), (-1, 3, -4), (-2, 3, -4), (0, -1, 3), (0, -2, 3), (1, 1, 3), (-1, -2, 0), (0, -1, -9), (0, -2, -9), (-1, -1, 0), (-2, -1, 0), (-2, -2, 0), (2, 2, 0), (0, 2, -9), (-1, -2, -2), (-1, -2, -1), (-1, -1, -1), (-1, -1, -2), (-2, -1, -1), (-2, -1, -2), (-2, -2, -2), (1, -3, 3), (-2, -2, -1), (1, 4, 2), (0, 2, 3), (2, 1, -6), (-1, -3, -6), (-1, 3, 4), (-2, 3, 4), (-1, 0, -3), (2, 0, 1), (-1, -4, 1), (-2, 0, -3), (0, -3, 2), (0, 3, -4), (3, 1, 2), (1, 2, 2), (1, -4, -4), (1, 1, -9), (2, -1, 3), (1, -1, -9), (1, 0, 9), (2, -2, 3), (-2, 2, 3), (0, 0, -8), (-1, 2, 3), (-1, 4, 3), (0, 4, 0), (1, 3, 5), (-1, 1, 7), (-2, 1, 7), (2, 2, -1), (2, 2, -2), (1, 0, -4), (1, -1, 2), (1, -2, 2), (0, 1, 2), (1, 0, 1), (-1, 1, -1), (-1, 1, -2), (-2, 1, -1), (-2, 1, -2), (2, 3, 0), (2, -3, -1), (0, -4, 5), (0, 4, -3), (2, -3, -2), (-1, 4, -2), (0, 0, 5), (-1, 4, -1), (2, -1, -6), (2, -2, -6), (-2, 2, -6), (-1, 2, -6), (0, 1, -9), (1, -4, 1), (0, 3, 1), (-1, 0, 4), (-2, 0, 4), (2, 1, 3), (-1, -3, 3), (-2, -3, 3), (-1, 3, -3), (-2, 3, -3), (0, -1, 2), (0, -2, 2), (0, 2, -2), (0, 2, -1), (1, 1, 2), (1, -3, -2), (1, -3, -1), (0, 0, -9), (1, 4, -5), (-1, -2, 7), (-1, -1, 7), (-2, -1, 7), (-3, 0, 2), (3, 0, -4), (3, -1, 2), (-1, -2, -3), (-1, -1, -3), (-2, -1, -3), (-2, -2, -3), (1, 4, 3), (2, 2, -3), (1, 1, -1), (1, 1, -2), (1, -3, 2), (0, -1, -2), (0, -1, -1), (0, -2, -1), (0, -2, -2), (0, 2, 2), (2, 1, -5), (-1, -3, -5), (-2, -3, -5), (-1, 3, 5), (-2, 3, 5), (-1, 0, -4), (2, 0, 0), (-1, -4, 0), (-2, 0, -4), (0, -3, 3), (0, 3, -3), (3, 1, 1), (1, 2, 3), (1, -4, -3), (0, 1, -8), (-3, 1, 1), (2, -1, 2), (2, -2, 2), (-2, 2, 2), (-1, 2, 2), (-1, 4, 2), (-1, 1, -9), (1, 3, 4), (-1, 1, 4), (-2, 1, 4), (2, -3, 4), (1, 0, -3), (1, -1, 3), (1, -2, 3), (0, 1, 3), (1, 2, -8), (1, -1, -8), (1, 0, 6), (1, -2, -8), (2, 3, 1), (0, -4, 4), (0, 4, -4), (0, -1, 5), (0, -2, 5), (0, 2, -7), (3, 2, -1), (0, 0, 4), (-3, 2, 0), (2, -1, -7), (-1, 2, -7), (0, 3, 6), (-1, 0, 7), (2, 0, -5), (-1, -4, -5), (-2, 0, 7), (2, 1, 0), (-1, -3, 0), (-2, -3, 0), (-1, 3, -1), (-1, 3, -2), (3, -2, 1), (-2, 3, -2), (-2, 3, -1), (1, 1, -7), (1, -3, 5), (1, 1, 5), (1, -3, -7), (-1, -2, 6), (-1, -1, 6), (-2, -1, 6), (-2, -2, 6), (-3, -1, -3), (-3, 0, 3), (3, 0, -3), (3, -1, 3), (2, 2, 6), (-1, 0, -9), (0, -3, 4), (0, 3, -6), (-1, -2, -4), (-1, -1, -4), (-2, -1, -4), (-2, -2, -4), (1, 4, 0), (2, 2, -4), (0, 0, -1), (0, 0, -2), (-1, 4, 5), (0, -1, -7), (0, -2, -7), (0, 2, 5), (-1, 3, 6), (2, 0, 3), (-1, -4, 3), (3, 1, 0), (1, 0, -6), (1, -1, 4), (1, -2, 4), (1, 2, 4), (0, 1, -7), (-3, 1, 0), (2, -1, 1), (2, -2, 1), (-2, 2, 1), (-1, 2, 1), (1, 3, -1), (0, -4, 3), (1, 3, -2), (0, 4, -5), (0, -4, -2), (0, -4, -1), (1, 3, 3), (-1, 1, 5), (-2, 1, 5), (2, 3, -5), (2, -3, 5), (-3, 1, -3), (0, 1, 4), (1, 2, -7), (1, -1, -7), (1, 0, 7), (1, -2, -7), (3, 0, 0), (3, -1, -1), (-1, 1, -4), (-2, 1, -4), (2, 3, 2), (3, -1, -2), (3, -2, -1), (2, -3, -4), (0, -1, 4), (0, -2, 4), (0, 2, -8), (-3, 2, 1), (0, 0, 3), (-1, 2, -8), (0, -3, -7), (0, 3, 7), (-1, 0, 6), (2, 0, -6), (-2, 0, 6), (2, 1, 1), (-1, -3, 1), (-2, -3, 1), (-1, -2, -5), (-1, -1, -5), (-2, -2, -5), (-2, -1, -5), (-3, -2, 0), (-3, 0, -2), (-3, 0, -1), (1, 1, -8), (1, -3, 4), (-3, -1, 0), (1, 1, 4), (3, 0, -1), (3, -1, 0), (3, -2, 0), (-1, -2, 5), (-1, -1, 5), (-2, -1, 5), (-2, -2, 5), (-3, -2, -1), (-3, -1, -1), (-3, -1, -2), (-3, 0, 0), (2, 2, 5), (3, 0, -2), (0, -3, 5), (0, 3, -5), (1, 4, 1), (-1, 2, 8), (0, 0, -3), (-1, 4, 4), (0, -1, -8), (0, -2, -8), (0, 2, 4), (2, 1, -7), (-1, -3, -7), (-1, 3, 7), (-1, 0, -2), (-1, 0, -1), (2, 0, 2), (-1, -4, 2), (-2, 0, -2), (-2, 0, -1), (-1, 1, 2), (-2, 1, 2), (2, 3, -4), (2, -3, 2), (1, 0, -5), (1, -1, 5), (1, -2, 5), (1, 2, 5), (1, -4, -5), (0, 1, -6), (-3, 1, 3), (2, -1, 0), (2, -2, 0), (-2, 2, 0), (-1, 2, 0), (1, 3, -3), (0, -4, 2), (0, -4, -3), (1, 3, 2), (0, 4, 5), (0, 1, 5), (1, 2, -6), (1, -4, 4), (1, -1, -6), (1, 0, 4), (1, -2, -6), (-1, 1, -3), (-2, 1, -3), (2, 3, 3), (2, -3, -3), (-1, 0, 1), (2, 0, -3), (-1, -4, -3), (-2, 0, 1), (-1, -3, 6), (2, 1, 6), (0, -1, 7), (0, -2, 7), (0, 2, -5), (-1, 4, -5), (0, 0, 2), (1, 4, -2), (1, 4, -1), (0, -3, -6), (0, 3, 4), (-1, 0, 9), (-1, -2, -6), (-1, -1, -6), (-2, -2, -6), (-2, -1, -6), (-3, -2, 1), (-3, -1, 1), (2, 2, -6), (1, 1, -5), (1, -3, 7), (3, 0, 1), (1, 1, 7), (1, -3, -5), (-1, -2, 4), (-1, -1, 4), (-2, -1, 4), (-2, -2, 4), (-3, 0, 1), (2, 2, 4), (3, -1, 1), (2, 1, -1), (2, 1, -2), (-1, -3, -2), (-1, -3, -1), (-2, -3, -1), (-2, -3, -2), (-1, 3, 0), (-2, 3, 0), (-1, 0, -7), (2, 0, 5), (-1, -4, 5), (-2, 0, -7), (0, -3, 6), (2, -1, 7), (-1, 2, 7), (0, 0, -4), (3, 2, 0), (-3, 2, -1), (0, -1, -5), (0, -2, -5), (0, 2, 7), (-1, 1, 3), (-2, 1, 3), (2, 3, -3), (2, -3, 3), (1, 0, -8), (1, -1, 6), (1, -2, 6), (1, 2, 6), (0, 1, -5), (-3, 1, 2), (-1, 1, -6), (-2, 1, -6), (2, 3, 4), (1, 3, -4), (0, -4, 1), (0, -4, -4), (1, 3, 1), (0, 4, 4), (2, -1, -1), (2, -1, -2), (2, -2, -2), (2, -2, -1), (-2, 2, -2), (-2, 2, -1), (-1, 2, -1), (-1, 2, -2), (0, 1, 6), (1, 2, -5), (1, -4, 5), (1, -1, -5), (1, 0, 5), (1, -2, -5), (-1, 0, 0), (2, 0, -4), (-1, -4, -4), (-2, 0, 0), (-1, -3, 7), (-1, 3, -7), (2, 1, 7), (0, -1, 6), (0, -2, 6), (0, 2, -6), (0, 0, 1), (-1, -2, 3), (-1, -1, 3), (-2, -1, 3), (-2, -2, 3), (2, 2, 3), (0, -3, -5), (0, 3, 5), (-1, 0, 8), (-1, -2, -7), (-1, -1, -7), (-2, -1, -7), (-3, 0, -4), (0, 0, 9), (-3, -1, 2), (3, 0, 2), (1, 1, -6), (1, -3, 6), (1, 1, 6), (1, -3, -6), (-1, 3, 1), (-2, 3, 1), (-1, 0, -8), (2, 0, 4), (-1, -4, 4), (0, -3, 7), (0, 3, -7), (2, -1, 6), (2, -2, 6), (-2, 2, 6), (-1, 2, 6), (0, 0, -5), (3, 2, 1), (0, -1, -6), (0, -2, -6), (0, 2, 6), (0, -4, -5), (0, 4, 3), (-1, 1, 0), (-2, 1, 0), (2, 3, -2), (2, 3, -1), (2, -3, 0), (1, 0, -7), (1, -1, 7), (1, -2, 7), (1, 2, 7), (0, 1, -4), (1, -1, -4), (1, 0, 2), (1, -2, -4), (-1, 1, -5), (-2, 1, -5), (2, 3, 5), (2, -3, -5), (1, 3, -5), (0, -4, 0), (1, 3, 0), (-1, 1, 8), (-1, 4, -3), (2, -1, -3), (2, -2, -3), (-2, 2, -3), (-1, 2, -3), (1, 1, 9), (-3, 1, -1), (-3, 1, -2), (0, 1, 7), (1, 2, -4), (1, -4, 2), (3, 1, -1), (0, -3, -4), (0, 3, 2), (3, 1, -2), (-1, 0, 3), (-2, 0, 3), (-1, -3, 4), (-2, -3, 4), (-1, 3, -6), (2, 1, 4), (0, -1, 1), (0, -2, 1), (0, 2, -3), (0, 0, 0), (1, 1, 1), (1, -3, -3), (1, 4, -4), (-1, -2, 2), (-1, -1, 2), (-2, -1, 2), (-2, -2, 2), (0, 2, 9), (2, 2, 2), (2, 2, -5)}
Content source: dudektria/notebooks
Similar notebooks: