How to generate a permutation combination that does not repeat and does not contiguous identical characters based on a given character set and number of layers?

Character sets and layers: efficiently generate unique permutations

This article explores how to generate a permutation combination without duplicates and without consecutive identical characters based on a given character set and number of layers. For example, the character set {a, b}, the three-layer permutation combination should contain aab, aba, abb, baa, bab, bba, etc., but not aaa, bbb and other consecutive repeated characters. This requires algorithms to handle deduplication and avoid continuous duplication of characters.

The core challenge is to design an algorithm that can adapt to different character sets and layers and efficiently generate permutations that meet the criteria. This article will introduce two methods: digital replacement method and backtracking method.

Method 1: Digital replacement method

This method treats the permutation combination as an m-digit number (m is the character set size). For example, the character set {a, b} corresponds to a binary number. 00 represents aa, 01 represents ab, and so on. By traversing all m-digit numbers and replacing characters, you can get all possible combinations. To avoid continuous identical characters, specific m-digit numbers need to be excluded, such as numbers where all bits are the same.

Python code example:

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

print(solve_digit('ab', 2)) # ['ab', 'ba']
print(solve_digit('ab', 2, True)) # ['aa', 'ab', 'ba', 'bb']
print(solve_digit('ab', 3)) # ['aab', 'aba', 'abb', 'baa', 'bab', 'bba']
print(solve_digit('abc', 2)) # ['ab', 'ac', 'ba', 'bc', 'ca', 'cb']

Method 2: Backtracking method

Backtrace is a recursive algorithm that finds results by trying all possible combinations. Add a character to the current combination at each step and recursively generates longer combinations. At the same time, it is necessary to track whether the previous characters are the same to avoid combinations that do not meet the conditions.

Python code example:

 def solve_backtracking(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_backtracking('AB', 2)) # ['AB', 'BA']
print(solve_backtracking('AB', 2, True)) # ['AA', 'AB', 'BA', 'BB']
print(solve_backtracking('AB', 3)) # ['AAB', 'ABA', 'ABB', 'BAA', 'BAB', 'BBA']
print(solve_backtracking('ABC', 2)) # ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

Both methods can solve the problem. The digital replacement method is more efficient and the backtracking method is easier to understand. Which method to choose depends on the specific application scenario and personal preferences.

The above is the detailed content of How to generate a permutation combination that does not repeat and does not contiguous identical characters based on a given character set and number of layers?. For more information, please follow other related articles on the PHP Chinese website!