如何在常数长度内找到两个字符串的所有可能排列组合

Question

我想找到两个字符串列表的所有可能排列，且长度不超过 （5）。假设list_1 = ["A"] ，list_2 = ["BB"]。

所有可能的组合如下：

A A A A A
A A A BB
A A BB A
A BB A A
BB A A A
A BB BB
BB A BB
BB BB A

我试图使用以下代码进行实现，但我不确定如何为其定义长度5。

import itertools 
from itertools import permutations 

list_1 = ["A"] 
list_2 = ["BB"] 
unique_combinations = [] 

permut = itertools.permutations(list_1, 5) 

for comb in permut: 
    zipped = zip(comb, list_2) 
    unique_combinations.append(list(zipped)) 

print(unique_combinations) 

- user14385051

Answer 1

你可以按照以下步骤操作：

import itertools

unique_combinations = []

permut = itertools.product(["A","B"], repeat=5)
for comb in permut:
    l = "".join(comb)
    c_bb = l.count("BB")
    c_a = l.count("A")
    if 2*c_bb + c_a == 5:
        unique_combinations.append(l)
print(unique_combinations)

这将会得到：

['AAAAA', 'AAABB', 'AABBA', 'ABBAA', 'ABBBB', 'BBAAA', 'BBABB', 'BBBBA']

首先找到所有由5个元素组成的类似字符串，其中每个元素要么是“A”，要么是“B”。然后使用string.count来计算您感兴趣的每个子字符串出现的次数，如果它等于5，则保存它。

- David

---

这种情况只适用于一组非常严格的输入。如果输入是 ['A', 'BC']，那么它将失败。我会寻找更通用的解决方案。 - flakes

@flakes 我同意，但是你只需要调整传递给 product 的值并调整条件，我认为这是一个容易通用的更改。你不同意吗？ - David

我认为对于一般情况需要进行很多更改。考虑choices=['A', 'BC', 'C']这种情况，或者任何输入方法事先不知道的情况。假设你提供了def perm_with_size(choices, limit):，思考如何支持这些未知因素。 - flakes

Answer 2

您可以使用 itertools.product 来找出所有可能的组合，其中包含'A'和'BB' （重复次数为3到5，因为这些是可接受答案中的元素数量），然后根据它们的总长度为5个字符过滤掉它们：

import itertools

all_options = []
for i in range(3,6):
    all_options += list(itertools.product(['A', 'BB'], repeat=i))
all_options = [i for i in all_options if len(''.join(i)) == 5]
print(all_options)

输出：

[('A', 'BB', 'BB'), ('BB', 'A', 'BB'), ('BB', 'BB', 'A'), ('A', 'A', 'A', 'BB'), ('A', 'A', 'BB', 'A'), ('A', 'BB', 'A', 'A'), ('BB', 'A', 'A', 'A'), ('A', 'A', 'A', 'A', 'A')]

- Tom

---

我建议在all_options中使用set而不是list。 - flakes

Answer 3

使用递归：

list_1 = ["A"]
list_2 = ["BB"]
size = 5

strs = list_1 + list_2
res = []

def helper(strs, size, cur, res):
    if size == 0:
        res.append(cur)
        return
    if size < 0:
        return

    for s in strs:
        helper(strs, size-len(s), cur+[s], res)

helper(strs, size, [], res)
print(res)

不使用递归：

list_1 = ["A"]
list_2 = ["BB"]
size = 5

strs = list_1 + list_2
res = []

q = [[]]
while q:
    t = q.pop()
    for s in strs:
        cur = t + [s]
        cursize = len(''.join(cur))
        if cursize == size:
            res.append(cur)
        elif cursize < size:
            q.append(cur)
print(res)

- Frank

---

通常我会避免在排列等问题中使用递归。在更复杂的输入上，你很可能会遇到递归限制。我建议尝试使用 while 循环来重构代码。 - flakes

Answer 4

你需要一个像这样的递归函数：

def f(words, N, current = ""):
    if(len(current)<N):
        for i in words:
            f(words, N, current+i)
    elif(len(current)==N):
        print(current)
        

f(["A", "BB"], 5)

编辑：不幸的是，如果您的列表中有两个或更多单词共享相同的字母，此函数将返回重复项。因此，正确的方法应该是填充一个包含所有返回值的列表，然后消除重复项。

- user14478314