计算学生考试时间的贪婪算法

Question

我决定把堆栈溢出上的一个问题作为一种乐趣来解决。(我不会把它张贴在那里，因为他们应该自己尝试)

其基本思想是为一组学生找到使用最少插槽数的考试时间表。学生选择不同的模块，每个模块应该能够参加他们的所有考试，没有任何冲突。

以下是输入的数据：

John取模A，G，F，C 取模E，F，B，A Clare取模D，A，G，E

这应该会导致

时隙1:模块D和F 时隙2:模块B和G 时隙3:模块C和E 时隙4:模块A

(我认为时隙的名称/顺序是任意的，不确定这是否是原意)

我有三个类，它们基本上都是数据持有者：Module、TimeSlot和Student，还有一个Main类进行实际计算。

代码是用Java 8编写的，我在几个地方使用了流和lambda。我确实考虑过在var中使用Java10，但它在许多地方似乎并没有增加多少价值。

如有任何建议，敬请见谅。我真的不关心表演。在我看来，可读性和可维护性是最重要的代码质量指标。特别是，我几乎肯定可以使用流重写modulesToStudents。我不知道它是否更易读。

请注意，我已经知道，因为这是一个贪婪的实现，它不会在所有情况下都给出最佳的解决方案。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.stream.Collectors;

class Module
{
    private final char name;

    Module(final char name)
    {
        this.name = name;
    }

    @Override
    public boolean equals(final Object o)
    {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        final Module module = (Module) o;
        return name == module.name;
    }

    @Override
    public int hashCode()
    {
        return Objects.hash(name);
    }

    @Override
    public String toString()
    {
        return "Module " + name;
    }
}

class TimeSlot
{
    private final int id;
    private final List<Module> modules = new ArrayList<>();

    TimeSlot(final int id)
    {
        this.id = id;
    }

    void addModule(final Module module)
    {
        modules.add(module);
    }

    boolean containsAny(final List<Module> modules)
    {
        return modules.stream().anyMatch(this.modules::contains);
    }

    @Override
    public String toString()
    {
        return "TimeSlot{modules=" + modules + ", id=" + id + '}';
    }
}

class Student
{
    private final String name;
    private final List<Module> modules;

    Student(final String name, final List<Module> modules)
    {
        this.name = name;
        this.modules = modules;
    }

    List<Module> getModules()
    {
        return modules;
    }

    @Override
    public String toString()
    {
        return name;
    }
}

public class Main
{
    public static void main(final String... args)
    {
        System.out.println(calculateSchedule(data()));
    }

    private static List<Student> data()
    {
        return Arrays.asList(
            new Student("John",  Arrays.asList(new Module('A'), new Module('G'), new Module('F'), new Module('C'))),
            new Student("Ben",   Arrays.asList(new Module('E'), new Module('F'), new Module('B'), new Module('A'))),
            new Student("Clare", Arrays.asList(new Module('D'), new Module('A'), new Module('G'), new Module('E')))
        );
    }

    private static String calculateSchedule(final List<Student> students)
    {
        final List<TimeSlot> slots = new ArrayList<>();
        final Map<Module, List<Student>> modulesToStudentsByPopularity = sortLargestFirst(
            modulesToStudents(students)
        );
        for (final Map.Entry<Module, List<Student>> entry : modulesToStudentsByPopularity.entrySet())
        {
            final Module module = entry.getKey();
            final List<Student> modulesStudents = entry.getValue();
            boolean isSlotAvailable = false;
            for (final TimeSlot slot : slots)
            {
                isSlotAvailable = isSlotAvailable(slot, modulesStudents);
                if (isSlotAvailable)
                {
                    slot.addModule(module);
                    break;
                }
            }
            if (!isSlotAvailable)
            {
                final TimeSlot newSlot = new TimeSlot(slots.size());
                newSlot.addModule(module);
                slots.add(newSlot);
            }
        }
        return slots.toString();
    }

    private static Map<Module, List<Student>> modulesToStudents(final List<Student> students)
    {
        final Map<Module, List<Student>> modulesToStudents = new HashMap<>();
        for (final Student student : students)
        {
            for (final Module module : student.getModules())
            {
                modulesToStudents.putIfAbsent(module, new ArrayList<>());
                modulesToStudents.get(module).add(student);
            }
        }
        return modulesToStudents;
    }

    private static <K, V> Map<K, List<V>> sortLargestFirst(final Map<K, List<V>> input)
    {
        return input.entrySet().stream()
            .sorted((a, b) -> b.getValue().size() - a.getValue().size()) // Sort by size, descending
            .collect(
                Collectors.toMap(
                    Map.Entry::getKey,
                    Map.Entry::getValue,
                    (a, b) -> { throw new AssertionError(); },
                    LinkedHashMap::new
                )
            );
    }

    private static boolean isSlotAvailable(final TimeSlot slot, final List<Student> students)
    {
       return students.stream().noneMatch(student -> slot.containsAny(student.getModules()));
    }
}

Answer 1

一些小贴士：

• Java惯例规定开头的大括号应该在同一条线上。
• 在块中只有单行语句/表达式时，请始终尝试使用大括号。它防止了由于格式化而产生的潜在错误，并且使以后在不担心太多的情况下更改或添加代码变得更容易。
• 也许让你的课上完课。您可以选择在等于方法中使用instanceof (这也消除了对null检查的需要)。有关更多信息，请参见例如vs getClass的实例
• Object.hash将不必要地自动设置字符。只需返回(int) name (将值作为无符号16位int)，或者为了更清晰起见，Character.hashCode(name)。
• return modules.stream().anyMatch(this.modules::contains);，您不应该在列表中像这样使用should。每个包含将迭代列表以找到值。使用Set代替，例如HashSet。当然，为了保持相同的顺序(或使用有序集)，您可能需要将列表作为状态。
• 对于Student类，您将直接将模块引用的值分配给字段。这意味着，在此传递列表之外的任何更改也将在此处可见。使用一个安全的副本，以防止任何下流。
• 有点像这样，您正在返回对列表的直接引用。用户可以通过修改这个列表来改变学生的内部状态。例如使用Collections.unmodifiableList(modules)。因为无法更新学生状态，所以可以缓存此值。
• 非常小，但我个人认为这一点更清楚:布尔isSlotAvailable = false；对于(最终的TimeSlot插槽:插槽){ if ( isSlotAvailable (时隙，modulesStudents)) {slot.addModule(模块)；isSlotAvailable=真；中断；}
• 我会让calculateSchedule返回时隙，而不是字符串。让客户决定如何处理它。
• 您可以将isSlotAvailable编写为:返回students.stream() .map(Student::getModules) .noneMatch(槽：：students.stream：.map)；
• 我试图为modulesToStudents创建一个Java8版本。我目前的解决方案是对学生使用额外的方法。不过，我并不是很喜欢。我想用一个groupingBy来尝试它，但是我不知道如何使用list属性。我将添加我的另一个解决方案以供参考:返回students.stream() .flatMap(学生-> student.getModules().stream()) .distinct() .collect( toMap( identity() )，模块-> students.stream().filter(student -> .filter))