How to generate non-repetitive permutation combinations based on character set and number of layers, and exclude all characters of the same combinations?

Efficient generation of character arrangement and combination: avoid duplication and exclude all the same

This article describes how to generate non-repetitive permutation combinations based on a given character set and number of layers, and effectively exclude combinations where all characters are the same. For example, the character set is 'a' and 'b', which generates a combination of different layers: the first layer is 'a', 'b'; the second layer is 'ab', 'ba' (excluding 'aa', 'bb'); the third layer contains 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', etc.

We will adopt two algorithm strategies: digital replacement method and backtracking method.

Method 1: Digital replacement method (more concise)

This method treats permutations as m-digit numbers. Taking the character set 'a', 'b' as an example, 'a' is 0 and 'b' is 1. Second-layer combination: 00('aa'), 01('ab'), 10('ba'), 11('bb'). Iterate through all m-digit numbers and convert them into character combinations. In order to exclude the same combination, it is determined whether the generated m-digit number can be divisible by (11...1) (the number of 1 is equal to the number of layers m).

Python code example:

 def generate_combinations(charset, layers, allow_all_same=False):
    results = []
    n = len(charset)
    all_ones = sum(n**i for i in range(layers))
    for i in range(n**layers):
        if allow_all_same or i % all_ones != 0: #Exclude combination = ""
            temp = i
            for _ in range(layers):
                combination = charset[temp % n] combination
                temp //= n
            results.append(combination)
    Return results

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

Method 2: Backtracking method (easier to understand)

Backtrace is a recursive algorithm that tries all combinations. Add a character to the current combination at each step, and recursively generates longer combinations. Use the flag to determine whether the current combination is the same character, and avoid duplication and the same combination.

Python code example:

 def generate_combinations_recursive(charset, layers, allow_all_same=False):
    results = []
    current_combination = [''] * layers

    def backtrack(index, all_same):
        if index == layers:
            if not all_same:
                results.append("".join(current_combination))
            Return
        for char in charset:
            current_combination[index] = char
            backtrack(index 1, all_same and char == current_combination[index - 1] if index > 0 else False)

    for char in charset:
        current_combination[0] = char
        backtrack(1, not allow_all_same)

    Return results


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

Both methods can effectively solve the problem, and the choice depends on specific needs and preferences. The digital replacement method is simpler, and the backtracking method is easier to understand and expand.

The above is the detailed content of How to generate non-repetitive permutation combinations based on character set and number of layers, and exclude all characters of the same combinations?. For more information, please follow other related articles on the PHP Chinese website!