java - 稳定的婚姻问题 - 代码不为任何人返回合作伙伴/选择

Question

我认为问题出在 int w1 变量上。我无法直接通过列表引用该信息，因此我无法说明该特定女性是否更喜欢那个男性 (m) 而不是当前的男性 (m1)。

我尝试了许多不同的方法来解决这个问题，但所有这些方法都会导致相同的输出:没有匹配，每个人都保持单例，我不知道我哪里出了问题。

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

测试文件:男子 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结束

输出:男子比赛

命名选择合作伙伴

Man 0——没有人男人1——没有人男人2——没有人男人3——没有人平均选择 = NaN

女子比赛

命名选择合作伙伴

女人 0 -- 没有人女人1——没人女人2——没人女人3——没人平均选择 = NaN结果应该使用 Gale-Shapley 算法将每个男人与一个女人配对。

Answer 1

这里有几个问题。首先，我不确定为什么在 makeMatches 中有这个双 for 循环结构。 Gale-Shapley 的条件是迭代男人列表，只要存在至少一个尚未订婚的男人，但仍然有一个他尚未求婚的人。因此，我会删除双 for 循环并保留 while 循环，而是更改内部条件以调用一个方法，也许将其称为 stillNotEngged ，该方法返回男性列表中不属于男性的某人的索引参与并且仍然有选择，如果他们都参与或没有任何选择，则为 -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;
}

然后，请确保设置BOTH男人和女人的伴侣。之前你只是设定了那个男人的伴侣。如果离婚确实发生，不仅要清除女方的伴侣，还要清除男性和女方的伴侣。或者更简单一点，离婚的情况下，只需清除旧丈夫的伴侣，并设置新夫妻的伴侣即可。最后，我不太确定为什么要使用 oldPreferences ，也不知道为什么要在 getPartnerRank 方法中的排名中添加 1，为什么不只使用索引首选项中的合作伙伴如下所示，

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

还要记住的另一件事是，当男人求婚时，你应该将该女人从男人的偏好中删除，否则循环将是无限的。 Gary-Shapley 规定男性最多向每个女性求婚一次，因此也许可以考虑创建一个名为 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);
    }
}