java - 有没有更有效的方法来随机化然后将 3 个数据子集均匀分布组合？

Question

我为我本地的写作小组制作了一个简单的应用程序，该应用程序“随机”将小组分成两半，以确定他们是在橙色房间还是蓝色房间。我的方法有效，人数从不超过 20 人，但我知道这是一种蛮力方法，不适用于非常大的人数。

我试图为这种方法留下好的评论，但如果有任何混淆，我会很乐意更新问题。

// Splits people into three groups, anchors, people with pages, and people without pages. Then it evenly(as possible) distributes people with and without pages into two groups.
public ArrayList<Person> shuffle() {

    ArrayList<Person> haveNoPages = new ArrayList<>(); // people who don't have pages, including anchors.
    ArrayList<Person> anchorList = new ArrayList<>(); // people who are Anchors.

    // Split people who don't have pages
    for(int i = 0; i < people.size(); i++){
        if(people.get(i).getPages().equals("0")){
            haveNoPages.add(people.get(i));
            people.remove(i);
            i--;
        }
    }

    // holds the anchors temporarily
    for (int i = 0; i < people.size(); i++) {
        if (people.get(i).isBlueA() || people.get(i).isOrangeA()) {
            anchorList.add(people.get(i));
            people.remove(i);
            i--;
        }
    }

    // Randomize the lists to "draw" names.
    Collections.shuffle(people);
    Collections.shuffle(haveNoPages);

    // Alternate group placement until the list is empty.
    for (int i = 0; i < people.size(); i++) {
        if (i % 2 == 0) {
            people.get(i).setGroup("Orange");
        } else {
            people.get(i).setGroup("Blue");
        }
    }

    // Alternate group placement until the list is empty.
    for (int i = 0; i < haveNoPages.size(); i++) {
        if (i % 2 == 0) {
            haveNoPages.get(i).setGroup("Orange");
        } else {
            haveNoPages.get(i).setGroup("Blue");
        }
    }

    // Recombine the list and return it.
    people.addAll(anchorList);
    people.addAll(haveNoPages);
    anchorList.clear();
    haveNoPages.clear();
    return people;
}

我最初的想法是将所有内容组合到一个 for 循环中，然后使用 boolean 值在每种类型的人之间交替显示蓝色和橙色组。示例:

   for (int i = 0; i < people.size(); i++) {
        if (i % 2 == 0 && !people.get(i).isBlueA() && !people.get(i).isOrangeA()) {
            people.get(i).setGroup("Orange");
        } else if (!people.get(i).isBlueA() && !people.get(i).isOrangeA()) {
            people.get(i).setGroup("Blue");
        }
    }

此解决方案的问题是我不知道如何确保没有页面的人被集中在一个无用的组中。我需要每个“类型”均匀分布。

排序不当的组示例:

蓝色组

• 凯蒂 - 0 页
• 巴特 - 0 页
• Alice 页面(主播)- 0 页

橙色集团

• Alex - 5 页

• 玛丽莎 - 6 页

• John(主播)- 2 页

希望这可以清楚地说明我为什么要对组进行排序并将组分别分配给每个子集。我需要确保每个组中有页面的人数是偶数，这样一组人就不会胡思乱想了。

我最终想更进一步，找出一种方法来考虑每个人带来的页数，但这是以后要担心的事情。

Answer 1

前几天我也在想类似的事情。关于如何使用带有计数器的“ transient ”列表。

基本上，使用 3 个独立的计数器来保持 {Anchor, >0, =0} 的连续计数。当您遍历人员列表时，确定类型，使用模数检查计数器以确定蓝色或橙色，然后递增。

// Evenly(as possible) distributes people with and without pages into two groups.
public ArrayList<Person> shuffle() {

    int anAnchorCount = 0; // useless?
    int hasPagesCount = 0;
    int emptyHanded = 0;

    // Split people who don't have pages
    for(Person p : people){
        if (p.isBlueA() || p.isOrangeA()){
            // skip ?? ... Already assigned?
            anAnchorCount++;
        }
        else if(p.getPages().equals("0")){
            p.setGroup((emptyHanded++ % 2 == 0) ? "Orange" : "Blue");
        }
        else
            p.setGroup((hasPagesCount++ % 2 == 0) ? "Orange" : "Blue");
    }

    return people;
}

如果可行，那么它就是 O(N)。

---

稍后，您可以使用桶根据页数平均分配。您的 if/elseif/else 树只会检查范围。