每周组分配算法和参与者奇数 [英] Weekly group assignment algorithm with odd number of participants

问题描述

有一个循环的解决了问题，我问过。它的伟大工程与偶数的人，但没有任何的建议，似乎一旦你实现该算法并尝试出来工作。我已经尝试了许多变化和（分组最后一个有一大堆其他人，第二组最后一组，不同的组合，2和4的最后一个底排的，我认为这会给我最最佳的解决方案，但仍然有许多重复）。有人建议可以很长的路要走，或证明，不能有没有2人一起工作不止一次这样我就可以停止尝试，使其工作的解决方案。如果你想在算法中的java我可以发布，所以你可以用它玩了。

There is a round-robin solution to a question I asked before. It works great with even number of people but none of the suggestions seem to work once you implement the algorithm and try them out. I've tried many variations and (grouping the last one with a whole bunch of other people, the second group the last group, different combinations, the 2 and 4 to the last of the bottom row, I thought this would give me the most optimal solution but still many duplicates). Can someone suggest a way to go, or a proof that there cannot be a solution without 2 people working together more than once so I can stop trying to make it work. If you want the algorithm in java I can post it so you can play with it.

感谢。

推荐答案

14周的23名学生在2组和一个3足够要求不高的本地搜索能够找到一个解决方案。

14 weeks for 23 students in groups of 2 and one 3 is sufficiently undemanding that local search is able to find a solution.

 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 code，使得它。

Here's the Java code that made it.

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

这篇关于每周组分配算法和参与者奇数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！