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

Question

数组A,B ,通过层数 求得排列组合

第一层:A、B
第二次:AB（去重,并且不能AA,BB）
AB
AA
BA
BB

第三层:类似上
AAA
ABA
ABB
AAB
BAA
BAB
BBA
BBB
求个思路(解题答案更好了)，数组不一定是A,B可能是A,B,C等。层数也不是固定。

Answer 1

方法一：数位替换

可以递增一个 \( m \) 进制数，替换每一数位即可，以 \( AB,m=2 \) 层为例

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

不希望每一位都相同，判断是否能除尽 \( 11 \) 即可
参考代码（Python）：

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（或者自己维护一个栈），同时可以维护一个前面全部字符是否相同的标志
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']