Java中排列组合的生成与概率计算：以“招聘助理”问题为例

1. 问题背景与“招聘助理”算法概述

在算法分析中，我们经常会遇到需要对所有可能的输入序列进行统计分析的场景。一个经典的例子是“招聘助理问题”：假设我们面试n位助理候选人，他们的能力值（或排名）以某种随机顺序出现。我们总是雇佣第一个面试者，之后每当遇到比当前已雇佣助理更优秀的候选人时，就解雇现有助理并雇佣这位更优秀的。我们的目标是计算在所有可能的面试顺序（即所有排列）中，恰好雇佣了特定次数助理的概率。

核心算法hireAssistant1用于模拟这一过程并计算雇佣次数：

public static int hireAssistant1(int[] arr, int n) {
    ArrayList hired = new ArrayList<>(); // 记录雇佣的助理能力值
    int best = arr[0]; // 初始雇佣第一个
    hired.add(best);
    for (int i = 1; i < n; i++) {
        if (arr[i] < best) { // 如果遇到更优秀的
            best = arr[i]; // 更新最佳人选
            hired.add(best); // 记录新的雇佣
        }
    }
    return hired.size(); // 返回雇佣的总次数
}

此方法接收一个整数数组arr（代表候选人的排名序列）和总人数n，返回在此特定序列下雇佣助理的次数。

2. 生成所有排列组合

为了计算在所有可能的面试顺序中恰好雇佣两次的概率，我们需要生成n个候选人排名的所有n!种排列。这可以通过递归回溯法实现。

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors; // 稍后可能用到，先导入

// 假设这些方法在一个名为 Assignment8 的类中

public static int[] makeArray(int n) {
    int[] arr = new int[n];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i + 1; // 生成1到n的排名数组
    }
    return arr;
}

public List> permute(int[] arr) {
    List> list = new ArrayList<>();
    permuteHelper(list, new ArrayList<>(), arr);
    return list; // 返回所有排列的列表，每个排列是一个List
}

private void permuteHelper(List> list, List resultList, int[] arr) {
    if (resultList.size() == arr.length) {
        list.add(new ArrayList<>(resultList)); // 找到一个完整的排列，添加到结果列表
    } else {
        for (int i = 0; i < arr.length; i++) {
            if (resultList.contains(arr[i])) {
                continue; // 如果当前元素已在结果列表中，跳过
            }
            resultList.add(arr[i]); // 选择当前元素
            permuteHelper(list, resultList, arr); // 递归生成后续排列
            resultList.remove(resultList.size() - 1); // 回溯：移除当前元素，尝试其他选择
        }
    }
}

permute方法是入口，它调用permuteHelper来递归地构建所有排列。最终，permute方法返回一个List>，其中外层列表包含所有排列，每个内层List代表一个独立的排列序列。

立即学习“Java免费学习笔记（深入）”；

3. 正确处理单个排列并计算概率

原始代码中存在一个常见误区：在获得所有排列List>后，错误地使用了listToList方法将其扁平化为一个巨大的List。

// 原始代码中的错误方法：将所有排列扁平化
static List listToList(List> list) {
    List flat =
            list.stream()
                    .flatMap(List::stream)
                    .collect(Collectors.toList());
    return flat;
}

这个listToList方法会将例如[[1,2,3], [1,3,2]]这样的排列列表，错误地转换为[1,2,3,1,3,2]这样的单一列表。如果将这个扁平化的列表传递给hireAssistant1，它将不再是对单个排列的独立评估，而是对一个拼接起来的超长序列进行评估，这显然不符合计算每个排列概率的初衷。

虎课网

虎课网是超过1800万用户信赖的自学平台，拥有海量设计、绘画、摄影、办公软件、职业技能等优质的高清教程视频，用户可以根据行业和兴趣爱好，自主选择学习内容，每天免费学习一个...

下载

正确的做法是遍历permute方法返回的List>，对其中的每一个List（即每一个独立的排列）调用hireAssistant1方法。

下面是修正后的methodThreePerm方法，用于正确计算恰好雇佣两次的概率：

public static void methodThreePerm(List> allPermutations, int n) {
    // 总排列数 n! 可以通过阶乘函数计算，也可以直接使用 allPermutations.size()
    // int size = factorial(n); // 阶乘函数，也可以直接用 allPermutations.size()
    double totalPermutations = allPermutations.size(); // 确保是所有排列的总数

    double countHiresEqualToTwo = 0; // 记录雇佣次数恰好为2的排列数量

    // 遍历每一个独立的排列
    for (List permutation : allPermutations) {
        // 将 List 转换为 int[]，因为 hireAssistant1 接收 int[]
        int[] arr = toIntArray(permutation);

        int hires = hireAssistant1(arr, n); // 对当前排列计算雇佣次数
        if (hires == 2) {
            countHiresEqualToTwo++; // 如果雇佣次数为2，则计数
        }
    }

    // 计算并输出概率
    System.out.println("Method 3: s/n! = " + countHiresEqualToTwo / totalPermutations);
}

// 辅助方法：将 List 转换为 int[]
static int[] toIntArray(List list) {
    int[] ret = new int[list.size()];
    for (int i = 0; i < ret.length; i++) {
        ret[i] = list.get(i);
    }
    return ret;
}

// 阶乘函数 (如果需要独立计算总排列数)
public static int factorial(int n) {
    if (n == 0 || n == 1) return 1;
    return n * factorial(n - 1);
}

4. 完整示例与运行

结合所有部分，main方法将如下所示：

public class Assignment8 {

    // ... (makeArray, hireAssistant1, permute, permuteHelper, toIntArray, factorial 方法放在这里) ...

    public static void methodThreePerm(List> allPermutations, int n) {
        // ... (同上文修正后的 methodThreePerm) ...
    }

    public static void main(String[] args) {
        Assignment8 pa = new Assignment8(); // 创建实例以调用非静态的 permute 方法
        int n = 6; // 设定候选人数量

        // 生成所有排列
        List> allPermutations = pa.permute(makeArray(n));

        System.out.println("N = " + n);
        // 调用修正后的方法来计算概率
        methodThreePerm(allPermutations, n);

        // 作为参考，可以打印理论值（如果已知）
        // methodOneSum1(n); // 原始答案中提供的理论方法
    }

    // 原始答案中提供的理论计算方法 (仅供参考，其推导不在本文范畴)
    static void methodOneSum1(int n) {
        double sum = 0;
        for (double i = 2; i <= n; i++)
            sum += 1 / ((double) (i - 1));
        System.out.println("Method 1: n = " + (sum / n));
    }
}

当n = 6时，运行此代码，methodThreePerm将遍历6! = 720个排列，对每个排列独立调用hireAssistant1，然后统计其中雇佣次数为2的排列数量，最终计算出概率。这个结果应该与理论计算值（如methodOneSum1所示）相符。

5. 注意事项与总结

• 数据结构理解至关重要： List>和List是截然不同的。前者是“列表的列表”，每个内层列表是一个独立的数据单元；后者是扁平化的单一列表。混淆它们会导致逻辑错误。
• 性能考虑： 生成所有排列的时间复杂度是O(n!)，这对于较大的n（例如n > 10或12）会变得非常慢甚至不可行。在实际应用中，如果n很大，通常需要采用蒙特卡洛模拟或其他近似方法，而不是穷举所有排列。
• 算法验证： 在处理排列组合和概率计算时，如果存在理论上的解析解（如本例中的methodOneSum1），将其与实验结果进行对比是验证代码正确性的重要步骤。

通过遵循上述步骤和注意事项，我们可以有效地在Java中生成和处理所有排列组合，并对每种排列进行独立的算法分析，从而准确计算特定事件的发生概率。