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

public static int hireAssistant1(int[] arr, int n) {
    ArrayList<Integer> 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(); // 返回雇佣的总次数
}

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

private void permuteHelper(List<List<Integer>> list, List<Integer> 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); // 回溯：移除当前元素，尝试其他选择
        }
    }
}

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

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

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

    // 遍历每一个独立的排列
    for (List<Integer> permutation : allPermutations) {
        // 将 List<Integer> 转换为 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<Integer> 转换为 int[]
static int[] toIntArray(List<Integer> 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);
}

public class Assignment8 {

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

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

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

        // 生成所有排列
        List<List<Integer>> 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));
    }
}