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

amosmz
  • 3
新手上路,请多包涵

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

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

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

回复
阅读 362
1 个回答
Mannix
  • 1.1k
✓ 已被采纳

方法一:数位替换

可以递增一个 \( 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']
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏