Создать полную комбинацию без циклических вращений ⇐ Python

[Anonymous]

У меня возникла проблема, я занимаюсь научными исследованиями и возникла необходимость сгенерировать двоичную последовательность определенной длины.
Для генерации комбинаций я использую библиотеку numpy. В Интернете я нашел следующий код:

Код: Выделить всё

np.array(np.meshgrid(*[[1, 0] for x in range(size)])).T.reshape(-1, size)

Он работает, и работает быстро, но создает все комбинации определенной длины.
if size = 3

[1 1 1]
[1 0 1]
[0 1 1]
[0 0 1]
[1 1 0]
[1 0 0]
[0 1 0]
[0 0 0]


Мне нужно сгенерировать комбинации таким образом, чтобы удалить все цикличные копии, т.е.:

[1 1 1]
[1 0 1]
[0 1 1] потому что [1 0 1] и [1 1 0] — циклические перемещения
[0 0 1]
[1 1 0]
[1 0 0]
[0 1 0]
[0 0 0]


Необходимо написать функцию, которая будет генерировать все разрешенные комбинации любой длины. от 3 до 1000 элементов. Другой вопрос, как его сохранить))
Я создал какой-то действительно ужасный код, за который мне стыдно, но он вроде работает.

Код: Выделить всё

def gen_matrix(size):
return np.array(np.meshgrid(*[[1, 0] for x in range(0, size)])).T.reshape(-1, size)

def build_matrix(size_row):
a = gen_matrix(size_row)
kill = True
while kill:
kill = False
for i in a:
if kill:
break
for j in range(1, size_row):
b = np.roll(i, j)
if np.array_equal(i, b):
continue
k = np.where((a == b).all(axis=1))
if np.size(k) > 0:
a = np.delete(a, k[0], 0)
kill = True
return a

result:
[1 1 1 1 1]
[1 0 1 1 1]
[0 0 1 1 1]
[0 1 0 1 1]
[0 0 0 1 1]
[0 0 1 0 1]
[0 0 0 0 1]
[0 0 0 0 0]

Описать в 2 строчки будет сложно. Существуют такие комбинаторные последовательности, как совершенные золотые кольца (ПГР), они чем-то похожи на линии Голомба, но имеют циклическую структуру. Существует общее правило, по которому можно проверить истинность последовательности, суммы соседних чисел исчерпывают все множество от 1 до Sn, где Sn определяется по формуле или представляет собой просто сумму всех чисел. Например, PGR (1,2,4) => 1, 2, 1+2=3, 4,4+1=5, 2+4=6,1+2+4=7. Вы можете добавить цифры в круг. Существует несколько PGR, в которых количество вариантов суммы может быть больше 1, т.е. PGR (1,1,2,3), поскольку «1» = 2, то можно формировать смежные суммы от 1 до 7 двумя способами. . . Генерируется различными способами, одним из которых является генерация циклических кодов, например, PGR (1,2,4) можно записать как 1101000. Цифры последовательности представляют собой количество «0» между «1». У меня есть задача, мне удалось найти последовательности до Sn=35. Теперь мне нужно найти другие комбинации. Раньше я делал полное перечисление, то есть количество комбинаций 2^N, где N — количество бит, но чем выше порядок, тем сложнее. Итак, теперь я поставил перед собой цель. 1. Оптимизация входного массива потенциальных кодов. 2. вычислить на GPU.
на самом деле мне нужно сгенерировать все комбинации двоичной последовательности, но удалить все циклические копии.
2^12 = всего 4096 вариантов
если из них удалить циклические копии, количество вариантов будет 352.

Подробнее здесь: https://stackoverflow.com/questions/730 ... -rotations