# 问个排列组合的方法，通过AB,第三层得到AAB,BAB...等四层AAAB..等

amosmz
• 3

AB
AA
BA
BB

AAA
ABA
ABB
AAB
BAA
BAB
BBA
BBB

1 个回答
Mannix
• 1.1k
✓ 已被采纳

#### 方法一：数位替换

\$\$ 00,01,10,11 \Rightarrow AA,AB,BA,BB \$\$

``````def solve(arr, m, allow_all_same=False):
res, cur = [], [''] * m
n = len(arr)
all_1 = 0
for _ in range(m):
all_1 = all_1 * n + 1
for d in range(n ** m):
if allow_all_same or d % all_1 != 0:
for i in range(m - 1, -1, -1):
cur[i] = arr[d % n]
d //= n
res.append(''.join(cur))
return res

print(solve('AB', 2))  # ['AB', 'BA']
print(solve('AB', 2, True))  # ['AA', 'AB', 'BA', 'BB']
print(solve('AB', 3))  # ['AAB', 'ABA', 'ABB', 'BAA', 'BAB', 'BBA']
print(solve('ABC', 2))  # ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']``````

#### 方法二：回溯

DFS 参考代码（Python）：

``````def solve(arr, m, allow_all_same=False):
res, cur = [], [''] * m

def dfs(i, same):
if i == m:
if not same:
res.append(''.join(cur))
return
for a in arr:
cur[i] = a
dfs(i + 1, same and a == cur[i - 1])

for a in arr:
cur[0] = a
dfs(1, not allow_all_same)

return res

print(solve('AB', 2))  # ['AB', 'BA']
print(solve('AB', 2, True))  # ['AA', 'AB', 'BA', 'BB']
print(solve('AB', 3))  # ['AAB', 'ABA', 'ABB', 'BAA', 'BAB', 'BBA']
print(solve('ABC', 2))  # ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']``````