Проблема стабильного брака - код не возвращает ни одного партнера / выбора для кого-либо

Question

Я думаю, проблема в переменной int w1.Я не могу напрямую ссылаться на это в списках, поэтому я не могу утверждать, предпочитает ли эта конкретная женщина этого мужчину (м) нынешнему мужчине (м1).

Я пробовал много разных способов решения этой проблемы.проблема, но все они приводят к одному и тому же выводу: не было найдено ни одного совпадения, и все остались одни, и я не могу понять, где я ошибся.

    public static void makeMatches(List<Person> list1, List<Person> list2) {
        // set each person to be free
        for (Person m : list1) {
            m.erasePartner();
        }

        for (Person w: list2) {
            w.erasePartner();
        }


        for (Person m : list1) {
            for (Person w : list2) {
                // find man with nonempty preference list that is free      
                while (m.hasChoices() && !m.hasPartner()) {
                    // first woman on man's list
                    int w1 = m.getFirstChoice();

                    for (Person m1 : list1) {
                        // if chosen woman is free, set her to be man's partner
                        if (!w.hasPartner()) {m.setPartner(w1);

                        // if chosen woman has partner, set her to be free and engage her and man
                        } else if (w.hasPartner()) {
                            if (w.getPartnerRank() < w.getChoices().indexOf(m)) {
                            w.erasePartner();
                            m.setPartner(w1);
                            }
                        }
                    }
                }
            }
        }
    }

import java.util.*;

public class Person {
    public static final int NOBODY = -1;

    private String name;
    private List<Integer> preferences;
    private List<Integer> oldPreferences;
    private int partner;

    public Person(String name) {
        this.name = name;
        preferences = new ArrayList<Integer>();
        oldPreferences = new ArrayList<Integer>();
        erasePartner();
    }

    public void erasePartner() {
        partner = NOBODY;
    }

    public boolean hasPartner() {
        return partner != NOBODY;
    }

    public int getPartner() {
        return partner;
    }

    public void setPartner(int partner) {
        this.partner = partner;
    }

    public String getName() {
        return name;
    }

    public boolean hasChoices() {
        return !preferences.isEmpty();
    }

    public int getFirstChoice() {
        return preferences.get(0);
    }

    public void addChoice(int person) {
        preferences.add(person);
        oldPreferences.add(person);
    }

    public List<Integer> getChoices() {
        return preferences;
    }

    public int getPartnerRank() {
        return oldPreferences.indexOf(partner) + 1;
    }
}

тестовый файл: Man 0:3 0 1 2 Мужчина 1: 1 2 0 3 Мужчина 2: 1 3 2 0 Мужчина 3: 2 0 3 1 КОНЕЦ Женщина 0: 3 0 2 1 Женщина 1: 0 2 1 3 Женщина 2: 0 1 2 3 Женщина 3:3 0 2 1 КОНЕЦ

вывод: Матчи для мужчин

Имя Выбор Партнер

Мужчина 0 - никто Мужчина 1 - никто Мужчина 2 - никто Мужчина 3 -никто не означает выбор = NaN

совпадения для женщин

имя выбор партнера

женщина 0 - никто женщина 1 - никто женщина 2 - никто женщина 3 - никто не имеет значенияchoice = NaN Результаты должны объединять каждого мужчину с женщиной с использованием алгоритма Гейла-Шепли.

Answer 1

Несколько вопросов здесь.Во-первых, я не уверен, почему у вас есть двойная структура цикла в makeMatches.Условие Гейл-Шепли состоит в том, чтобы перебирать список мужчин, пока существует хотя бы один человек, который все еще не помолвлен, но у него еще есть кто-то, кто может предложить то, что он еще не сделал.Поэтому я удалил бы двойной цикл for и сохранил цикл while, но вместо этого изменил условие внутри, чтобы вызвать метод, возможно, вызвать его stillNotEngaged, который возвращает индекс кого-то в списке мужчин, которые не заняты и все еще имеют выбори -1 или NOBODY, если они все заняты или у них не осталось выбора.

public static void makeMatches(List<Person> list1, List<Person> list2) {
    // code from before that set each partner free
    int m1 = stillNotEngaged(list1, list2);
    while (m1 != -1) { // at least one not engaged or has choices
        // to be filled in later in this answer...
        m1 = stillNotEngaged(list1, list2);
    }
}

public static int stillNotEngaged(List<Person> men, List<Person> women) {
    for (int i = 0; i < men.size(); i++) {
        if (!men.get(i).hasPartner() && men.get(i).hasChoices()) {
            return i;
        }
    }
    return NOBODY;
}

Затем обязательно установите партнера ОБА мужчину и женщину.Раньше вы только устанавливали партнера только для мужчины.И если развод происходит, не просто очистите партнера женщины, очистите ОБА партнеров мужчины и женщины.Или, чтобы облегчить ситуацию, в случае развода, просто очистите партнера старого мужа и установите партнеров нового мужа и жены.Наконец, я не совсем уверен, почему вы используете oldPreferences и почему вы добавляете 1 к рангу в методе getPartnerRank, почему бы просто не использовать индекс партнера в preferences, как это так,

public int getPartnerRank() {
    return preferences.indexOf(partner);
}

Еще одна вещь, которую следует иметь в виду, заключается в том, что, когда мужчина предлагает, вы должны исключить эту женщину из предпочтений мужчины, иначе цикл будет бесконечным.Гэри-Шепли предлагает мужчинам предлагать каждой женщине не более одного раза, поэтому, возможно, стоит подумать о создании метода под названием removeChoice, например,

public void removeChoice(int w) {
    preferences.remove(preferences.indexOf(w));
}

В общем, если вы внедрите новые изменения, которые я только что упомянул, ваш makeMatches метод теперь должен выглядеть так:

 public static void makeMatches(List<Person> list1, List<Person> list2) {
    // set each person to be free
    for (Person m : list1) {
        m.erasePartner();
    }

    for (Person w: list2) {
        w.erasePartner();
    }

    int m1 = stillNotEngaged(list1, list2);
    while (m1 != -1) { // at least one not engaged and has choices
        int w1 = m.getFirstChoice();
        Person m = list1.get(m1);
        Person w = list2.get(w1);
        if (!w.hasPartner()) {
            m.setPartner(w1);
            w.setPartner(m1);
        }
        // if chosen woman has partner, set her to be free and engage her and man
        else if (w.hasPartner()) {
            // assuming preferences are in descending order, so index 0 is the first priority choice
            if (w.getPartnerRank() > w.getChoices().indexOf(m1)) {
                list1.get(w.getPartner()).erasePartner();
                w.setPartner(m1);
                m.setPartner(w1);
            }
        }
        m.removeChoice(w1);
        m1 = stillNotEngaged(list1, list2);
    }
}