如何将n!个排列逐个传入hireAssistant1以计算雇佣两次的概率

你的核心问题是错误地将所有排列扁平化传递给methodThreePerm，导致无法单独处理每个排列。以下是修正后的代码和关键改动说明：

关键问题分析 #

• permute方法已经正确生成了所有排列的List<List<Integer>>，但你用listToList把它扁平化成了一个超大数组，丢失了单个排列的边界。
• methodThreePerm里循环调用hireAssistant1时，始终传入同一个大数组，完全没有遍历不同排列。

修正步骤 #

1. 修改methodThreePerm的参数：直接接收List<List<Integer>>类型的排列集合，而非扁平化列表。
2. 遍历每个排列：在methodThreePerm中逐个取出每个排列，转换为int数组后传入hireAssistant1。
3. 简化hireAssistant1逻辑：不需要用ArrayList存储雇佣记录，直接计数即可提升效率。
4. 修正main方法：不再调用listToList扁平化，直接传递原始排列集合。

修正后的完整代码 #

import java.util.ArrayList;
import java.util.List;

public class Assignment8 {

    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) {
        if (n == 0) return 0;
        int hireCount = 1;
        int best = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] < best) {
                best = arr[i];
                hireCount++;
            }
        }
        return hireCount;
    }

    // 修改参数为排列集合，逐个处理每个排列
    public static void methodThreePerm(List<List<Integer>> permutations, int n) {
        int totalPerms = factorial(n);
        int count = 0;
        for (List<Integer> perm : permutations) {
            // 将单个排列转为int数组
            int[] arr = perm.stream().mapToInt(Integer::intValue).toArray();
            int hires = hireAssistant1(arr, n);
            if (hires == 2) {
                count++;
            }
        }
        double probability = (double) count / totalPerms;
        System.out.println("Method 3: s/n! = " + probability);
    }

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

    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) {
        Assignment8 pa = new Assignment8();
        int n = 6;
        List<List<Integer>> permutations = pa.permute(makeArray(n));
        System.out.println("N = 6");
        methodThreePerm(permutations, n);
    }
}

关键改动说明 #

• 参数调整：methodThreePerm现在接收List<List<Integer>>，直接遍历每个子列表（单个排列）。
• 排列转数组：用stream().mapToInt(Integer::intValue).toArray()简化单个排列到int数组的转换，原有的toIntArray和listToList方法可直接删除。
• 雇佣计数优化：hireAssistant1去掉了ArrayList，直接用变量计数，减少不必要的内存开销。
• main方法修正：不再扁平化排列集合，直接传递给methodThreePerm。

内容的提问来源于stack exchange，提问作者Scels12