深入理解Java中全排列的生成与逐个处理

public static int hireAssistant1(int[] arr, int n) {
    // 假设arr[0]是第一个面试者，直接聘用
    int best = arr[0];
    int hiresCount = 1; // 初始招聘人数为1

    // 从第二个面试者开始遍历
    for (int i = 1; i < n; i++) {
        // 如果当前面试者比目前最佳的还要好（值越小表示越好）
        if (arr[i] < best) {
            best = arr[i]; // 更新最佳候选人
            hiresCount++;  // 招聘人数增加
        }
    }
    return hiresCount;
}

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors; // 稍后可能需要

public class PermutationProcessor {

    // 辅助方法：生成初始数组，例如 [1, 2, 3, ..., 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 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); // 回溯：移除最后一个元素，尝试其他路径
            }
        }
    }

    // 辅助方法：将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;
    }
}

// 原始的错误方法，用于对比说明
// 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<Integer> list, int n) {
//     int size = factorial(n);
//     int [] arr = new int [list.size()];
//     arr = toIntArray(list); // 这里的arr是所有排列拼接而成的一个大数组

//     double sum = 0;
//     for (int i = 0; i < size; i++) {
//         int hires = hireAssistant1(arr, n); // 每次都传入同一个大数组
//         if (hires == 2)
//             sum = sum + 1;
//     }
//     System.out.println("Method 3: s/n! = " + sum /size);
// }

public class PermutationProcessor {
    // ... (makeArray, hireAssistant1, permute, permuteHelper, toIntArray methods as above) ...

    public static int factorial(int n) {
        if (n == 0 || n == 1) return 1;
        return n * factorial(n - 1);
    }

    /**
     * 正确处理所有排列的方法。
     * 遍历每个独立的排列，并对其进行分析。
     *
     * @param allPermutations 包含所有独立排列的列表 (List<List<Integer>>)
     * @param n 原始数组的长度
     */
    public static void processAllPermutations(List<List<Integer>> allPermutations, int n) {
        double sumOfSuccessfulOutcomes = 0;
        // 总排列数就是allPermutations列表的大小
        int totalPermutations = allPermutations.size();

        // 确保totalPermutations与n的阶乘一致
        if (totalPermutations != factorial(n)) {
            System.err.println("警告: 生成的排列数与阶乘不匹配！实际: " + totalPermutations + ", 预期: " + factorial(n));
        }

        // 逐个遍历每个独立的排列
        for (List<Integer> currentPermutationList : allPermutations) {
            // 将当前的List<Integer>排列转换为int[]，以便传递给hireAssistant1
            int[] currentPermutationArray = toIntArray(currentPermutationList);

            // 对当前的单个排列进行分析
            int hires = hireAssistant1(currentPermutationArray, n);

            // 如果满足特定条件（例如，招聘次数恰好为2）
            if (hires == 2) {
                sumOfSuccessfulOutcomes++;
            }
        }

        // 计算并输出概率
        System.out.println("方法3 (修正版): 招聘次数为2的概率 = " + sumOfSuccessfulOutcomes / totalPermutations);
    }

    public static void main(String[] args) {
        PermutationProcessor processor = new PermutationProcessor();
        int n = 6; // 例如，n=6表示有6个候选人

        // 1. 生成初始数组 [1, 2, ..., n]
        int[] initialArray = makeArray(n);

        // 2. 生成所有排列 (List<List<Integer>>)
        List<List<Integer>> allPermutations = processor.permute(initialArray);

        System.out.println("N = " + n);

        // 3. 调用修正后的方法，逐个处理每个排列
        processAllPermutations(allPermutations, n);

        // 理论值（作为对比，来源于原始问题中的Method 1）
        // 招聘助理问题中，招聘次数为2的概率理论值是 (H_n - 1) / n
        // 其中 H_n = 1 + 1/2 + 1/3 + ... + 1/n 是调和级数
        // 对于 n=6, H_6 = 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 = 2.45
        // 理论概率 = (2.45 - 1) / 6 = 1.45 / 6 = 0.24166...
        // 原始问题中Method 1的输出是 0.38055555555555554，这可能对应的是招聘次数的期望值，
        // 或者计算的是招聘次数大于等于2的概率。这里我们继续使用原始问题提供的理论值作为对比。
        // 根据原始答案提供的Method 1代码，它计算的是 sum(1/(i-1)) / n
        // 当n=6时，sum = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 = 1 + 0.5 + 0.333 + 0.25 + 0.2 = 2.283
        // sum / n = 2.283 / 6 = 0.38055555555555554
        // 这与招聘次数为2的概率并非直接对应，但可以作为验证我们计算的概率是否合理的一个参考。
        // 实际的“恰好招聘两次”的概率是 (n-1)/n! * (n-2)! = (n-1)/n
        // 或者是 (n-1) * (n-2)! / n!
        // 对于恰好招聘两次的概率，通常是 1/n * sum_{i=2 to n} 1/(i-1)
        // 实际上，招聘助理问题中，恰好招聘两次的概率是 (H_{n-1}) / n
        // H_5 = 1 + 1/2 + 1/3 + 1/4 + 1/5 = 2.28333...
        // 概率 = H_5 / 6 = 2.28333... / 6 = 0.380555...
        // 这与原始问题中Method 1的输出完全一致。
        // 因此，我们计算的 `hires == 2` 的概率，应该与 `methodOneSum1` 的结果相符。
        methodOneSum1(n);
    }

    // 原始问题中提供的理论计算方法（Method 1）
    static void methodOneSum1(int n) {
        double sum = 0;
        for (double i = 2; i <= n; i++)
            sum += 1 / ((double) (i - 1));
        System.out.println("方法1 (理论值): n = " + (sum / n));
    }
}