


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?
Apr 01, 2025 am 06:18 AMCharacter 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!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

The key to dealing with API authentication is to understand and use the authentication method correctly. 1. APIKey is the simplest authentication method, usually placed in the request header or URL parameters; 2. BasicAuth uses username and password for Base64 encoding transmission, which is suitable for internal systems; 3. OAuth2 needs to obtain the token first through client_id and client_secret, and then bring the BearerToken in the request header; 4. In order to deal with the token expiration, the token management class can be encapsulated and automatically refreshed the token; in short, selecting the appropriate method according to the document and safely storing the key information is the key.

To view Git commit history, use the gitlog command. 1. The basic usage is gitlog, which can display the submission hash, author, date and submission information; 2. Use gitlog--oneline to obtain a concise view; 3. Filter by author or submission information through --author and --grep; 4. Add -p to view code changes, --stat to view change statistics; 5. Use --graph and --all to view branch history, or use visualization tools such as GitKraken and VSCode.

The way to access nested JSON objects in Python is to first clarify the structure and then index layer by layer. First, confirm the hierarchical relationship of JSON, such as a dictionary nested dictionary or list; then use dictionary keys and list index to access layer by layer, such as data "details"["zip"] to obtain zip encoding, data "details"[0] to obtain the first hobby; to avoid KeyError and IndexError, the default value can be set by the .get() method, or the encapsulation function safe_get can be used to achieve secure access; for complex structures, recursively search or use third-party libraries such as jmespath to handle.

To test the API, you need to use Python's Requests library. The steps are to install the library, send requests, verify responses, set timeouts and retry. First, install the library through pipinstallrequests; then use requests.get() or requests.post() and other methods to send GET or POST requests; then check response.status_code and response.json() to ensure that the return result is in compliance with expectations; finally, add timeout parameters to set the timeout time, and combine the retrying library to achieve automatic retry to enhance stability.

Asynchronous programming is made easier in Python with async and await keywords. It allows writing non-blocking code to handle multiple tasks concurrently, especially for I/O-intensive operations. asyncdef defines a coroutine that can be paused and restored, while await is used to wait for the task to complete without blocking the entire program. Running asynchronous code requires an event loop. It is recommended to start with asyncio.run(). Asyncio.gather() is available when executing multiple coroutines concurrently. Common patterns include obtaining multiple URL data at the same time, reading and writing files, and processing of network services. Notes include: Use libraries that support asynchronously, such as aiohttp; CPU-intensive tasks are not suitable for asynchronous; avoid mixed

In Python, variables defined inside a function are local variables and are only valid within the function; externally defined are global variables that can be read anywhere. 1. Local variables are destroyed as the function is executed; 2. The function can access global variables but cannot be modified directly, so the global keyword is required; 3. If you want to modify outer function variables in nested functions, you need to use the nonlocal keyword; 4. Variables with the same name do not affect each other in different scopes; 5. Global must be declared when modifying global variables, otherwise UnboundLocalError error will be raised. Understanding these rules helps avoid bugs and write more reliable functions.

AMA in the currency circle is the abbreviation of Ask Me Anything, which is literally translated as "ask me any questions". This is a form of interaction between project parties and community members. Project teams usually broadcast live on specific platforms, such as Telegram groups, Discord servers, or via Twitter Spaces, to open questions to participants. Community members can take this opportunity to directly raise questions about any aspects such as technology, economic model, marketing promotion, roadmap, etc. to the core members of the project.

To create modern and efficient APIs using Python, FastAPI is recommended; it is based on standard Python type prompts and can automatically generate documents, with excellent performance. After installing FastAPI and ASGI server uvicorn, you can write interface code. By defining routes, writing processing functions, and returning data, APIs can be quickly built. FastAPI supports a variety of HTTP methods and provides automatically generated SwaggerUI and ReDoc documentation systems. URL parameters can be captured through path definition, while query parameters can be implemented by setting default values ??for function parameters. The rational use of Pydantic models can help improve development efficiency and accuracy.
