时间戳

首页 > 解决方案 > 生成循环字符系列的所有唯一顺序（所有循环排列）

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

问题描述

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

XXYYYY

如果通过循环（/旋转/移动）它周围的字符产生一个已经找到的字符串，那么我如何生成由四个 X 和两个 Y 组成的所有可能的唯一字符串?

例如：

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

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

在两个 X 和四个 Y（我们的示例）的情况下，所有可能的唯一排列是：

XXYYYY
XYXYYY
XYYXYY

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

您将如何生成具有 N 个 X 和 M 个 Y 的字符串的所有可能排列？

标签： permutationcombinatoricscircular-permutations

解决方案

本质上，您需要生成具有固定数量的二进制项链的组合对象

这是改编自Sawada 文章“生成具有固定内容的项链的快速算法”的 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]

推荐阅读