Python递归实现K次交换求最大值时如何正确返回结果

• 问题来源：GeeksforGeeks平台K次交换求最大数题目，题目链接

初始递归版本代码问题 #

初始编写的递归代码如下：

def swap_kdigits(s, k, maximum):
    if k == 0:
       return
    for i in range(0, len(s) - 1): 
   /* find maximum element on the right */
       maxc = s[i]
       for j in range(i + 1, len(s)):
          if int(s[j]) > int(maxc):
            maxc = s[j]

       if maxc != s[i]:
         idx = s.index(maxc)
         ll = list(s)
        # do the swap
         ll[i], ll[idx] = ll[idx], ll[i]
         s = ''.join(ll)
         maximum = max(int(s), maximum) /* update maximum values*/
        # make  a recursive call on the new string
         swap_kdigits(s, k - 1, maximum)
        # backtrack
         ll[i], ll[idx] = ll[idx], ll[i]

         s = ''.join(ll)


def main_fn(s, k):
    maximum = int(s) /*initialize maximum variable*/
    return swap_kdigits(s, k, maximum) /* call helper function */

无有效返回值的核心原因 #

1. Python中整数是不可变类型，参数按对象引用传递时，递归内层对maximum的赋值只会修改内层函数的局部变量，不会同步改变外层的变量值
2. 递归辅助函数swap_kdigits没有定义有效返回逻辑，终止分支直接return返回空值，外层main_fn调用后自然拿不到结果
3. 代码本身存在逻辑bug：用s.index(maxc)查找最大值索引时，只会返回第一个匹配的最大值位置，当右侧存在多个相同最大值时，无法枚举所有交换可能，会漏掉最优解。

递归版本修复方案 #

改为让递归函数直接返回当前分支计算得到的最大值，替代传参传递最大值的写法，同时修复最大值索引查找的bug，修复后代码如下：

def swap_kdigits(s, k):
    # 递归终止：无剩余交换次数，直接返回当前字符串对应数字
    if k == 0:
        return int(s)
    max_num = int(s)
    n = len(s)
    for i in range(n - 1):
        # 查找i位置右侧的最大数字
        max_digit = s[i]
        for j in range(i+1, n):
            if s[j] > max_digit:
                max_digit = s[j]
        # 当前位置已经是右侧最大，无需交换
        if max_digit == s[i]:
            continue
        # 枚举所有等于max_digit的位置交换，避免漏掉同值不同位置的最优解
        for j in range(i+1, n):
            if s[j] == max_digit:
                s_list = list(s)
                s_list[i], s_list[j] = s_list[j], s_list[i]
                current_s = ''.join(s_list)
                # 递归计算k-1次交换的最大值，更新当前结果
                current_max = swap_kdigits(current_s, k-1)
                if current_max > max_num:
                    max_num = current_max
    return max_num

调用时直接执行return swap_kdigits(s, k)即可拿到正确结果。

非递归版本问题说明 #

后续编写的非递归（贪心）版本代码如下：

def swap_kdigits(s, k):
# define current max
   maximum = int(s)

   for i in range(0, len(s) - 1):
      maxc = s[i]
      if k == 0:
        break
      for j in range(i + 1, len(s)):

         if int(s[j]) > int(maxc):
            maxc = s[j]
   

      if maxc != s[i]:
        k -= 1
        idx = s[i + 1:].rfind(maxc) + i + 1  # find last occurrence
        ll = list(s)
        # do the swap
        ll[i], ll[idx] = ll[idx], ll[i]
        s = ''.join(ll)
        # find the new max
        maximum = max(int(s), maximum)
       
  return maximum

该贪心版本无法通过所有测试用例：贪心策略每一步固定当前位置选择右侧最大值交换，属于局部最优选择，但K次交换问题中局部最优无法保证全局最优，例如s="1993",k=1场景下，贪心选择第一个9交换得到9193，但实际最优解是交换第二个9得到9913；更多多轮交换场景下，贪心提前消耗交换次数的选择会直接丢失全局最优解，这类问题的标准正确解法是带回溯的递归枚举。

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