Генерация всех уникальных порядков циклического ряда символов (все круговые перестановки) - PullRequest
Новая
       41

Генерация всех уникальных порядков циклического ряда символов (все круговые перестановки)

0 голосов
/ 06 марта 2019
  • У меня есть строка, состоящая из Xs и Ys .

Ради вопроса, скажем, эта строка состоит из четырех X и двух Y: 

XXYYYY

Как я могу сгенерировать все возможные уникальные строки, которые состоят из Four-X и Two-Y, при условии, что строка не считается уникальной, если по циклу (/ вращение / смещение) его символы вокруг него производит строку, которая уже была найдена?

Например: 

XXYYYY is considered similar to YXXYYY and YYYXXY (cardinal numbers added clarify)
123456                          612345     456123

Обратите внимание: , что порядок символов остается неизменным, единственное, что изменилось, это начальный символ (исходная строка начинается с 1, вторая строка с 6, а третья с 4, но все они следят за порядком).

В случае Two-X и Four-Y (наш пример) все возможные уникальные перестановки: 

XXYYYY
XYXYYY
XYYXYY

И любой другой заказ будет сдвинутой версией одного из этих 3.

Как бы вы сгенерировали все возможные перестановки строки с и числом N X и числом Y Y?

1 Ответ

2 голосов
/ 06 марта 2019

По сути, вам нужно генерировать комбинаторные объекты с именами бинарных ожерелий с фиксированным числом единиц

Это код Python, адаптированный из Статья Савады «Быстрый алгоритм создания ожерелий с фиксированным содержимым».
(Я использовал самый простой вариант, есть и более оптимизированные) 

n = 6
d = 3
aa = [0] * n
bb = [n - d, d]  #n-d zeros, d ones

def SimpleFix(t, p):
    if t > n:
        if n % p == 0:
            print(aa)
    else:
        for j in range(aa[t - p - 1], 2):
            if bb[j] > 0:
                aa[t - 1] = j
                bb[j] -= 1
                if j == aa[t-p-1]:
                    SimpleFix(t+1, p)
                else:
                    SimpleFix(t+1, t)
                bb[j] += 1

SimpleFix(1, 1)

#example for 3+3

[0, 0, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 1]
[0, 0, 1, 1, 0, 1]
[0, 1, 0, 1, 0, 1]
...