如何在恒定长度内找到两个字符串的所有可能排列

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)

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的string-like由5个元素组成，要么是“A”，要么是“B”。然后用string.count统计你感兴趣的每个子串出现的次数，如果等于5就保存。

Answer 2

您可以使用 itertools.product 找到 'A' 和 'BB' 的所有可能组合（repeat 从 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')]

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)

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)

编辑：不幸的是，如果列表中的两个或更多单词共享同一个字母，则此函数 return 会重复。所以正确的做法应该是用所有 return 填充一个列表，然后消除重复的

如何在恒定长度内找到两个字符串的所有可能排列

How to find all possible permutation of two strings within constant length

python

string

combinations

permutation

itertools