Как рассчитать все 24 вращения 3D-массива?

Ответ 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]

Распределение выглядит довольно равномерно, но повторение этого несколько раз показывает, что оно слегка смещено.