Java中处理全排列：模拟雇佣问题与概率计算的正确姿势

public static int hireAssistant1(int[] arr, int n) {
    ArrayList<Integer> hired = new ArrayList<Integer>();
    // 第一个候选人总是被雇佣
    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(); // 返回雇佣的总人数
}

public List<List<Integer>> permute(int[] arr) {
    List<List<Integer>> list = new ArrayList<>();
    permuteHelper(list, new ArrayList<>(), arr);
    return list;
}

private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int[] arr) {
    // 递归终止条件：当resultList的长度等于原始数组长度时，表示一个完整的排列已生成
    if (resultList.size() == arr.length) {
        list.add(new ArrayList<>(resultList)); // 将当前排列添加到结果列表中
    } else {
        // 遍历原始数组中的每个元素
        for (int i = 0; i < arr.length; i++) {
            // 如果当前元素已在resultList中，则跳过（避免重复）
            if (resultList.contains(arr[i])) {
                continue;
            }
            resultList.add(arr[i]); // 将元素添加到当前排列中
            permuteHelper(list, resultList, arr); // 递归调用
            resultList.remove(resultList.size() - 1); // 回溯：移除最后一个元素，尝试其他路径
        }
    }
}

public static void main(String[] args) {
    Assignment8 pa = new Assignment8();
    int n = 6;
    List<List<Integer>> p = pa.permute(makeArray(n)); // p 包含所有独立的排列
    List<Integer> list = listToList(p); // 错误：将所有排列扁平化为一个大列表
    System.out.println("N = 6");
    methodThreePerm(list, n); // 将扁平化列表传递给处理方法
}

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors; // For listToList, though it's removed in solution

public class PermutationHiring {

    // 辅助方法：创建包含1到n的数组
    public static int[] makeArray(int n) {
        int arr[] = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }
        return arr;
    }

    // 雇佣模拟方法
    public static int hireAssistant1(int[] arr, int n) {
        // ArrayList<Integer> hired = new ArrayList<Integer>(); // 实际上不需要存储被雇佣者，只需计数
        int hires = 0;
        if (n == 0) return 0; // 空数组没有雇佣
        if (n == 1) return 1; // 只有一个候选人，必然雇佣一次

        int best = arr[0];
        hires = 1; // 第一个候选人总是被雇佣

        for (int i = 1; i < n; i++) {
            if (arr[i] < best) {
                best = arr[i];
                hires++;
            }
        }
        return hires;
    }

    // 计算阶乘
    public static int factorial(int n) {
        if (n < 0) throw new IllegalArgumentException("Factorial is not defined for negative numbers.");
        if (n == 0 || n == 1) return 1;
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    // 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 List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> list = new ArrayList<>();
        permuteHelper(list, new ArrayList<>(), arr);
        return list;
    }

    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);
            }
        }
    }

    public static void main(String[] args) {
        PermutationHiring ph = new PermutationHiring(); // 实例化类以调用非静态方法
        int n = 6;
        // 生成所有排列
        List<List<Integer>> allPermutations = ph.permute(makeArray(n));

        int hiresTwoCount = 0; // 统计雇佣次数恰好为2的排列数
        int totalPermutations = factorial(n); // 总排列数

        // 遍历每一个独立的排列
        for (List<Integer> permutation : allPermutations) {
            int[] currentPermutationArray = toIntArray(permutation);
            int hires = hireAssistant1(currentPermutationArray, n);
            if (hires == 2) {
                hiresTwoCount++;
            }
        }

        double probability = (double) hiresTwoCount / totalPermutations;
        System.out.println("N = " + n);
        System.out.println("雇佣次数恰好为2的排列数: " + hiresTwoCount);
        System.out.println("总排列数 (n!): " + totalPermutations);
        System.out.println("雇佣次数恰好为2的概率: " + probability);

        // 原始答案中提供的Method 1，用于计算不同的概率（例如，期望雇佣次数的某个变体）
        // 注意：这个方法计算的结果与“雇佣恰好两次”的概率不同。
        // static void methodOne