递归与列表变换：旋转反转找最小步数

一分耕耘，一分收获！既然打开了这篇文章《递归与列表变换：旋转反转找最小次数》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

本教程详细阐述如何通过递归算法，利用列表的旋转（rotate）和反转（reverse）操作，计算将一个给定列表转换为目标列表所需的最少操作次数。文章深入探讨了基于状态空间搜索的递归方法，包括关键的剪枝优化策略，并提供了完整的Java代码实现，旨在帮助读者理解并实现高效的列表转换路径查找。

列表转换问题概述

在编程实践中，我们常会遇到需要对数据结构进行变换以达到特定状态的问题。本教程聚焦于一个具体的列表转换场景：给定一个初始列表 a 和一个目标列表 b，这两个列表包含相同的元素但顺序可能不同。我们的任务是使用两种基本操作——旋转 (rotate) 和反转 (reverse)——将列表 a 转换成列表 b，并找出完成此转换所需的最小操作次数，同时记录操作序列。

• 旋转 (rotate)：将列表的最后一个元素移动到列表的开头。例如，[1, 2, 3, 4] 经过一次旋转变为 [4, 1, 2, 3]。
• 反转 (reverse)：将列表的元素顺序完全颠倒。例如，[1, 2, 3, 4] 经过一次反转变为 [4, 3, 2, 1]。

这个问题的挑战在于，从 a 到 b 可能存在多条操作路径，我们必须找到其中操作次数最少的那一条。简单的贪婪算法可能无法找到全局最优解，因此需要一种更全面的搜索策略。

递归算法设计思想

解决这类问题的一个有效方法是将问题建模为状态空间搜索。每个列表的当前状态可以看作是搜索树中的一个节点，而 rotate 和 reverse 操作则是连接这些节点的边。我们的目标是从初始状态（列表 a）出发，通过最少的边到达目标状态（列表 b）。

由于我们需要找到“最少”操作次数，这通常暗示着广度优先搜索（BFS）或经过优化的深度优先搜索（DFS）。在这里，我们将采用一种带有剪枝策略的递归（深度优先）方法来探索所有可能的转换路径。

核心的递归函数将接收以下参数：

1. currentList：当前正在操作的列表状态。
2. targetList：目标列表。
3. currentCount：当前已执行的操作次数。
4. lastOperation：上一步执行的操作，用于实现剪枝优化。

操作函数的实现

为了确保递归过程的正确性并避免副作用，rotate 和 reverse 操作必须返回一个新的列表，而不是修改原始输入列表。Java的 java.util.Collections 工具类提供了方便的方法来实现这些操作。

import java.util.*;

// 定义操作类型枚举
enum OP {
    REV, // 反转
    ROT  // 旋转
}

public class ListTransformer {

    /**
     * 对列表进行旋转操作，将最后一个元素移动到开头。
     * 返回一个新的列表，不修改原列表。
     * @param list 原始列表
     * @return 旋转后的新列表
     */
    private static List<Integer> rotate(List<Integer> list) {
        var newList = new ArrayList<>(list);
        Collections.rotate(newList, 1); // 将列表向右旋转1位
        return newList;
    }

    /**
     * 对列表进行反转操作。
     * 返回一个新的列表，不修改原列表。
     * @param list 原始列表
     * @return 反转后的新列表
     */
    private static List<Integer> reverse(List<Integer> list) {
        var newList = new ArrayList<>(list);
        Collections.reverse(newList); // 反转列表
        return newList;
    }

    // ... 递归函数和主函数将在此处定义
}

优化策略：避免冗余操作

在递归搜索过程中，存在一些可以避免的冗余路径，从而显著提高效率。最明显的一个是：

• 连续两次反转会还原列表：reverse(reverse(list)) 等同于 list。因此，如果上一步操作是 reverse，那么下一步就没有必要再次执行 reverse，因为这只会浪费一次操作并回到上一个状态。

为了实现这一优化，我们在递归函数中引入 parentOP 参数，它记录了导致当前 currentList 状态的上一步操作。

递归函数的详细实现

现在，我们来构建核心的递归函数 minimumOpsRec。这个函数不仅要返回最小操作数，还要返回对应的操作序列。

public class ListTransformer {
    // ... (rotate, reverse, OP enum definitions) ...

    /**
     * 递归地寻找从当前列表到目标列表的最少操作次数和操作序列。
     * @param currentList 当前列表状态
     * @param targetList 目标列表
     * @param count 当前已执行的操作次数
     * @param parentOP 导致当前列表状态的上一步操作
     * @return 包含最小操作数和操作序列的Map.Entry对象
     */
    public static Map.Entry<Integer, List<OP>> minimumOpsRec(
            List<Integer> currentList, List<Integer> targetList, int count, OP parentOP) {

        // 基本情况 1: 如果当前列表已达到目标列表，返回当前操作数和操作序列。
        // 注意：这里的操作序列在返回时会逐层添加当前操作。
        if (Objects.equals(currentList, targetList)) {
            // 返回一个包含当前操作数和仅包含parentOP的列表。
            // 稍后在递归栈回溯时，会逐层添加父操作。
            return new AbstractMap.SimpleEntry<>(count, new ArrayList<>(List.of(parentOP)));
        }

        // 基本情况 2: 剪枝条件。如果操作次数超过列表大小，
        // 认为这条路径不是最优解或不可达。
        // 这是一个启发式剪枝，对于某些复杂情况可能需要调整。
        if (count > currentList.size() * 2) { // 增加乘数以允许更长的路径，例如2倍
            return new AbstractMap.SimpleEntry<>(Integer.MAX_VALUE, new ArrayList<>());
        }

        count++; // 每次递归调用都代表执行了一次操作，所以操作数递增

        Map.Entry<Integer, List<OP>> revResult = null;
        Map.Entry<Integer, List<OP>> rotResult;

        // 优化剪枝：如果上一步是反转 (REV)，则当前步不应再次反转。
        // 否则，探索反转分支。
        if (parentOP == OP.ROT) { // 只有当上一步是旋转时，才考虑反转
            revResult = minimumOpsRec(reverse(currentList), targetList, count, OP.REV);
        } else { // 如果上一步是REV，那么当前步不能是REV，但为了保持逻辑完整性，这里可以不进行操作
            // 或者，更严格地说，如果parentOP是REV，那么revResult应该直接为MAX_VALUE
            revResult = new AbstractMap.SimpleEntry<>(Integer.MAX_VALUE, new ArrayList<>());
        }

        // 总是探索旋转分支，因为连续旋转是有效的。
        rotResult = minimumOpsRec(rotate(currentList), targetList, count, OP.ROT);

        // 比较两个分支的结果，选择操作数更小的那个。
        // 注意：需要处理 revResult 可能为 null 的情况，或者其值为 MAX_VALUE 的情况。
        if (revResult != null && revResult.getKey() <= rotResult.getKey()) {
            // 如果反转分支更优或相等，将当前操作 (parentOP) 添加到其操作序列中
            revResult.getValue().add(parentOP);
            return revResult;
        } else {
            // 如果旋转分支更优，将当前操作 (parentOP) 添加到其操作序列中
            rotResult.getValue().add(parentOP);
            return rotResult;
        }
    }

    /**
     * 主函数，用于启动递归搜索。
     * @param a 初始列表
     * @param b 目标列表
     * @return 包含最小操作数和操作序列的Map.Entry对象
     */
    public static Map.Entry<Integer, List<OP>> minimumOps(List<Integer> a, List<Integer> b) {
        if (Objects.equals(a, b)) {
            return new AbstractMap.SimpleEntry<>(0, new ArrayList<>()); // 初始列表即为目标列表，0操作
        }

        // 初始调用：分别尝试从反转a和旋转a开始
        // 注意：这里的count从1开始，因为已经执行了一次操作
        Map.Entry<Integer, List<OP>> revInitial = minimumOpsRec(reverse(a), b, 1, OP.REV);
        Map.Entry<Integer, List<OP>> rotInitial = minimumOpsRec(rotate(a), b, 1, OP.ROT);

        // 比较两个初始分支的结果，返回更优的解
        if (rotInitial.getKey() >= revInitial.getKey()) {
            // 如果反转分支更优或相等，返回反转分支的结果
            // 注意：revInitial.getValue() 已经包含了后续的操作，这里不需要再添加
            return revInitial;
        } else {
            // 如果旋转分支更优，返回旋转分支的结果
            return rotInitial;
        }
    }

    // ... (main method for testing) ...
}

关于 minimumOpsRec 中的 parentOP 处理的修正和解释: 在原始的答案中，if (parentOP == OP.ROT) rev = minimumOpsRec(...) 这一行是正确的，它意味着只有当上一步是 ROT 时，我们才考虑下一步是 REV。如果上一步是 REV，那么 rev 路径应该被排除（设置为 Integer.MAX_VALUE）。

同时，在 return 语句之前，rev.getValue().add(parent); 或 rot.getValue().add(parent); 是将当前递归层执行的操作（即 parentOP，它导致了 currentList）添加到其子路径的操作序列中。这是为了在递归回溯时，从最深层的操作开始，逐层构建完整的操作序列。

修正后的 minimumOpsRec 逻辑:

public static Map.Entry<Integer, List<OP>> minimumOpsRec(
        List<Integer> currentList, List<Integer> targetList, int count, OP currentOp) { // 这里的parent改为currentOp，表示当前层执行的操作

    if (Objects.equals(currentList, targetList)) {
        // 达到目标，返回当前操作数，操作序列仅包含当前操作
        return new AbstractMap.SimpleEntry<>(count, new ArrayList<>(List.of(currentOp)));
    }

    // 剪枝：如果操作次数过多，认为不可达或非最优
    // 这里可以根据实际情况调整乘数，例如 `currentList.size() * 2`
    if (count > currentList.size() * 2) {
        return new AbstractMap.SimpleEntry<>(Integer.MAX_VALUE, new ArrayList<>());
    }

    // 递增操作计数，为下一层递归做准备
    int nextCount = count + 1;

    Map.Entry<Integer, List<OP>> revResult = null;
    Map.Entry<Integer, List<OP>> rotResult;

    // 探索反转分支：只有当前操作不是 REV 时，才考虑下一步是 REV
    if (currentOp == OP.ROT) { // 如果当前操作是ROT，则下一步可以REV
        revResult = minimumOpsRec(reverse(currentList), targetList, nextCount, OP.REV);
    } else { // 如果当前操作是REV，则下一步不能是REV，避免 reverse(reverse(list))
        revResult = new AbstractMap.SimpleEntry<>(Integer.MAX_VALUE, new ArrayList<>());
    }

    // 探索旋转分支：总是可以旋转
    rotResult = minimumOpsRec(rotate(currentList), targetList, nextCount, OP.ROT);

    // 比较两个分支的结果
    Map.Entry<Integer, List<OP>> bestResult;
    if (revResult.getKey() <= rotResult.getKey()) {
        bestResult = revResult;
    } else {
        bestResult = rotResult;
    }

    // 将当前操作添加到最佳结果的操作序列中
    // 这里的currentOp是导致currentList的父操作
    bestResult.getValue().add(currentOp);
    return bestResult;
}

// 主函数调用逻辑保持不变，但需要调整 minimumOpsRec 的参数名
public static Map.Entry<Integer, List<OP>> minimumOps(List<Integer> a, List<Integer> b) {
    if (Objects.equals(a, b)) {
        return new AbstractMap.SimpleEntry<>(0, new ArrayList<>());
    }

    // 初始调用：从初始列表开始，分别尝试REV和ROT
    // 这里的count从1开始，因为已经执行了一次操作
    // 注意：这里的minimumOpsRec的currentOp参数代表的是“刚刚执行”的操作
    Map.Entry<Integer, List<OP>> revInitial = minimumOpsRec(reverse(a), b, 1, OP.REV);
    Map.Entry<Integer, List<OP>> rotInitial = minimumOpsRec(rotate(a), b, 1, OP.ROT);

    // 比较两个初始分支的结果，返回更优的解
    // 在这里，revInitial和rotInitial的getValue()已经包含了完整的操作序列
    if (rotInitial.getKey() >= revInitial.getKey()) {
        return revInitial;
    } else {
        return rotInitial;
    }
}

完整代码示例

import java.util.*;

class ListTransformer {

    // 定义操作类型枚举
    enum OP {
        REV, // 反转
        ROT  // 旋转
    }

    public static void main(String[] args) {
        var a = new ArrayList<>(List.of(1, 2, 3, 4));
        var b = new ArrayList<>(List.of(2, 1, 4, 3));
        Map.Entry<Integer, List<OP>> result = minimumOps(a, b);

        if (result.getKey() == Integer.MAX_VALUE) {
            System.out.println("无法转换或操作次数过多");
        } else {
            // 结果中的操作序列是逆序的，需要反转以显示正确的执行顺序
            List<OP> ops = result.getValue();
            Collections.reverse(ops); // 反转操作序列以显示正确顺序
            System.out.println("最小操作次数: " + result.getKey());
            System.out.println("操作序列: " + ops);
        }

        // 示例 2: 无法转换的情况 (或需要非常多的操作)
        var c = new ArrayList<>(List.of(1, 2, 3, 4));
        var d = new ArrayList<>(List.of(4, 2, 1, 3)); // 这是一个可能无法通过短路径转换的例子
        Map.Entry<Integer, List<OP>> result2 = minimumOps(c, d);
        if (result2.getKey() == Integer.MAX_VALUE) {
            System.out.println("\n列表 c 到 d 无法转换或操作次数过多。");
        } else {
            List<OP> ops2 = result2.getValue();
            Collections.reverse(ops2);
            System.out.println("\n最小操作次数 (c 到 d): " + result2.getKey());
            System.out.println("操作序列 (c 到 d): " + ops2);
        }
    }

    /**
     * 主函数，用于启动递归搜索。
     * @param a 初始列表
     * @param b 目标列表
     * @return 包含最小操作数和操作序列的Map.Entry对象
     */
    public static Map.Entry<Integer, List<OP>> minimumOps(List<Integer> a, List<Integer> b) {
        if (Objects.equals(a, b)) {
            return new AbstractMap.SimpleEntry<>(0, new ArrayList<>()); // 初始列表即为目标列表，0操作
        }

        // 初始调用：分别从反转a和旋转a开始
        // 这里的count从1开始，因为已经执行了一次操作
        // minimumOpsRec的最后一个参数是“当前这一步执行的操作”
        Map.Entry<Integer, List<OP>> revInitial = minimumOpsRec(reverse(a), b, 1, OP.REV);
        Map.Entry<Integer, List<OP>> rotInitial = minimumOpsRec(rotate(a), b, 1, OP.ROT);

        // 比较两个初始分支的结果，返回更优的解
        // 在这里，revInitial和rotInitial的getValue()已经包含了完整的操作序列
        if (rotInitial.getKey() >= revInitial.getKey()) {
            return revInitial;
        } else {
            return rotInitial;
        }
    }

    /**
     * 递归地寻找从当前列表到目标列表的最少操作次数和操作序列。
     * @param currentList 当前列表状态
     * @param targetList 目标列表
     * @param count 当前已执行的操作次数
     * @param currentOp 当前递归层执行的操作（即导致currentList的父操作）
     * @return 包含最小操作数和操作序列的Map.Entry对象
     */
    public static Map.Entry<Integer, List<OP>> minimumOpsRec(
            List<Integer> currentList, List<Integer> targetList, int count, OP currentOp) {

        // 基本情况 1: 如果当前列表已达到目标列表，返回当前操作数和操作序列。
        // 操作序列中仅包含导致这一状态的当前操作。
        if (Objects.equals(currentList, targetList)) {
            return new AbstractMap.SimpleEntry<>(count, new ArrayList<>(List.of(currentOp)));
        }

        // 基本情况 2: 剪枝条件。如果操作次数超过某个阈值，
        // 认为这条路径不是最优解或不可达。
        // 这里的阈值可以根据列表大小进行调整，例如 `currentList.size() * 2`
        if (count > current

今天关于《递归与列表变换：旋转反转找最小步数》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！