python - 生成具有 n 个连续重复元素的排列

Question

我需要生成 p 个不同字符的所有可能排列，长度为 r，字符串中有重复字符。我有一个额外的约束 - 在每个排列中的任何点我只能有 n 个连续的重复字符。

约束:(1 ≤ p, r, n ≤ 12)

例如:对于字母“AB”，r 值为 4，n 值为 2，我想要以下输出:

AABA
AABB
ABAA
ABAB
ABBA
BAAB
BABA
BABB
BBAA
BBAB

相邻相同字符的最大数量 n 为 2。

我通过找到字符串的笛卡尔积，然后遍历结果并消除任何不符合 n 值的结果，获得了所需的输出。虽然我的方法非常慢!如果需要，这是我的代码:

s = "AB"
q = 2
r = 4

pools = [s] * r
result = [[]]
final = []
for pool in pools:
    result = [x+[y] for x in result for y in pool]

check = [''.join([l]*(q+1))for l in s]

for r in result:
    add = True
    z = ''.join(r)
    for c in check:
        if c in z:
            add = False
            break
    if add:
        final.append(z)

print(final)
# ['AABA', 'AABB', 'ABAA', 'ABAB', 'ABBA', 'BAAB', 'BABA', 'BABB', 'BBAA', 'BBAB']

我的解决方案适用于上面的输入，但对于更大的数字/字符串，它需要几分钟。例如，使用我的解决方案，以下输入将花费很长时间:

s = "ABCDEF"
q = 3
r = 10

我想要一个最好能在一秒钟内完成的解决方案。我写了一个更快的递归解决方案，但是由于较大数字的内存错误导致我的机器崩溃 - 所以请不要递归解决方案:)谢谢!

Answer 1

将其视为树遍历问题。节点是排列的初始段，每个排列都可以以 p 方式或 p-1 方式扩展(取决于最后一个 n 字符已相同)。

一些未优化的代码:

from string import ascii_uppercase

def children(s,p,r,n):
    chars = ascii_uppercase[:p]
    if len(s)==r:
        return []
    elif len(s) >= n and s[-n:] == s[-1]*n:
        return [s+c for c in chars if c != s[-1]]
    else:
        return [s+c for c in chars]

def extensions(s,p,r,n):
    kids = children(s,p,r,n)
    if kids == []:
        return [s]
    else:
        perms = []
        for kid in kids:
            perms.extend(extensions(kid,p,r,n))
        return perms

def perms(p,r,n):
    return extensions('',p,r,n)

例如，

>>> perms(2,4,2)
['AABA', 'AABB', 'ABAA', 'ABAB', 'ABBA', 'BAAB', 'BABA', 'BABB', 'BBAA', 'BBAB']

perms(6,10,3) 需要大约一分钟的时间来生成长度为 10 的 ABCDEF 的 58792500 排列，没有重复 block 长于 3。它是递归的，但递归的深度受 `r 的限制，因此递归不应崩溃(除非列表本身太大而无法保存在内存中)。您可以研究非递归列表遍历算法并将其编写为生成器而不是返回列表的东西。

On Edit 以下仍然是递归的，但它使用生成器因此内存效率更高:

def yield_leaves(s,chars,r,n):
    if len(s) == r:
        yield s
    else:
        avoid = s[-1] if len(s) >= n and s[-n:] == s[-1]*n else ''
        for c in chars:
            if c != avoid:
                yield from yield_leaves(s+c,chars,r,n)

def yield_perms(chars,r,n):
    yield from yield_leaves('',chars,r,n)

我更改了界面以使其更接近您的代码。例如，

p = list(yield_perms('ABCDEF',10,3))

相当于p = perms(6,10,3)。它实际上似乎稍微快一些。