algorithm - 具有奇数参与者的每周小组分配算法

Question

我之前提出的问题有一个循环解决方案。它适用于偶数人，但一旦您实施算法并尝试它们，这些建议似乎都不起作用。我尝试了很多变化并且（将最后一个与一大堆其他人分组，第二组最后一组，不同的组合，2和4到最后一行的最后一个，我认为这会给我最多最佳解决方案，但仍有许多重复项）。有人可以建议一种方法，或者证明如果没有 2 个人多次合作就不可能有解决方案，这样我就可以停止尝试让它发挥作用。如果您想要java中的算法，我可以发布它，以便您可以使用它。

谢谢。

Answer 1

23 名学生 2 人一组，1 人 3 人一组，为期 14 周，这对本地搜索能够找到解决方案的要求并不高。

 18  1 11|  3  4|  5  7|  9  6|  0 17|  2 12| 10 19| 15 16| 21  8| 14 20| 13 22|
  6 13 18| 17  4|  5  0| 20  1| 12 11| 10  9|  2 14| 15  7|  3  8| 19 16| 21 22|
 21 17  7| 19 22|  3  1|  2  8|  0 10| 14 12| 13 11|  6 16|  5 15| 18 20|  9  4|
  8  1 13| 18  2|  6 11| 20  0| 12 10| 14 15|  5 17|  9 21|  4 19|  3 22| 16  7|
  0  4 16| 17 20| 21  3|  7 18| 13 19|  1  5|  9 11| 15  2| 14  8| 10  6| 12 22|
 12  1 17| 15  4|  8  6| 16 18|  9  0| 11 22|  5 14|  3  2|  7 13| 19 20| 21 10|
  4  1 22| 12  8| 15  6|  7  0|  9 17| 11  3| 13  2|  5 18| 10 14| 19 21| 20 16|
  0  1  6| 13 21| 15 12| 17  8| 20 10| 11  4|  3 14|  5 16|  7  2| 19  9| 18 22|
 13 16  3|  2  9| 11 20|  6 17| 22 10|  5 12|  0 14| 15  1|  8 18| 19  7| 21  4|
 14  1  7|  2  4|  5  9|  3  6|  8 10| 13 12| 21  0| 17 16| 22 20| 19 18| 11 15|
 14 18 21| 12  4|  5  6|  2 19|  8 20|  1  9| 13  0| 11 16| 17 15|  3 10|  7 22|
 21  6  2|  3 20|  5 13| 16  8| 18 17|  0 12| 22 14| 10  1|  9 15|  7  4| 11 19|
  0 11  2|  6  4| 16 14|  7  8| 17 10|  1 19| 13  9|  3 18| 21 12| 20  5| 15 22|
  1 16  2| 14 13|  3  7|  8  4| 11 10|  9 12|  0 18| 15 19| 17 22|  6 20| 21  5|

这是制作它的Java代码。

public class Schedule {
  private final int weekCount;
  private final int groupCount;
  private final int personCount;
  private final int groupFirstSlot[];
  private final int weekSlotPerson[][];

  public Schedule(int weekCount, int groupCount, int personCount) {
    this.weekCount = weekCount;
    this.groupCount = groupCount;
    this.personCount = personCount;
    int remainingPersonCount = personCount;
    this.groupFirstSlot = new int[groupCount + 1];
    for (int remainingGroupCount = groupCount;
         remainingGroupCount > 0;
         remainingGroupCount--) {
      groupFirstSlot[remainingGroupCount] = remainingPersonCount;
      remainingPersonCount -= remainingPersonCount / remainingGroupCount;
    }
    this.weekSlotPerson = new int[weekCount][personCount];
    for (int week = 0; week < weekCount; week++) {
      for (int person = 0; person < personCount; person++) {
        weekSlotPerson[week][person] = person;
      }
    }
  }

  public int getWeekCount() {
    return weekCount;
  }

  public int getGroupCount() {
    return groupCount;
  }

  public int getPersonCount() {
    return personCount;
  }

  public int getGroupFirstSlot(int group) {
    return groupFirstSlot[group];
  }

  public int getWeekSlotPerson(int week, int slot) {
    return weekSlotPerson[week][slot];
  }

  public void swapWeekSlotPerson(int week, int slotOne, int slotTwo) {
    int temp = weekSlotPerson[week][slotOne];
    weekSlotPerson[week][slotOne] = weekSlotPerson[week][slotTwo];
    weekSlotPerson[week][slotTwo] = temp;
  }

  public int getConflictCount() {
    int pairCount[][] = new int[personCount][personCount];
    for (int week = 0; week < weekCount; week++) {
      for (int group = 0; group < groupCount; group++) {
        for (int slotOne = groupFirstSlot[group];
             slotOne < groupFirstSlot[group + 1];
             slotOne++) {
          int personOne = weekSlotPerson[week][slotOne];
          for (int slotTwo = groupFirstSlot[group];
               slotTwo < groupFirstSlot[group + 1];
               slotTwo++) {
            int personTwo = weekSlotPerson[week][slotTwo];
            pairCount[personOne][personTwo]++;
          }
        }
      }
    }
    int conflictCount = 0;
    for (int personOne = 0; personOne < personCount; personOne++) {
      for (int personTwo = personOne + 1;
           personTwo < personCount;
           personTwo++) {
        int pc = pairCount[personOne][personTwo];
        conflictCount += pc * (pc - 1) / 2;
      }
    }
    return conflictCount;
  }

  public static void main(String[] args) {
    Schedule sched = new Schedule(14, 11, 23);
    java.util.Random rand = new java.util.Random();
    int oldCc = sched.getConflictCount();
    while (oldCc > 0) {
      int week = rand.nextInt(sched.getWeekCount());
      int slotOne = rand.nextInt(sched.getPersonCount());
      int slotTwo = rand.nextInt(sched.getPersonCount());
      sched.swapWeekSlotPerson(week, slotOne, slotTwo);
      int newCc = sched.getConflictCount();
      if (newCc < oldCc) {
        oldCc = newCc;
      } else {
        sched.swapWeekSlotPerson(week, slotOne, slotTwo);
      }
    }
    for (int week = 0; week < sched.getWeekCount(); week++) {
      for (int group = 0; group < sched.getGroupCount(); group++) {
        for (int slot = sched.getGroupFirstSlot(group);
             slot < sched.getGroupFirstSlot(group + 1);
             slot++) {
          System.out.printf("%3d",
                            sched.getWeekSlotPerson(week, slot));
        }
        System.out.print('|');
      }
      System.out.println();
    }
  }
}