本文旨在探讨在Java中如何有效地生成所有可能的排列，并对每个独立的排列进行逐个处理。我们将通过一个经典的“雇佣助理”问题作为案例，详细阐述如何修正常见的将所有排列扁平化处理的错误，确保每个排列都能作为独立的输入传递给处理函数，从而实现正确的统计与分析，最终计算出特定条件下的概率。
理解问题：排列生成与单次处理的需求
在许多算法问题中，我们可能需要对一个数据集的所有排列进行分析。例如，在“雇佣助理”问题中，我们假设助理的排名是随机的，需要计算在特定雇佣策略下，雇佣了特定数量助理的概率。
给定的代码中，hireAssistant1 方法负责模拟雇佣过程并返回雇佣的助理数量。它接收一个 int[] 数组作为输入，代表一组助理的排名序列。
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(); }
另一方面，permute 方法通过回溯算法生成给定数组的所有可能排列，并以 List> 的形式返回：
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); } } }
核心问题出现在 methodThreePerm 方法中。原始实现试图将 permute 生成的所有排列 (List>) 通过 listToList 方法扁平化为一个 List
// 原始的错误实现片段 List<List<Integer>> p = pa.permute(makeArray(n)); List<Integer> list = listToList(p); // 错误：将所有排列扁平化 int [] arr = toIntArray(list); // 错误：将扁平化的List转为数组 // ... 然后将这个大数组传递给 hireAssistant1 int hires = hireAssistant1(arr, n); // 错误：hireAssistant1期望的是单个排列
解决方案：逐个处理排列
为了正确地对每个排列进行分析，我们需要遍历 permute 方法返回的 List>，将每个内部的 List
立即学习“Java免费学习笔记（深入）”；
以下是修正后的 methodThreePerm 方法及其在 main 方法中的调用示例：
import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; // 确保导入 public class Assignment8 { // 假设类名为Assignment8，与原代码一致 // 辅助方法：生成初始数组，例如 [1, 2, ..., 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 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 static int factorial(int n) { if (n == 0) return 1; int result = 1; for (int i = 1; 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); } } } // 修正后的 methodThreePerm 方法 public static void methodThreePerm(List<List<Integer>> permutations, int n) { // 参数类型改为 List<List<Integer>> int totalPermutations = factorial(n); // 总排列数 double sumOfHiresTwo = 0; // 统计雇佣两次的排列数 // 遍历每一个独立的排列 for (List<Integer> permutation : permutations) { int[] currentPermutationArray = toIntArray(permutation); // 将当前排列转换为 int[] int hires = hireAssistant1(currentPermutationArray, n); // 将单个排列传递给 hireAssistant1 if (hires == 2) { sumOfHiresTwo++; } } System.out.println("Method 3: s/n! = " + sumOfHiresTwo / totalPermutations); } // 辅助方法：methodOneSum1 (用于对比验证) 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)); } // 主方法示例 public static void main(String[] args) { Assignment8 pa = new Assignment8(); int n = 6; int[] initialArray = makeArray(n); // 例如：[1, 2, 3, 4, 5, 6] List<List<Integer>> allPermutations = pa.permute(initialArray); // 生成所有排列 System.out.println("N = " + n); methodThreePerm(allPermutations, n); // 调用修正后的方法 // 验证与比较：methodOneSum1 methodOneSum1(n); } }
通过上述修改，methodThreePerm 现在正确地迭代了 allPermutations 列表中的每一个 List
核心辅助方法解析
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
喜欢就支持一下吧
相关推荐
