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);
    }
}