java - 描述这种随机但公平地调用学生的程序/算法的正确术语是什么？

Question

作为一名老师，我想设计一个程序来帮助我随机点名学生。随机数生成器还不够好，因为少数学生可能很少通过这种方式被叫到。我也不想要随机队列生成器，因为这样我刚刚点名的学生就可以放心地停止注意力，直到我点名她的其他同学为止。

理想情况下，我可以使用某种程序在随机队列中调用学生 1-10，但偶尔会偏离该队列来调用以前调用的学生。这将确保所有学生都能合理地频繁地被拜访，而且最近一次被拜访的学生也不会因为我在一段时间内不会再次拜访他而沾沾自喜。例如，我需要这样的随机输出:5, 7, 2, 1, 1, 9, 10, 5, 3, 6, 8, 9, 4...

描述此类程序的正确术语是什么？我不一定要寻找如何编写此类代码的答案，尽管这也很好。

Answer 1

您可以从调用池中选择学生，每个学生都会被代表一定的次数。为了消除调用不均匀性，对于被选择次数较少的学生，该池中的出现次数较高，对于被选择次数较多的学生，该池中的出现次数较少，但永远不会小于 1，以便让任何学生有机会在任何时间，无论他的“通话记录”如何。最初，每个学生在池中只被代表一次。下面的实现允许热包含/排除学生。生成器由 nextCall() 方法提供。

import java.util.*;
import java.security.SecureRandom;

public class StudentCalls {
    private final Set<String> students = new HashSet<>();
    private final List<String> callPool = new ArrayList<>();
    private static final Random rand = new SecureRandom();

    public void addStudent(String name) {
        int studentCount = students.size();
        if (!students.add(name))
            throw new IllegalArgumentException(name + " has already been added");
        int newStudentCalls = studentCount == 0 ? 1 // bootstrap
                // average of already present students', never less than 1
                : (int) Math.round((double) callPool.size() / studentCount);
        for (int i = 1; i <= newStudentCalls; i++)
            callPool.add(name);
    }

    public void addStudents(String... names) {
        for (String name : names)
            addStudent(name);
    }

    public void removeStudent(String name) {
        if (!students.remove(name))
            throw new IllegalArgumentException("Unknown student: " + name);
        callPool.removeAll(Collections.singleton(name));
    }

    public String nextCall() {
        int poolSize = callPool.size();
        if (poolSize == 0)
            throw new IllegalStateException("No students to choose from");
        int poolIndex = rand.nextInt(poolSize);
        /* Below is optimized equivalent of this code:
        String selectedStudent = callPool.remove(poolIndex);
        if (!callPool.contains(selectedStudent))
            callPool.addAll(students);
        */
        String selectedStudent = callPool.get(poolIndex);
        if (Collections.frequency(callPool, selectedStudent) > 1) {
            String lastInPool = callPool.remove(--poolSize);
            if (poolIndex < poolSize)
                callPool.set(poolIndex, lastInPool);
        } else
            for (String student : students)
                if (!student.equals(selectedStudent))
                    callPool.add(student);
        return selectedStudent;
    }

    public void conductClasses(int numberOfCalls) {
        for (int i = 0; i < numberOfCalls; i++)
            System.out.println(nextCall());
        System.out.println();
    }

    public static void main(String[] args) {
        StudentCalls sc = new StudentCalls();
        sc.addStudents("Josh", "Cooper", "Rachel", "Buckley", "Matt",
                "Lucy", "Kristin", "Kyle", "Kelly");
        sc.conductClasses(20);
        sc.removeStudent("Matt");
        sc.conductClasses(15);
        sc.addStudent("Cliff");
        sc.conductClasses(25);
    }
}