Как рассчитать все 24 вращения 3D-массива?
У меня есть 3d-массив, описывающий поликуб (представьте себе кусок 3d-тетриса). Как я могу рассчитать все 24 вращения?
Процедуры манипулирования массивом Numpy включают метод rot90, который дает 4 из 24, но я не знаю, как рассчитать остальное. Моя единственная идея - преобразовать трехмерный массив в двумерную матрицу координат, умножить на матрицу вращения и выполнить обратное преобразование. Но я бы предпочел работать напрямую с 3D-массивом.
Пример массива 2x2x2:
>>> from numpy import array
>>> polycube
array([[[1, 0],
[1, 0]],
[[1, 1],
[0, 0]]])
Пример массива 3х3х3:
array([[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]],
[[0, 0, 0],
[1, 0, 0],
[1, 0, 0]],
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]])
Редактировать: я хочу только 24 сохраняющих ориентацию изометрии, а не все 48 поворотов и отражений (хотя было бы интересно узнать, как их сделать тоже). Если это помогает проверить, я считаю, что пример 3x3x3 не имеет вращательной симметрии и является киральным (поэтому 48 различны).
Мотивация: я пишу решатель для головоломки Soma cube -style.
Ответы
Ответ 1
Пока у меня их 12, составляющих numpy.transpose для перестановки осей (xyz, yzx, zxy - все с одинаковыми руками) и rot90.
def rotations12(polycube):
for i in range(3):
polycube = numpy.transpose(polycube, (1, 2, 0))
for angle in range(4):
polycube = numpy.rot90(polycube)
yield polycube
Быстрый тест 12 различны: len(set(str(x) for x in rotations(polycube)))
Обновление: вот как я сделал все 24.
def rotations24(polycube):
# imagine shape is pointing in axis 0 (up)
# 4 rotations about axis 0
yield from rotations4(polycube, 0)
# rotate 180 about axis 1, now shape is pointing down in axis 0
# 4 rotations about axis 0
yield from rotations4(rot90(polycube, 2, axis=1), 0)
# rotate 90 or 270 about axis 1, now shape is pointing in axis 2
# 8 rotations about axis 2
yield from rotations4(rot90(polycube, axis=1), 2)
yield from rotations4(rot90(polycube, -1, axis=1), 2)
# rotate about axis 2, now shape is pointing in axis 1
# 8 rotations about axis 1
yield from rotations4(rot90(polycube, axis=2), 1)
yield from rotations4(rot90(polycube, -1, axis=2), 1)
def rotations4(polycube, axis):
"""List the four rotations of the given cube about the given axis."""
for i in range(4):
yield rot90(polycube, i, axis)
Используя эту вспомогательную функцию, обобщающую rot90 для вращения вокруг любой оси:
def rot90(m, k=1, axis=2):
"""Rotate an array k*90 degrees in the counter-clockwise direction around the given axis"""
m = numpy.swapaxes(m, 2, axis)
m = numpy.rot90(m, k)
m = numpy.swapaxes(m, 2, axis)
return m
Я не уверен, что этот помощник идеален, но, похоже, работает.
Ответ 2
Посмотрите на код для rot90. Я вижу 3 варианта flip и swapaxes зависимости от параметра оси k.
fliplr(m).swapaxes(0, 1)
fliplr(flipud(m))
fliplr(m.swapaxes(0, 1))
fliplr(m) - это просто m[:, ::-1], и неудивительно, что flipud - это m[::-1,...].
Вы можете перевернуть 3-ю ось с помощью m[:,:,::-1] или m[...,::-1].
np.transpose - это еще один инструмент для перестановки осей, который может или не может быть проще в использовании, чем swapaxes.
Если rot90 дает вам 4 из поворотов, вы сможете применить те же процедуры для создания других. Вы просто должны понять логику, лежащую в основе rot90.
например
def flipbf(m):
return m[:,:,::-1]
flipbf(m).swapaxes(0, 2)
flipbf(m).swapaxes(1, 2)
etc
Ответ 3
Изменение: так как мое решение в основном сводится к произведению четностей осей, умноженных на четность перестановки осей, самый простой метод для генерации всех регулярных вращений n-мерного массива это (пролистывание некоторого кода Форма @Divakar ответ):
import itertools as it
def p_parity(a):
a = np.asarray(a)
l = a.size
i, j = np.tril_indices(l, -1)
return np.product(np.sign(a[i] - a[j]))
def rotations_gen(m):
n = m.ndim
for i in it.product([-1, 1], repeat = n):
for p in it.permutations(np.arange(n)):
if np.product(i) * p_parity(p) == 1:
s = [slice(None, None, j) for j in i]
yield np.transpose(m[s], p)
Это работает для любых (даже неквадратных) тензоров произвольной размерности и основано непосредственно на определении регулярных вращений под тензорной алгеброй ниже.
Фон
Самый простой способ объяснить это в тензорных терминах, поэтому давайте превратим все эти вращения в тензоры вращения. Тензоры вращения - это nxn матрицы, которые вращают n-мерное пространство. Как таковые они имеют несколько свойств:
np.linalg.det(R) == 1 # determinant = 1
np.inner(R, R.T) == np.eye(R.shape[0]) # Transpose is inverse
Кроме того, для поворотов на 90 градусов все члены должны быть либо 0, 1, либо -1.
В трех измерениях есть три основных семейства, которые составляют вместе, чтобы сделать ваши 24 вращения.
Первая простая перестановка:
A =
[[[1, 0, 0],
[0, 1, 0],
[0, 0, 1]],
[[0, 1, 0],
[0, 0, 1],
[1, 0, 0]],
[[0, 0, 1],
[1, 0, 0],
[0, 1, 0]]]
Второе включает в себя отрицание некоторых членов, так что произведение диагонали всегда равно 1:
B =
[[[ 1, 0, 0],
[ 0, 1, 0],
[ 0, 0, 1]],
[[-1, 0, 0],
[ 0,-1, 0],
[ 0, 0, 1]],
[[-1, 0, 0],
[ 0, 1, 0],
[ 0, 0,-1]],
[[ 1, 0, 0],
[ 0,-1, 0],
[ 0, 0,-1]]]
И третий определяет, является ли перестановка положительной или отрицательной, и отрицает условия, если отрицательная
C =
[[[ 1, 0, 0],
[ 0, 1, 0],
[ 0, 0, 1]],
[[ 0, 0,-1],
[ 0,-1, 0],
[-1, 0, 0]],
Важным моментом в этих семействах является то, что в каждом семействе любой продукт, степень или транспонирование двух матриц дают другую матрицу в семействе. Поскольку у нас есть три семейства, их произведения друг с другом образуют все возможные вращения, в этом случае 3 * 4 * 2 = 24
Примечание: другие 24 "нерегулярных" вращения - это те же матрицы, умноженные на -np.eye(3) которые дают аналогичные матрицы с определителем = -1
заявка
Это все хорошо, но как это связано с манипулированием массивами? Мы не хотим вращаться с помощью умножения матриц, поскольку это приведет к чрезмерным затратам памяти и обработки. К счастью, каждая семья легко связана с манипулированием массивами, которое создает представление.
def A_(m, i): # i in (0, 1, 2)
idx = np.array([[0, 1, 2], [1, 2, 0], [2, 0, 1]])
return np.transpose(m, idx[i])
def B_(m, j): # j in (0, 1, 2, 3)
idx = np.array([[ 1, 1, 1],
[ 1,-1,-1],
[-1, 1,-1],
[-1,-1, 1]])
return m[::idx[j, 0], ::idx[j, 1], ::idx[j, 2]]
def C_(m, k): # k in (1, -1)
return np.transpose(m, np.arange(3)[::k])[::k, ::k, ::k]
Все они производят представления m, и вы можете создать генератор, который создает представления, относящиеся ко всем поворотам:
def cube_rot_gen(m):
for i in [0, 1, 2]:
for j in [0, 1, 2, 3]:
for k in [1, -1]:
yield C_(B_(A_(m, i), j), k)
Ответ 4
Другой вариант - объединить вращения вокруг оси куба, который представляет матрицу. Что-то вроде:
import numpy as np
"""
Basic rotations of a 3d matrix.
----------
Example:
cube = array([[[0, 1],
[2, 3]],
[[4, 5],
[6, 7]]])
axis 0: perpendicular to the face [[0,1],[2,3]] (front-rear)
axis 1: perpendicular to the face [[1,5],[3,7]] (lateral right-left)
axis 2: perpendicular to the face [[0,1],[5,4]] (top-bottom)
----------
Note: the command m[:, ::-1, :].swapaxes(0, 1)[::-1, :, :].swapaxes(0, 2) rotates the cube m
around the diagonal axis 0-7.
"""
def basic_rot_ax(m, ax=0):
"""
:param m: 3d matrix
:return: rotate the cube around axis ax, perpendicular to the face [[0,1],[2,3]]
"""
ax %= 3
if ax == 0:
return np.rot90(m[:, ::-1, :].swapaxes(0, 1)[::-1, :, :].swapaxes(0, 2), 3)
if ax == 1:
return np.rot90(m, 1)
if ax == 2:
return m.swapaxes(0, 2)[::-1, :, :]
def axial_rotations(m, rot=1, ax=2):
"""
:param m: 3d matrix
:param rot: number of rotations
:param ax: axis of rotation
:return: m rotate rot times around axis ax, according to convention.
"""
if len(m.shape) is not 3:
assert IOError
rot %= 4
if rot == 0:
return m
for _ in range(rot):
m = basic_rot_ax(m, ax=ax)
return m
Если я не ошибаюсь, 24 оборота, которые вы ищете, представляют собой комбинацию этих 9 преобразований.
Ответ 5
Мы начнем с намерения получить все 48 комбинаций, чтобы получить общее представление о решении этого для массива n-dim. Позже мы отфильтруем ненужные 24.
Общая идея, чтобы решить для всех вращений
Идея решения для общего случая состояла бы в том, чтобы в основном сделать две вещи - пролистать каждую ось и переставить оси со всеми комбинациями для данного числа осей.
Отразить: для переворота мы будем использовать параметр stepsize для нарезки, т.е. массив [:: stepsize]. Итак, чтобы перевернуть, это будет: [::-1] и без переворота, просто: [::1]. Этот stepsize может быть назначен как переменная, варьирующаяся от 1 до -1 для двух простых комбинаций. Для ndarray просто распространите это на все оси.
Перестановка осей: чтобы достичь этого, мы можем использовать np.transpose и указать требуемый перестановочный порядок в качестве параметра осей с ним. Мы сгенерируем все возможные заказы с помощью itertools.permutations.
Это все, что есть! Пусть реализовать с в качестве входного a 3D массива -
import itertools
def rotations48(a):
# Get all combinations of axes that are permutable
n = a.ndim
axcomb = np.array(list(itertools.permutations(range(n), n)))
# Initialize output array
out = np.zeros((6,2,2,2,) + a.shape,dtype=a.dtype)
# Run loop through all axes for flipping and permuting each axis
for i,ax in enumerate(axcomb):
for j,fx in enumerate([1,-1]):
for k,fy in enumerate([1,-1]):
for l,fz in enumerate([1,-1]):
out[i,j,k,l] = np.transpose(a[::fx,::fy,::fz],ax)
return out
Мы могли бы упростить переворачивание вложенных циклов одним циклом -
def rotations48(a):
n = a.ndim
axcomb = list(itertools.permutations(range(n), n)) # all axes combinations
pcomb = list(itertools.product([1,-1], repeat=n)) # all permuted orders
out = np.zeros((6,8,) + a.shape,dtype=a.dtype) # Initialize output array
for i,ax in enumerate(axcomb): #loop through all axes for permuting
for j,(fx,fy,fz) in enumerate(pcomb): # all flipping combinations
out[i,j] = np.transpose(a[::fx,::fy,::fz],ax)
return out
Итак, это дает нам все 48 комбинаций.
Расширение до большего размера: если мы хотим расширить это до 4D массива, просто отредактируйте часть инициализации, чтобы расширить на 2 и нарезать вдоль еще одной оси.
Решить за 24 оборота
Теперь, как OP претендует иметь working solution, чтобы получить желаемые 24 комбинаций, необходимо отфильтровать out от предложенного нами решения. Я не смог найти общий шаблон для фильтрации, но получил индексы, необходимые для индексации -
idx = np.array([ 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, \
27, 29, 30, 32, 35, 37, 38, 41, 42, 44, 47])
Если вы заботитесь о том, чтобы выходные данные были такими же, как у rotations24, мы бы имели:
idx = np.array([ 0, 10, 3, 9, 5, 15, 6, 12, 41, 27, 42, 24, 44, \
30, 47, 29, 18, 35, 17, 32, 20, 37, 23, 38])
Следовательно, получите необходимые 24 с indexing -
final_out = out.reshape(48,-1)[idx]
Это работает для 3D массивов с любой общей длиной.
Пробный прогон для проверки
# From /questions/1233932/how-to-calculate-all-24-rotations-of-3d-array/3967194#3967194 @Colonel Panic
def rotations24_array(a):
out0 = np.zeros((6,2,2,2,) + a.shape,dtype=a.dtype)
p = [list(i) for i in rotations24(a)]
out0 = np.zeros((6,4,m,m,m),dtype=a.dtype)
for i in range(6):
for j in range(4):
out0[i,j] = p[i][j]
return out0
Проверить -
In [486]: # Setup
...: np.random.seed(0)
...: m = 3
...: a = np.random.randint(11,99,(m,m,m))
...:
...: # Verify results
...: idx = np.array([ 0, 10, 3, 9, 5, 15, 6, 12, 41, 27, 42, 24, 44, \
...: 30, 47, 29, 18, 35, 17, 32, 20, 37, 23, 38])
...: out1 = rotations24_array(a).reshape(-1,m**3)
...: out2 = rotations48(a).reshape(48,-1)[idx]
...: print np.allclose(out1, out2)
True
Ответ 6
Внизу этой страницы находятся 24 матрицы вращения: http://www.euclideanspace.com/maths/algebra/matrix/transforms/examples/index.htm.
Если кусок тетриса был представлен массивом координатных троек, чтобы применить вращение к части, ты бы просто умножил матрицу на каждую тройку в массиве. Вы сделали бы это 24 раза, чтобы получить 24 разных кусочка.
Например, если ваш массив ящиков (1,2,5), (1,2,4), (1,3,4)
И вращение, которое вы рассматриваете в данный момент, например,
1 0 0
M = 0 0 -1
0 1 0
Тогда повернутая фигура имеет представление
(1,2,5).M, (1,2,4).M, (1,3,4).M
где. представляет умножение матрицы. Сделайте это для каждого M в списке, и вы получите все 24 вращения. (Вы можете либо pre-, либо post- умножить на матрицы, это не имеет значения, если вы хотите, чтобы весь набор вращений не имел определенного порядка.)
Так что это очень просто.
Теперь, чтобы получить данные из вашей структуры данных и в структуру массива, которую я использовал выше, вам нужно сделать что-то вроде (извините, я не знаю Python)
for i = 0 to 2
for j = 0 to 2
for k = 0 to 2
if polycube(i,j,k)==1 then push(i-1,j-1,k-1) onto end of newArray
или что-то типа того. Наконец, чтобы перейти от представления newArray к поликубу, вы должны сделать что-то вроде
polycube = all zeros
foreach point (i,j,k) in newArray
polycube(i+1,j+1,k+1) = 1
Для 2x2x2 поликуба вы бы сделали
for i = 0 to 1
for j = 0 to 1
for k = 0 to 1
if polycube(i,j,k)==1 then push(i-0.5,j-0.5,k-0.5) onto end of newArray
и соответствующая обратная функция.
Ответ 7
Сначала давайте определим 48 изометрий как матрицы, которые переставляют базисные векторы, возможно, переворачивая некоторые знаки:
def isometries():
basis = numpy.eye(3)
for ix in range(3):
for iy in range(3):
if iy == ix:
continue
for iz in range(3):
if iz == ix or iz == iy:
continue
for sx in range(-1, 2, 2): # -1, 1
for sy in range(-1, 2, 2):
for sz in range(-1, 2, 2):
yield numpy.array([sx * basis[ix], sy * basis[iy], sz * basis[iz]])
Затем позвольте фильтровать вращения, которые являются изометриями определителя 1:
def rotations():
return filter(lambda x: numpy.linalg.det(x) > 0, isometries())
Наконец, мы можем применить такой поворот к поликубу, сместив индексы массива так, чтобы внутренняя точка была началом координат, и умножив вектор индекса на матрицу вращения:
def rotate(rotation, shape):
shift = numpy.array([1,1,1])
res = numpy.zeros(27).reshape(3,3,3)
it = numpy.nditer(shape, flags=['multi_index'])
while not it.finished:
v = numpy.array(it.multi_index) - shift
w = rotation.dot(v)
dest = tuple(w + shift)
res[dest] = it[0]
it.iternext()
return res
Например:
>>> rotate(list(rotations())[5], polycube)
array([[[ 0., 0., 0.],
[ 0., 0., 0.],
[ 0., 0., 0.]],
[[ 0., 1., 1.],
[ 0., 0., 0.],
[ 0., 0., 0.]],
[[ 1., 1., 0.],
[ 1., 1., 0.],
[ 0., 0., 0.]]])
Ответ 8
Я решил опубликовать другой ответ. Мой первый ответ был очень простым, но не полностью в духе вопроса. Я думаю, что теперь у меня есть лучший ответ, подумав немного.
TL; DR Следующий код вращает поликуб на протяжении всех 24 поворотов куба. Это происходит без умножения матриц, вместо этого используется таблица индексов 3x3x3x3x3, которая дает несколько ключевых поворотов индексов в поликубе, и код Грея длиной 23 для группы вращения куба. В нем всего шесть реальных строк кода, почти все из которых предназначены для циклов. Он очень быстрый и довольно компактный (за исключением таблицы индексов, которая может быть сгенерирована программой (см. Ниже)).
import numpy as np
# polycube that we want to rotate
A = np.array([[['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i']],
[['j', 'k', 'l'],
['m', '+', 'n'],
['o', 'p', 'q']],
[['r', 's', 't'],
['u', 'v', 'w'],
['x', 'y', 'z']]])
# I just do np.copy here because I don't know how to declare an array
T = np.copy(A)
Idx=np.array([
[[[[2,0,0], [2,1,0], [2,2,0]],
[[2,0,1], [2,1,1], [2,2,1]],
[[2,0,2], [2,1,2], [2,2,2]]],
[[[1,0,0], [1,1,0], [1,2,0]],
[[1,0,1], [1,1,1], [1,2,1]],
[[1,0,2], [1,1,2], [1,2,2]]],
[[[0,0,0], [0,1,0], [0,2,0]],
[[0,0,1], [0,1,1], [0,2,1]],
[[0,0,2], [0,1,2], [0,2,2]]]],
[[[[0,2,0], [1,2,0], [2,2,0]],
[[0,1,0], [1,1,0], [2,1,0]],
[[0,0,0], [1,0,0], [2,0,0]]],
[[[0,2,1], [1,2,1], [2,2,1]],
[[0,1,1], [1,1,1], [2,1,1]],
[[0,0,1], [1,0,1], [2,0,1]]],
[[[0,2,2], [1,2,2], [2,2,2]],
[[0,1,2], [1,1,2], [2,1,2]],
[[0,0,2], [1,0,2], [2,0,2]]]],
[[[[2,2,2], [2,1,2], [2,0,2]],
[[2,2,1], [2,1,1], [2,0,1]],
[[2,2,0], [2,1,0], [2,0,0]]],
[[[1,2,2], [1,1,2], [1,0,2]],
[[1,2,1], [1,1,1], [1,0,1]],
[[1,2,0], [1,1,0], [1,0,0]]],
[[[0,2,2], [0,1,2], [0,0,2]],
[[0,2,1], [0,1,1], [0,0,1]],
[[0,2,0], [0,1,0], [0,0,0]]]]
])
# Gray code gives Hamiltonican circuit through cube rotation group
gray = [3,2,1,2,1,2,3,2,3,2,1,2,1,2,3,2,3,2,1,2,1,2,3]
# Oops, index starting at 0
gray[:] = [x-1 for x in gray]
print(A)
# I'm sure there must be a more efficient way to move T (temp) into A
for g in gray:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx[g,i,j,k,0],Idx[g,i,j,k,1],Idx[g,i,j,k,2]]
A = np.copy(T)
print("-----------------")
print(A)
Мое решение состоит в том, чтобы найти код Грея для группы вращения куба.
Во-первых, мы должны найти хорошее представление для группы вращения, которую вы используете. Рассмотрим куб 2x2x2 с кубами 1x1x1, помеченными следующим образом:
1 2
3 4 4 3
2 1
Мы начинаем с 1, чтобы соответствовать литературе по математике. Верхний левый квадрат должен быть передней панелью, а нижний правый квадрат - задней. Представьте 1, соединенный ребрами с 2 и 3 на передней поверхности, с 4 на задней поверхности и т.д.
Обратите внимание, что по диагонали противоположные кубы имеют одинаковое число. Теперь любое вращение куба соответствует перестановке четырех чисел на лицевой стороне. Кроме того, любая перестановка чисел на лицевой стороне соответствует повороту. Четыре поворота по оси Z, выходящие из страницы,
1 2 3 1 4 3 2 4
3 4 4 3 4 2 2 4 2 1 1 2 1 3 3 1
2 1 1 3 3 4 4 2
Мы можем пометить повороты по эффекту на лицевой стороне. Это 1234, 3142, 4321 и 2413.
Три дополнительных поворота вокруг оси x (плюс единичное вращение, с которого мы начинаем)
1 2 3 4 2 1 4 3
3 4 4 3 2 1 1 2 4 3 3 4 1 2 2 1
2 1 4 3 1 2 3 4
В наших более компактных обозначениях дополнительные вращения - 3421, 2143 и 4312.
Три дополнительных поворота вокруг оси Y
1 2 2 3 3 4 4 1
3 4 4 3 4 1 1 4 1 2 2 1 2 3 3 2
2 1 3 2 4 3 1 4
В компактной записи три дополнительных поворота - 2341, 3412 и 4123.
Есть три поворота, включая идентичность, которые фиксируют 1 диагональ:
1 2 1 4 1 3
3 4 4 3 2 3 3 2 4 2 2 4
2 1 4 1 3 1
с новыми маркированными 1423 и 1342.
Есть три поворота, включая идентичность, которые фиксируют 2 диагонали:
1 2 4 2 3 2
3 4 4 3 1 3 3 1 4 1 1 4
2 1 2 4 2 3
с новыми маркированными 4213 и 3241.
Есть три поворота, включая идентичность, которые фиксируют 3 диагонали:
1 2 2 4 4 1
3 4 4 3 3 1 1 3 3 2 2 3
2 1 4 2 1 4
с новыми маркированными 2431 и 4132.
Есть три поворота, включая идентичность, которые фиксируют 4 диагонали:
1 2 2 3 3 1
3 4 4 3 1 4 4 1 2 4 4 2
2 1 3 2 1 3
с новыми, помеченными 2314 и 3124.
Наконец, есть шесть крайних сальто плюс индивидуальность. Сальто в 1-2 края
1 2 2 1
3 4 4 3 3 4 4 3
2 1 1 2
с новым, представленным 2134. Аналогичным образом, имеются ребра по краям 1-3 (3214), 1-4 (4231), 2-3 (1324), 2-4 (1432) и 3-4 (1243),
Каждое из 24 вращений соответствует отдельной перестановке из 1234, и, поскольку имеется 24 перестановки и 24 вращения, каждая отдельная перестановка соответствует вращению. Мы говорим, что группа вращения куба и группа перестановок S_4 из 1234 изоморфны. (Один способ думать об этом состоит в том, что вращения куба действуют как перестановка диагоналей куба, и соответствие составляет 1-1.)
Мы могли бы выяснить влияние каждого из 24 вращений на ваши массивы, но это утомительно и подвержено ошибкам. Вместо этого мы увидим, что группа вращений генерируется всего тремя вращениями, ребро переворачивается
R1=transpose numbers in position2 1 and 2, and leave numbers in positions 3 and 4 alone
R2=transpose numbers in positions 2 and 3, and leave numbers in positions 1 and 4 alone
R3=transpose numbers in positions 3 and 4, and leave numbers in positions 1 and 2 alone
и их композиции. Мы добавим
R0=identity operation
для полноты. Используя только эти три генератора, мы можем найти гамильтонову цепь через граф Кэли группы вращения:
01 1234 apply R0 to starting position, i.e., do nothing
02 1243 apply R3 to previous
03 1423 apply R2 to previous
04 4123 R1
05 4213 R2
06 2413 R1
07 2143 R2
08 2134 R3
09 2314 R2
10 2341 R3
11 2431 R2
12 4231 R1
13 4321 R2
14 3421 R1
15 3241 R2
16 3214 R3
17 3124 R2
18 3142 R3
19 3412 R2
20 4312 R1
21 4132 R2
22 1432 R1
23 1342 R2
24 1324 R3
Обратите внимание, что каждая перестановка (т.е. Вращение куба) появляется в этом списке ровно один раз, и что переход от одного элемента в списке к следующему выполняется путем транспонирования элементов в положениях 1-2, 2-3 или 3. -4, что соответствует поворотам поворота кромки R1, R2 и R3. Этот код Грея для S_4 (и многое другое, что, к сожалению, довольно сложно понять, если вы не знаете о группах отражений и диаграммах Кокстера), представлен в знаменитой статье " Коды Грея для групп отражений" Конвея, Слоана и Уилкса.
Код Грея суммируется этой последовательностью из 23 чисел:
gray = {3,2,1,2,1,2,3,2,3,2,1,2,1,2,3,2,3,2,1,2,1,2,3}
Таким образом, мы значительно сократили объем работы, которую мы должны выполнить, начиная с расчета эффекта 24 различных вращений на поликубе 2x2x2 (а затем и на поликубе 3x3x3), до измерения эффекта только 3 различных вращений на наших кубах. Эти три функции вращения могут быть сохранены в массиве с индексом 0..3, а затем применены как
nextConfiguration = currentConfiguration.Rotation[gray[i]]
(Обратите внимание, что мы можем даже получить все 48 отражений/поворотов, если захотим, следуя этой последовательности вращений одним отражением P (подойдет любое отражение, поэтому выберите простейшее для реализации), а затем следуя этому отражению серой последовательностью в обратном порядке, который дает код Грея для полной группы из 48 отражений/вращений (построение больших последовательностей путем прикрепления обратной последовательности к себе является одной из "больших идей" при построении кодов Грея.))
Мы прошли долгий путь, даже не рассматривая представление форм, которые вы хотите повернуть, но теперь мы должны реализовать R1, R2 и R3, поэтому нам нужно рассмотреть структуру данных, которая представляет формы, трехмерный массив. Рассмотрим влияние R1, поворота ребра на 180 градусов на ось через середины 1-2 ребер, на наш массив 2x2x2:
(0,0,0) (1,0,0) (1,0,0) (0,0,0)
(0,1,0) (1,1,0) (0,0,1) (1,0,1) --> (1,0,1) (0,0,1) (1,1,0) (0,1,0)
(0,1,1) (1,1,1) (1,1,1) (0,1,1)
Это говорит нам о том, что наша операция R1 может быть реализована
output(0,0,0) = input(1,0,0)
output(1,0,0) = input(0,0,0)
output(0,1,0) = input(1,0,1)
output(1,1,0) = input(0,0,1)
output(0,0,1) = input(1,1,0)
output(1,0,1) = input(0,1,0)
output(0,1,1) = input(1,1,1)
output(1,1,1) = input(0,1,1)
Это определяет операцию R1 в случае 2x2x2. Должно быть понятно, как определить R2 и R3 в случае 2x2x2, а также как определить эти операции в случае 3x3x3.
Позвольте мне в заключение сказать, что определение операторов Ri утомительно и подвержено ошибкам, поэтому мы не хотим делать это слишком много, если сможем помочь. Мы можем избежать определения только двух операторов, R1 (уже определено выше) и F, вращения передней грани:
(0,0,0) (1,0,0) (0,1,0) (0,0,0)
(0,1,0) (1,1,0) (0,0,1) (1,0,1) --> (1,1,0) (1,0,0) (0,1,1) (0,0,1)
(0,1,1) (1,1,1) (1,1,1) (1,0,1)
Тогда мы можем представить R2 = FFFR1.F (где. Означает "с последующим"), а R3 = FFR1.FF (это "сопряженные" из R1.)
Для случая 3x3x3 это некоторая работа, чтобы найти таблицы индексов вручную, поэтому я написал процедуру для этого, а затем я нашел все 24 вращения алфавитного куба. Смотрите код ниже. Я уверен, что эксперт Python может сделать его гораздо короче. Это моя первая программа на Python.
Идея состоит в том, чтобы вращать не содержимое массива 3х3х3, а его индексы.
import numpy as np
# polycube that we want to rotate
A = np.array([[['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'i']],
[['j', 'k', 'l'],
['m', '+', 'n'],
['o', 'p', 'q']],
[['r', 's', 't'],
['u', 'v', 'w'],
['x', 'y', 'z']]])
# I just do np.copy here because I don't know how to declare an array
T = np.copy(A)
# matrix representing top front edge rotation (12)
R1 = np.array([[-1, 0, 0],
[ 0, 0, 1],
[ 0, 1, 0]])
# matrix representing right front edge rotation (23)
R2 = np.array([[ 0, 0, 1],
[ 0,-1, 0],
[ 1, 0, 0]])
# matrix representing bottom front edge rotation (34)
R3 = np.array([[-1, 0, 0],
[ 0, 0,-1],
[ 0,-1, 0]])
# Gray code gives Hamiltonican circuit through cube rotation group
gray = [3,2,1,2,1,2,3,2,3,2,1,2,1,2,3,2,3,2,1,2,1,2,3]
# trick for speed: we only need to apply each rotation matrix once
# to this polycube of indices, then we use the result as a table of
# pointers to new positions of polycube after rotation
Idx0 = np.array([[[[0,0,0], [1,0,0], [2,0,0]],
[[0,1,0], [1,1,0], [2,1,0]],
[[0,2,0], [1,2,0], [2,2,0]]],
[[[0,0,1], [1,0,1], [2,0,1]],
[[0,1,1], [1,1,1], [2,1,1]],
[[0,2,1], [1,2,1], [2,2,1]]],
[[[0,0,2], [1,0,2], [2,0,2]],
[[0,1,2], [1,1,2], [2,1,2]],
[[0,2,2], [1,2,2], [2,2,2]]]])
# Again, copy array because I don't know how to declare
Idx1 = np.copy(Idx0)
Idx2 = np.copy(Idx0)
Idx3 = np.copy(Idx0)
# We have to subtract [1,1,1] then add it again to move the center of the
# indexes to [0,0,0]
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
Idx1[i,j,k] = np.matmul(np.array([i,j,k])-np.array([1,1,1]),R1) + \
np.array([1,1,1])
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
Idx2[i,j,k] = np.matmul(np.array([i,j,k])-np.array([1,1,1]),R2) + \
np.array([1,1,1])
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
Idx3[i,j,k] = np.matmul(np.array([i,j,k])-np.array([1,1,1]),R3) + \
np.array([1,1,1])
# note that we have done only 81 vector*matrix multiplications. Now we don't
# have to do any more; we just look up the result in the index tables Idx[123]
print(A)
# I'm sure there must be a more efficient way to move T (temp) into A
for g in gray:
if g == 1:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx1[i,j,k,0],Idx1[i,j,k,1],Idx1[i,j,k,2]]
A = np.copy(T)
elif g == 2:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx2[i,j,k,0],Idx2[i,j,k,1],Idx2[i,j,k,2]]
A = np.copy(T)
elif g == 3:
for i in [0,1,2]:
for j in [0,1,2]:
for k in [0,1,2]:
T[i,j,k] = A[Idx3[i,j,k,0],Idx3[i,j,k,1],Idx3[i,j,k,2]]
A = np.copy(T)
print("-----------------")
print(A)
Вот вывод из программы
[[['a' 'b' 'c']
['d' 'e' 'f']
['g' 'h' 'i']]
[['j' 'k' 'l']
['m' '+' 'n']
['o' 'p' 'q']]
[['r' 's' 't']
['u' 'v' 'w']
['x' 'y' 'z']]]
-----------------
[[['z' 'w' 't']
['y' 'v' 's']
['x' 'u' 'r']]
[['q' 'n' 'l']
['p' '+' 'k']
['o' 'm' 'j']]
[['i' 'f' 'c']
['h' 'e' 'b']
['g' 'd' 'a']]]
-----------------
[[['x' 'o' 'g']
['y' 'p' 'h']
['z' 'q' 'i']]
[['u' 'm' 'd']
['v' '+' 'e']
['w' 'n' 'f']]
[['r' 'j' 'a']
['s' 'k' 'b']
['t' 'l' 'c']]]
-----------------
[[['r' 's' 't']
['j' 'k' 'l']
['a' 'b' 'c']]
[['u' 'v' 'w']
['m' '+' 'n']
['d' 'e' 'f']]
[['x' 'y' 'z']
['o' 'p' 'q']
['g' 'h' 'i']]]
-----------------
[[['a' 'd' 'g']
['j' 'm' 'o']
['r' 'u' 'x']]
[['b' 'e' 'h']
['k' '+' 'p']
['s' 'v' 'y']]
[['c' 'f' 'i']
['l' 'n' 'q']
['t' 'w' 'z']]]
-----------------
[[['c' 'l' 't']
['f' 'n' 'w']
['i' 'q' 'z']]
[['b' 'k' 's']
['e' '+' 'v']
['h' 'p' 'y']]
[['a' 'j' 'r']
['d' 'm' 'u']
['g' 'o' 'x']]]
-----------------
[[['i' 'h' 'g']
['f' 'e' 'd']
['c' 'b' 'a']]
[['q' 'p' 'o']
['n' '+' 'm']
['l' 'k' 'j']]
[['z' 'y' 'x']
['w' 'v' 'u']
['t' 's' 'r']]]
-----------------
[[['r' 'u' 'x']
['s' 'v' 'y']
['t' 'w' 'z']]
[['j' 'm' 'o']
['k' '+' 'p']
['l' 'n' 'q']]
[['a' 'd' 'g']
['b' 'e' 'h']
['c' 'f' 'i']]]
-----------------
[[['t' 'l' 'c']
['s' 'k' 'b']
['r' 'j' 'a']]
[['w' 'n' 'f']
['v' '+' 'e']
['u' 'm' 'd']]
[['z' 'q' 'i']
['y' 'p' 'h']
['x' 'o' 'g']]]
-----------------
[[['g' 'h' 'i']
['o' 'p' 'q']
['x' 'y' 'z']]
[['d' 'e' 'f']
['m' '+' 'n']
['u' 'v' 'w']]
[['a' 'b' 'c']
['j' 'k' 'l']
['r' 's' 't']]]
-----------------
[[['x' 'u' 'r']
['o' 'm' 'j']
['g' 'd' 'a']]
[['y' 'v' 's']
['p' '+' 'k']
['h' 'e' 'b']]
[['z' 'w' 't']
['q' 'n' 'l']
['i' 'f' 'c']]]
-----------------
[[['z' 'q' 'i']
['w' 'n' 'f']
['t' 'l' 'c']]
[['y' 'p' 'h']
['v' '+' 'e']
['s' 'k' 'b']]
[['x' 'o' 'g']
['u' 'm' 'd']
['r' 'j' 'a']]]
-----------------
[[['t' 's' 'r']
['w' 'v' 'u']
['z' 'y' 'x']]
[['l' 'k' 'j']
['n' '+' 'm']
['q' 'p' 'o']]
[['c' 'b' 'a']
['f' 'e' 'd']
['i' 'h' 'g']]]
-----------------
[[['c' 'f' 'i']
['b' 'e' 'h']
['a' 'd' 'g']]
[['l' 'n' 'q']
['k' '+' 'p']
['j' 'm' 'o']]
[['t' 'w' 'z']
['s' 'v' 'y']
['r' 'u' 'x']]]
-----------------
[[['a' 'j' 'r']
['b' 'k' 's']
['c' 'l' 't']]
[['d' 'm' 'u']
['e' '+' 'v']
['f' 'n' 'w']]
[['g' 'o' 'x']
['h' 'p' 'y']
['i' 'q' 'z']]]
-----------------
[[['z' 'y' 'x']
['q' 'p' 'o']
['i' 'h' 'g']]
[['w' 'v' 'u']
['n' '+' 'm']
['f' 'e' 'd']]
[['t' 's' 'r']
['l' 'k' 'j']
['c' 'b' 'a']]]
-----------------
[[['i' 'f' 'c']
['q' 'n' 'l']
['z' 'w' 't']]
[['h' 'e' 'b']
['p' '+' 'k']
['y' 'v' 's']]
[['g' 'd' 'a']
['o' 'm' 'j']
['x' 'u' 'r']]]
-----------------
[[['r' 'j' 'a']
['u' 'm' 'd']
['x' 'o' 'g']]
[['s' 'k' 'b']
['v' '+' 'e']
['y' 'p' 'h']]
[['t' 'l' 'c']
['w' 'n' 'f']
['z' 'q' 'i']]]
-----------------
[[['x' 'y' 'z']
['u' 'v' 'w']
['r' 's' 't']]
[['o' 'p' 'q']
['m' '+' 'n']
['j' 'k' 'l']]
[['g' 'h' 'i']
['d' 'e' 'f']
['a' 'b' 'c']]]
-----------------
[[['g' 'd' 'a']
['h' 'e' 'b']
['i' 'f' 'c']]
[['o' 'm' 'j']
['p' '+' 'k']
['q' 'n' 'l']]
[['x' 'u' 'r']
['y' 'v' 's']
['z' 'w' 't']]]
-----------------
[[['i' 'q' 'z']
['h' 'p' 'y']
['g' 'o' 'x']]
[['f' 'n' 'w']
['e' '+' 'v']
['d' 'm' 'u']]
[['c' 'l' 't']
['b' 'k' 's']
['a' 'j' 'r']]]
-----------------
[[['c' 'b' 'a']
['l' 'k' 'j']
['t' 's' 'r']]
[['f' 'e' 'd']
['n' '+' 'm']
['w' 'v' 'u']]
[['i' 'h' 'g']
['q' 'p' 'o']
['z' 'y' 'x']]]
-----------------
[[['t' 'w' 'z']
['l' 'n' 'q']
['c' 'f' 'i']]
[['s' 'v' 'y']
['k' '+' 'p']
['b' 'e' 'h']]
[['r' 'u' 'x']
['j' 'm' 'o']
['a' 'd' 'g']]]
-----------------
[[['g' 'o' 'x']
['d' 'm' 'u']
['a' 'j' 'r']]
[['h' 'p' 'y']
['e' '+' 'v']
['b' 'k' 's']]
[['i' 'q' 'z']
['f' 'n' 'w']
['c' 'l' 't']]]
Ответ 9
Я столкнулся с аналогичной проблемой при попытке случайного поворота трехмерного массива с горячим кодированием непосредственно перед передачей в мою нейронную сеть. Я продемонстрирую здесь для трехмерного массива, но это также работает с 4-м измерением (при использовании OHE).
>>> m = np.reshape(np.arange(8),(2,2,2))
>>> m
array([[[0, 1],
[2, 3]],
[[4, 5],
[6, 7]]])
Затем мы вращаем массив 3 раза, каждый раз в другом направлении. Повторите 24 000 раз, чтобы увидеть распределение (ожидая 1000 отсчетов для каждого уникального поворота):
>>> rot_list = []
>>> for _ in range(24000):
a = np.rot90(m,np.random.randint(0,4),axes=(0,np.random.randint(1,3)))
b = np.rot90(a,np.random.randint(0,4),axes=(np.random.randint(1,3),0))
c = np.rot90(b,np.random.randint(0,4),axes=(1,2)) # or axes=(2,1)
rot_list.append(c)
>>> unique_rotation_matrices, counts = np.unique(np.asarray(rot_list),axis=0, return_counts=True)
>>> len(unique_rotation_matrices)
24
Итак, мы видим, что мы получаем все 24 возможных поворота. Давайте посмотрим на их распределение:
>>> counts
[1062 946 917 982 1096 978 1153 936 939 907 1183 932 958 932 1122
926 1115 954 933 932 1135 924 1138 900]
Распределение выглядит довольно равномерно, но повторение этого несколько раз показывает, что оно слегка смещено.
