编写 Python 程序查找给定字符串的排列

2024 年 8 月 29 日 | 5 分钟阅读

在本教程中，我们将编写Python程序来查找给定字符串的排列。问题是给定一个字符串S，我们需要以字典序找到给定字符串的所有唯一排列。下面是一个例子 -

示例 - 1

Input: ABC

Output:
ABC ACB BAC BCA CAB CBA

Explanation:
Given string ABC has permutations in 6 
forms as ABC, ACB, BAC, BCA, CAB and CBA 

示例 - 2

Input: ABSG

Output:
ABGS ABSG AGBS AGSB ASBG ASGB BAGS 
BASG BGAS BGSA BSAG BSGA GABS GASB 
GBAS GBSA GSAB GSBA SABG SAGB SBAG 
SBGA SGAB SGBA

Explanation:
Given string ABSG has 24 permutations.

解决方案

我们将使用递归回溯方法来解决这个问题。让我们理解下面的代码片段。

示例 -

def unique_permutations(string):
    # Convert the string to a list of characters
    chars = list(string)
    # Sort the characters in lexicographic order
    chars.sort()
    
    # Create a list to store the permutations
    result = []
    
    # Define a recursive function to generate permutations
    def backtrack(start):
        # If the start index reaches the end of the string,
        # It means we have a valid permutation, so add it to the result
        if start == len(chars):
            result.append(''.join(chars))
        
        # Iterate from the start index to the end of the string
        for i in range(start, len(chars)):
            # Skip if the current character is the same as the previous character
            if i != start and chars[i] == chars[start]:
                continue
            
            # Swap the characters at the start and current indices
            chars[start], chars[i] = chars[i], chars[start]
            
            # Recursively generate permutations for the remaining characters
            backtrack(start + 1)
            
            # Restore the original order by swapping back the characters
            chars[start], chars[i] = chars[i], chars[start]
    
    # Call the backtrack function to start generating permutations
    backtrack(0)
    
    return result

# Example usage
string = "ABC"
permutations = unique_permutations(string)
for permutation in permutations:
    print(permutation)

输出

ABC
ACB
BAC
BCA
CAB
CBA

解释 -

在上面的代码中，我们定义了一个unique_permutations()函数，它接收字符串，将其转换为字符列表，按字典序对其进行排序，然后使用递归回溯方法生成所有唯一排列。排列存储在结果列表中并作为最终输出返回。

方法 - 2

在此方法中，我们将使用itertools库和set数据结构。

示例 -

import itertools

def unique_permutations(string):
    # Generate all permutations of the string
    perms = itertools.permutations(string)
    # Use a set to remove duplicates and sort the permutations
    unique_perms = sorted(set(perms))
    
    # Print each unique permutation
    for perm in unique_perms:
        print(''.join(perm))
string = "ABC"
print(unique_permutations(string))

输出

ABC
ACB
BAC
BCA
CAB
CBA

解释 -

在此实现中，使用itertools.permutations函数生成给定字符串的所有可能排列。然后将这些排列传递给set函数以消除重复项，最后进行排序以确保字典序。使用print语句打印每个唯一排列。

方法 - 3

在此方法中，我们利用itertools和functools库的组合来解决问题。让我们理解下面的例子。

示例 -

import itertools
import functools

def compare_permutations(perm1, perm2):
    # Concatenate the permutations in different orders
    order1 = perm1 + perm2
    order2 = perm2 + perm1

    # Compare the concatenated permutations lexicographically
    if order1 < order2:
        return -1
    elif order1 > order2:
        return 1
    else:
        return 0

def unique_permutations(string):
    # Generate all permutations of the string
    perms = itertools.permutations(string)
    # Sort the permutations using custom comparison function
    sorted_perms = sorted(perms, key=functools.cmp_to_key(compare_permutations))
    
    # Convert permutations to strings
    unique_perms = [''.join(perm) for perm in sorted_perms]
    
    return unique_perms

# Example usage
string = "ABC"
permutations = unique_permutations(string)
for permutation in permutations:
    print(permutation)

输出 -

在此解决方案中，unique_permutations()函数使用itertools.permutations()函数生成给定字符串的所有可能排列。然后使用sorted函数和自定义比较函数compare_permutations()对排列进行排序。compare_permutations()函数通过以不同顺序连接两个排列并以字典序比较结果字符串来比较它们。

functools.cmp_to_key()函数用于将比较函数转换为适合排序的键函数。最后，将排序后的排列转换回字符串并作为结果返回。

方法 - 4

为了以字典序获取给定字符串的所有唯一排列，我们将使用带有记忆化的递归方法。此方法可以帮助避免冗余计算并提高效率。让我们理解下面的例子。

示例 -

def unique_permutations(string):
    # Create a dictionary to store already computed permutations
    memo = {}
    
    # Define a recursive function to generate permutations
    def generate_permutations(remaining):
        # Base case: If there is only one character remaining,
        # return a list with that character as the only permutation
        if len(remaining) == 1:
            return [remaining]
        
        # Check if the permutations for the remaining characters have already been computed
        if remaining in memo:
            return memo[remaining]
        
        permutations = []
        
        # Generate permutations by fixing each character at the beginning
        for i in range(len(remaining)):
            fixed_char = remaining[i]
            # Exclude the fixed character from the remaining characters
            remaining_chars = remaining[:i] + remaining[i+1:]
            
            # Recursively generate permutations for the remaining characters
            sub_permutations = generate_permutations(remaining_chars)
            
            # Append the fixed character to each sub-permutation
            for sub_permutation in sub_permutations:
                permutations.append(fixed_char + sub_permutation)
        
        # Store the computed permutations in the memoization dictionary
        memo[remaining] = permutations
        
        return permutations
    
    # Call the recursive function to generate permutations
    all_permutations = generate_permutations(string)
    
    # Sort the permutations in lexicographic order
    sorted_permutations = sorted(all_permutations)
    
    return sorted_permutations

# Example usage
string = "ABC"
permutations = unique_permutations(string)
for permutation in permutations:
    print(permutation)

输出

ABC
ACB
BAC
BCA
CAB
CBA

解释 -

在此实现中，unique_permutations()函数接收字符串并使用递归函数generate_permutations()来生成所有唯一排列。该函数递归地将每个字符固定在开头，并为剩余字符生成排列。使用记忆化来存储已计算的排列，以避免冗余计算。

然后使用sorted函数按字典序对计算出的排列进行排序。最后，将排序后的排列作为结果返回。

这种带有记忆化的方法提供了一种替代解决方案，通过避免重复计算来减少计算时间。

下一个主题编写Python程序根据另一个数组对数组进行排序

← 上一个下一个 →

编写 Python 程序查找给定字符串的排列

方法 - 2

方法 - 3

方法 - 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

编写 Python 程序查找给定字符串的排列

方法 - 2

方法 - 3

方法 - 4

相关帖子

编写程序打印给定二维矩阵的对角线元素

如何在 Python 中调用函数

Python 程序查找包含最多 1 的行

Python Bio 模块

学习 Django 的最佳书籍

Java 开发人员的 Python 基础

Python 中的简单待办事项列表 GUI 应用程序

Python 中的 Apache Airflow

缺失数据难题：探索和插补技术

在 Python 中反转链表

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器