生成循环字符系列的所有唯一顺序（所有循环排列）

Question

我有一个由 Xs 和 Ys 组成的字符串。

为了问题的缘故，假设这个字符串是由四个 X 和两个 Y 构成的：

XXYYYY

如何生成所有可能的唯一字符串，这些字符串由四个 X 和两个 Y 组成，因为字符串是 not 如果通过循环 (/rotating/shifting) 它周围的字符产生一个已经找到的字符串，那么它是否被认为是唯一的？

例如：

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

注意：字符顺序不变，唯一改变的是起始字符（原始字符串以1开头，第二个字符串以6开头，并且第三个和 4 个，但他们都保持顺序）。

在 Two-Xs 和 Four-Ys（我们的示例）的情况下，所有可能的唯一排列是：

XXYYYY
XYXYYY
XYYXYY

其他所有订单都是这 3 个订单中的一个的转换版本。

你如何生成一个字符串的所有可能排列，其中有 N 个 X 和 M 个 Y？

Answer 1

本质上，您需要生成名为二进制项链的组合对象，其中的个数固定

这是 Python 改编自 Sawada article "A fast algorithm to generate necklaces with fixed contents" 的代码。
（我用的是最简单的变体，还有更优化的）

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]

生成循环字符系列的所有唯一顺序（所有循环排列）

Generating all unique orders of looping series of characters (all circular permutations)

permutation

combinatorics

circular-permutations