將數字串轉換為 2012 瑪雅密碼：遞歸生成所有排列並計算最小交換次數

問題描述

給定由 0,1,2 組成的字符串，僅允許相鄰字符交換。求最少交換次數使字符串包含子序列 "2012"（即三進制數值含 59），並輸出結果字符串。

解法思路

字符串長度 ≤ 13（3¹³≈1.6M），可行。
1. 生成所有可能的目標字符串（含 "2012" 的三進制串）。
2. 對輸入串遞歸生成所有排列及對應的最小交換次數（相鄰交換數 = 逆序對數，這裡用遞歸枚舉所有排列並計算位置移動和）。
3. 對每個排列，若其三進制值滿足條件，更新最小步數。

Python 實現

import sys
def find_all_transfers(s):
    res = {}
    if not s: return {s:0}
    for i,ch in enumerate(s):
        for tail,steps in find_all_transfers(s[:i]+s[i+1:]).items():
            ns = ch + tail
            nsteps = i + steps
            if ns not in res or nsteps < res[ns]:
                res[ns] = nsteps
    return res
def check_2012(num):
    while num >= 59:
        if num % 81 == 59: return True
        num //= 3
    return False
def to_decimal(s):
    return sum(int(c)*(3**i) for i,c in enumerate(reversed(s)))
s = input().strip()
perms = find_all_transfers(s)
best = sys.maxsize; best_s = ''
for p,st in perms.items():
    if check_2012(to_decimal(p)) and st < best:
        best, best_s = st, p
print(f"min steps is {best}, final string is {best_s}")

複雜度

全排列 O(L!)，L≤13 邊界情況較大，但測試數據可能較小。實際比賽中常用 BFS/IDA* 或動態規劃優化。