如何在Java中生成符合进程操作顺序约束的资源操作全排列

核心思路 #

问题本质是多个有序子序列的交错合并：每个进程的资源操作是固定顺序的子序列，我们需要生成所有可能的交错组合，确保每个子序列内部的操作顺序严格遵循原进程定义，不同进程的操作可自由穿插。

修改后的Java实现 #

import java.util.ArrayList;
import java.util.List;

public class ResourceOperationPermutations {
    // 封装单个资源操作：进程名 + 操作类型
    static class Operation {
        String process;
        String action;

        public Operation(String process, String action) {
            this.process = process;
            this.action = action;
        }

        @Override
        public String toString() {
            return process + ": " + action;
        }
    }

    public static List<List<Operation>> generateValidPermutations(List<List<Operation>> processOperations) {
        List<List<Operation>> result = new ArrayList<>();
        // 记录每个进程当前已处理到的操作索引
        int[] currentIndices = new int[processOperations.size()];
        // 计算总操作数，作为递归终止条件
        int totalOps = processOperations.stream().mapToInt(List::size).sum();
        backtrack(processOperations, currentIndices, new ArrayList<>(), totalOps, result);
        return result;
    }

    private static void backtrack(List<List<Operation>> processOps, int[] indices, List<Operation> currentPath, int totalOps, List<List<Operation>> result) {
        // 所有操作都已加入当前路径，保存结果
        if (currentPath.size() == totalOps) {
            result.add(new ArrayList<>(currentPath));
            return;
        }

        // 遍历所有进程，尝试取出每个进程的下一个未处理操作
        for (int i = 0; i < processOps.size(); i++) {
            List<Operation> ops = processOps.get(i);
            // 若当前进程还有未处理的操作
            if (indices[i] < ops.size()) {
                Operation nextOp = ops.get(indices[i]);
                currentPath.add(nextOp);
                indices[i]++;
                // 递归构建后续排列
                backtrack(processOps, indices, currentPath, totalOps, result);
                // 回溯：移除操作，恢复索引状态
                currentPath.remove(currentPath.size() - 1);
                indices[i]--;
            }
        }
    }

    public static void main(String[] args) {
        // 测试用例1：两个进程，A有2个顺序操作，B有1个操作
        System.out.println("=== 测试用例1 ===");
        List<List<Operation>> test1 = new ArrayList<>();
        List<Operation> processA = List.of(new Operation("A", "请求R"), new Operation("A", "请求S"));
        List<Operation> processB = List.of(new Operation("B", "请求R"));
        test1.add(processA);
        test1.add(processB);
        List<List<Operation>> result1 = generateValidPermutations(test1);
        result1.forEach(perm -> System.out.println(perm));

        // 测试用例2：三个进程，X、Y各有2个顺序操作，Z有1个操作
        System.out.println("\n=== 测试用例2 ===");
        List<List<Operation>> test2 = new ArrayList<>();
        List<Operation> processX = List.of(new Operation("X", "请求P"), new Operation("X", "释放P"));
        List<Operation> processY = List.of(new Operation("Y", "请求Q"), new Operation("Y", "释放Q"));
        List<Operation> processZ = List.of(new Operation("Z", "请求R"));
        test2.add(processX);
        test2.add(processY);
        test2.add(processZ);
        List<List<Operation>> result2 = generateValidPermutations(test2);
        result2.forEach(perm -> System.out.println(perm));
    }
}

代码说明 #

1. Operation类：简洁封装单个资源操作的进程标识和具体动作，便于后续打印和逻辑处理。
2. generateValidPermutations方法：初始化递归依赖的索引数组和结果集合，触发回溯逻辑生成所有合法排列。
3. backtrack回溯方法：
   • 终止条件：当前路径的操作数等于总操作数时，将当前路径的副本存入结果集。
   • 遍历逻辑：逐个检查每个进程是否有未处理的操作，若有则取出下一个操作加入路径，更新索引后递归，最后回溯恢复状态以尝试其他分支。

测试用例输出说明 #

• 测试用例1：共生成3种合法排列，均保证A的"请求R"在"请求S"之前，B的操作可穿插在任意位置。
• 测试用例2：共生成10种合法排列（计算方式：(2+2+1)!/(2!*2!*1!)=10），所有排列均严格遵循X、Y各自的操作顺序。

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