group_generator.ipynb

group_generator.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "group_generator.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "[View in Colaboratory](https://colab.research.google.com/gist/tovrstra/0b5520e50211ae9c5d53d11c32e3c4d3/group_generator.ipynb)"
      ]
    },
    {
      "metadata": {
        "id": "L58tI4wy3fAu",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**Description:** The code below generates a schedule for students who have to work in different \"corners\" of a room in  consecutive time slots, subject to the requirements that (i) they visit each corner once and (ii) that the number of times they work with the same other students in different corners is minimal. Furthermore, the code assumes that you want to have approximately the same number of students in each corner during all time slots. Finally, and this is obvious, the algorithm also assumes that you want all students to be present in one of the corners at all times. (Idle hands ...)\n",
        "\n",
        "Parameters that can be changed: \n",
        "\n",
        "- `ncorner`: the number of corners you create\n",
        "\n",
        "- `nstudent`: the number of students in your class\n",
        "\n",
        "The output consists of three sections: (i) a permutation of corners that each student has to follow with students in the original order, (ii) the same list but with a randomized ordering of the students and (iii) the students present in each corner for each time slot. The list of permutations is built up in batches, which is just an algorithmic detail. Each batch is assigned an \"Overlap\" number, which is the number of times a student will encounter another student more than once in any of the time slots. This algorithm tries to minimize overlap.\n",
        "\n",
        "**Hints:** When `nstudent` is not a multiple of `ncorner`, not all corners will count the same number of students at all times, but they will be distributed as evenly as possible. If the number of students is more than the factorial of the number of corners, it is unavoidable that some students will go through all corners following exactly the same permutation.\n",
        "\n",
        "If you need to make such a schedule multiple times for the same group, you may want to assign each student number in this algorithm randomly to students in your class.\n",
        "\n",
        "**Algorithmic details:** The algorithm divides the students into batches, with the same size as the number of corners. Each batch contains all cyclic permutations of the schedule of the first student in the batch. This guarantees an even distribution of students over corners at all times. Whenever a new batch is created, the algorithm looks for a starting permutation that has minimal overlap with students visiting the same corners in the same time slots."
      ]
    },
    {
      "metadata": {
        "id": "YT6ET7V0tV-r",
        "colab_type": "code",
        "outputId": "6f1ce88a-076b-4d68-c213-b6678a87b40a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1205
        }
      },
      "cell_type": "code",
      "source": [
        "from itertools import permutations\n",
        "from random import shuffle\n",
        "\n",
        "\n",
        "def cycle(p):\n",
        "    \"\"\"Return a cyclic permutation of the given permutation.\"\"\"\n",
        "    return (p[-1],) + p[:-1]\n",
        "\n",
        "\n",
        "def select_least_overlap(valid_ps, used_ps):\n",
        "    \"\"\"Select from a set of valid permutations one with minimal overlap with\n",
        "       previously used permutations\n",
        "    \"\"\"\n",
        "    best = None\n",
        "    for candidate in valid_ps:\n",
        "        if candidate[0] != 0:\n",
        "           continue\n",
        "        # overlap is the number of times a student works with another student\n",
        "        # more than once.\n",
        "        overlap = 0\n",
        "        for used in used_ps:\n",
        "            shared = sum(i==j for i, j in zip(candidate, used))\n",
        "            if shared > 1:\n",
        "                overlap += shared - 1\n",
        "        # make sure the best (and first) candidate from the list of valid\n",
        "        # permutations is selected.\n",
        "        if best is None or overlap < best[0] or \\\n",
        "           (overlap == best[0] and candidate < best[1]):\n",
        "            best = overlap, candidate\n",
        "    return best\n",
        "\n",
        "\n",
        "def generate_permutations(ncorner, nstudent):\n",
        "    \"\"\"Generate permutations of corners for a given number of students with\n",
        "       minimal overlap.\n",
        "    \"\"\"\n",
        "    print(\"Student list in the original order...\")\n",
        "    used_ps = []\n",
        "    irep = 0\n",
        "    # When there are more students than the factorial of the number of corners,\n",
        "    # the outermost loop is iterated more than once.\n",
        "    while True:\n",
        "        valid_ps = set(permutations(range(ncorner)))\n",
        "        nbatch = len(valid_ps)//ncorner\n",
        "        for ibatch in range(nbatch):\n",
        "            overlap, current = select_least_overlap(valid_ps, used_ps)\n",
        "            print(\"Iteration {:d}, Batch {:d}, Overlap {:d}\".format(\n",
        "                irep, ibatch, overlap))\n",
        "            for icorner in range(ncorner):\n",
        "                valid_ps.discard(current)\n",
        "                used_ps.append(current)\n",
        "                print(\"   Student {:d} visits corners {}\".format(\n",
        "                    len(used_ps), current))\n",
        "                if len(used_ps) == nstudent:\n",
        "                    return used_ps\n",
        "                current = cycle(current)\n",
        "        irep += 1\n",
        "\n",
        "        \n",
        "def print_student_schedule(used_ps):\n",
        "    print()\n",
        "    print(\"Student list in randomized order...\")\n",
        "    for istudent, p in enumerate(used_ps):\n",
        "        print(\"Student {:d} visits corners {}\".format(istudent + 1, p))\n",
        "\n",
        "\n",
        "def print_time_slots(used_ps):\n",
        "    \"\"\"Print the composition of each corner in each time slot.\"\"\"\n",
        "    if len(used_ps) == 0:\n",
        "        return\n",
        "    ncorner = len(used_ps[0])\n",
        "    print()\n",
        "    print(\"Composition of each corner for each time slot...\")\n",
        "    for islot in range(ncorner):\n",
        "        print(\"Time slot {:d}\".format(islot))\n",
        "        for icorner in range(ncorner):\n",
        "            students = [istudent+1 for istudent, p in enumerate(used_ps)\n",
        "                        if p[islot] == icorner]\n",
        "            print(\"   Corner {:d} contains students {}\".format(\n",
        "                icorner, students))\n",
        "\n",
        "\n",
        "used_ps = generate_permutations(ncorner=4, nstudent=19)\n",
        "shuffle(used_ps)  # This randomizes the students\n",
        "print_student_schedule(used_ps)\n",
        "print_time_slots(used_ps)"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Student list in the original order...\n",
            "Iteration 0, Batch 0, Overlap 0\n",
            "   Student 1 visits corners (0, 1, 2, 3)\n",
            "   Student 2 visits corners (3, 0, 1, 2)\n",
            "   Student 3 visits corners (2, 3, 0, 1)\n",
            "   Student 4 visits corners (1, 2, 3, 0)\n",
            "Iteration 0, Batch 1, Overlap 1\n",
            "   Student 5 visits corners (0, 1, 3, 2)\n",
            "   Student 6 visits corners (2, 0, 1, 3)\n",
            "   Student 7 visits corners (3, 2, 0, 1)\n",
            "   Student 8 visits corners (1, 3, 2, 0)\n",
            "Iteration 0, Batch 2, Overlap 2\n",
            "   Student 9 visits corners (0, 2, 1, 3)\n",
            "   Student 10 visits corners (3, 0, 2, 1)\n",
            "   Student 11 visits corners (1, 3, 0, 2)\n",
            "   Student 12 visits corners (2, 1, 3, 0)\n",
            "Iteration 0, Batch 3, Overlap 4\n",
            "   Student 13 visits corners (0, 2, 3, 1)\n",
            "   Student 14 visits corners (1, 0, 2, 3)\n",
            "   Student 15 visits corners (3, 1, 0, 2)\n",
            "   Student 16 visits corners (2, 3, 1, 0)\n",
            "Iteration 0, Batch 4, Overlap 5\n",
            "   Student 17 visits corners (0, 3, 1, 2)\n",
            "   Student 18 visits corners (2, 0, 3, 1)\n",
            "   Student 19 visits corners (1, 2, 0, 3)\n",
            "\n",
            "Student list in randomized order...\n",
            "Student 1 visits corners (1, 0, 2, 3)\n",
            "Student 2 visits corners (0, 2, 1, 3)\n",
            "Student 3 visits corners (0, 3, 1, 2)\n",
            "Student 4 visits corners (3, 0, 1, 2)\n",
            "Student 5 visits corners (1, 2, 3, 0)\n",
            "Student 6 visits corners (2, 0, 3, 1)\n",
            "Student 7 visits corners (0, 2, 3, 1)\n",
            "Student 8 visits corners (2, 3, 0, 1)\n",
            "Student 9 visits corners (2, 3, 1, 0)\n",
            "Student 10 visits corners (3, 1, 0, 2)\n",
            "Student 11 visits corners (3, 0, 2, 1)\n",
            "Student 12 visits corners (1, 3, 2, 0)\n",
            "Student 13 visits corners (0, 1, 3, 2)\n",
            "Student 14 visits corners (1, 3, 0, 2)\n",
            "Student 15 visits corners (0, 1, 2, 3)\n",
            "Student 16 visits corners (3, 2, 0, 1)\n",
            "Student 17 visits corners (2, 0, 1, 3)\n",
            "Student 18 visits corners (1, 2, 0, 3)\n",
            "Student 19 visits corners (2, 1, 3, 0)\n",
            "\n",
            "Composition of each corner for each time slot...\n",
            "Time slot 0\n",
            "   Corner 0 contains students [2, 3, 7, 13, 15]\n",
            "   Corner 1 contains students [1, 5, 12, 14, 18]\n",
            "   Corner 2 contains students [6, 8, 9, 17, 19]\n",
            "   Corner 3 contains students [4, 10, 11, 16]\n",
            "Time slot 1\n",
            "   Corner 0 contains students [1, 4, 6, 11, 17]\n",
            "   Corner 1 contains students [10, 13, 15, 19]\n",
            "   Corner 2 contains students [2, 5, 7, 16, 18]\n",
            "   Corner 3 contains students [3, 8, 9, 12, 14]\n",
            "Time slot 2\n",
            "   Corner 0 contains students [8, 10, 14, 16, 18]\n",
            "   Corner 1 contains students [2, 3, 4, 9, 17]\n",
            "   Corner 2 contains students [1, 11, 12, 15]\n",
            "   Corner 3 contains students [5, 6, 7, 13, 19]\n",
            "Time slot 3\n",
            "   Corner 0 contains students [5, 9, 12, 19]\n",
            "   Corner 1 contains students [6, 7, 8, 11, 16]\n",
            "   Corner 2 contains students [3, 4, 10, 13, 14]\n",
            "   Corner 3 contains students [1, 2, 15, 17, 18]\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}