深入理解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));     } }