如何用Python实现a、b、c全排列生成程序及识别自动机？

1. 生成a、b、c的全排列 #

Python可以直接借助标准库itertools.permutations快速生成所有符合要求的全排列，代码示例如下：

import itertools

# 生成所有长度为3的a/b/c全排列
permutations = [''.join(p) for p in itertools.permutations('abc', 3)]
print(permutations)
# 输出: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

该方法会自动保证每个字符仅使用一次，且生成的排列长度固定为3。

2. 构建自动机识别合法排列 #

我们可以用状态转移机实现识别逻辑，核心是通过状态跟踪已输入的字符，确保无重复输入且最终长度为3。

状态转移规则： #

• 初始状态：未输入任何字符
• 单字符状态：已输入第一个字符（分为seen_a/seen_b/seen_c三种）
• 双字符状态：已输入两个不重复的字符（分为seen_ab/seen_ac/seen_ba/seen_bc/seen_ca/seen_cb六种）
• 接受状态：输入第三个不重复字符，完成合法排列

Python实现代码： #

def is_valid_permutation(word):
    # 先校验长度是否为3
    if len(word) != 3:
        return False
    
    # 定义状态转移表：当前状态 -> {输入字符: 下一状态}
    state_transitions = {
        'start': {'a': 'seen_a', 'b': 'seen_b', 'c': 'seen_c'},
        'seen_a': {'b': 'seen_ab', 'c': 'seen_ac'},
        'seen_b': {'a': 'seen_ba', 'c': 'seen_bc'},
        'seen_c': {'a': 'seen_ca', 'b': 'seen_cb'},
        'seen_ab': {'c': 'accept'},
        'seen_ac': {'b': 'accept'},
        'seen_ba': {'c': 'accept'},
        'seen_bc': {'a': 'accept'},
        'seen_ca': {'b': 'accept'},
        'seen_cb': {'a': 'accept'},
        'accept': {}  # 接受状态无后续转移
    }
    
    current_state = 'start'
    for char in word:
        # 若当前字符不在状态转移规则中，判定为非法
        if char not in state_transitions[current_state]:
            return False
        current_state = state_transitions[current_state][char]
    
    # 最终状态必须为接受状态才合法
    return current_state == 'accept'

# 测试示例
test_cases = ['abc', 'acb', 'bac', 'bca', 'cab', 'cba', 'aab', 'abcd', 'ab']
for case in test_cases:
    print(f"{case}: {'合法' if is_valid_permutation(case) else '非法'}")

测试输出： #

abc: 合法
acb: 合法
bac: 合法
bca: 合法
cab: 合法
cba: 合法
aab: 非法
abcd: 非法
ab: 非法

以上代码完全用Python实现了排列生成与自动机识别的需求。

内容的提问来源于stack exchange，提问作者jin15