Can we put 7 students in optimal lab groups for 4 weeks? Nope.

LabCombinations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4d8646c2-4fae-4cef-add2-9f5b38951e9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations, permutations\n",
    "from tqdm.notebook import tqdm,trange\n",
    "students = 'ABCDEFG'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f8483998-3582-4807-a873-a172b77fa6ea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5040"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(list(permutations(students,7)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b1e1862-8418-465d-b53b-3a2efd3e18f0",
   "metadata": {},
   "source": [
    "# Obvious code\n",
    "The below is the \"obvious\" brute force code. Unfortunately, it would take 20 days to run.\n",
    "\n",
    "```\n",
    "#for w1 in permutations(students,7):\n",
    "# WLOG\n",
    "w1 = ('A','B','C','D','E','F','G')\n",
    "g11,g12,g13 = w1[:2],w1[2:4],w1[4:]\n",
    "for w2 in tqdm(permutations(students,7)):\n",
    "    g21,g22,g23 = w2[:2],w2[2:4],w2[4:]\n",
    "    for w3 in permutations(students,7):\n",
    "        g31,g32,g33 = w3[:2],w3[2:4],w3[4:]\n",
    "        for w4 in permutations(students,7):\n",
    "            g41,g42,g43 = w4[:2],w4[2:4],w4[4:]\n",
    "            seen = {s:{ss:0 for ss in students if s != ss} for s in students}\n",
    "            for g in g11,g12,g21,g22,g31,g32,g41,g42:\n",
    "                s1,s2 = g\n",
    "                seen[s1][s2] += 1\n",
    "                seen[s2][s1] += 1\n",
    "            for g in g13,g23,g33,g43:\n",
    "                s1,s2,s3 = g\n",
    "                seen[s1][s2] += 1\n",
    "                seen[s1][s3] += 1\n",
    "                seen[s2][s1] += 1\n",
    "                seen[s2][s3] += 1\n",
    "                seen[s3][s1] += 1\n",
    "                seen[s3][s2] += 1\n",
    "            good = True\n",
    "            for s1 in seen:\n",
    "                for s2 in seen[s1]:\n",
    "                    if seen[s1][s2] > 1:\n",
    "                        good = False\n",
    "            if good:\n",
    "                print(w1)\n",
    "                print(w2)\n",
    "                print(w3)\n",
    "                print(w4)\n",
    "                print(seen)\n",
    "```\n",
    "\n",
    "So, let's think a bit. \n",
    "1. No student can be in four groups of three. That would look like the following in weeks 1-4: ABC, ADE, AFG, Axx and there are no students left to fill the xx spots.\n",
    "\n",
    "1. No student can be in three groups of three. If we have them in the above groups ABC, ADE, AFG, there's nobody left for them to group with.\n",
    "\n",
    "1. There has to be at least one student who isn't in two groups of three: we only get 12 total students in the groups of three over the four weeks. However, if every student is in two groups of three, that's 14 people to fit into those 12 spots.\n",
    "\n",
    "1. So, there has to be one student who is in either 0 groups of 3 or 1 group of 3. We can enumerate those quickly enough:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5d742179-706c-4a56-80db-e6ad881db80e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "d273d880ea65437ca47685d67e8fc504",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "0it [00:00, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "donezo\n"
     ]
    }
   ],
   "source": [
    "# Assume student A is in no groups of three. \n",
    "# Then, WLOG, the first week is ABCDEFG and the student is in groups \n",
    "# AB, AC, AD, AE\n",
    "w1 = 'ABCDEFG'\n",
    "g11,g12,g13 = w1[:2],w1[2:4],w1[4:]\n",
    "for _w2 in tqdm(permutations('BDEFG',5)):\n",
    "    w2 = 'AC' + ''.join(_w2)\n",
    "    g21,g22,g23 = w2[:2],w2[2:4],w2[4:]\n",
    "    for _w3 in permutations('BCEFG',5):\n",
    "        w3 = 'AD' + ''.join(_w3)\n",
    "        g31,g32,g33 = w3[:2],w3[2:4],w3[4:]\n",
    "        for _w4 in permutations('BCDFG',5):\n",
    "            w4 = 'AE' + ''.join(_w4)\n",
    "            g41,g42,g43 = w4[:2],w4[2:4],w4[4:]\n",
    "            seen = {s:{ss:0 for ss in students if s != ss} for s in students}\n",
    "            for g in g11,g12,g21,g22,g31,g32,g41,g42:\n",
    "                s1,s2 = g\n",
    "                seen[s1][s2] += 1\n",
    "                seen[s2][s1] += 1\n",
    "            for g in g13,g23,g33,g43:\n",
    "                s1,s2,s3 = g\n",
    "                seen[s1][s2] += 1\n",
    "                seen[s1][s3] += 1\n",
    "                seen[s2][s1] += 1\n",
    "                seen[s2][s3] += 1\n",
    "                seen[s3][s1] += 1\n",
    "                seen[s3][s2] += 1\n",
    "            good = True\n",
    "            for s1 in seen:\n",
    "                for s2 in seen[s1]:\n",
    "                    if seen[s1][s2] > 1:\n",
    "                        good = False\n",
    "            if good:\n",
    "                print(w1)\n",
    "                print(w2)\n",
    "                print(w3)\n",
    "                print(w4)\n",
    "                print(seen)\n",
    "print('donezo')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0847783a-9816-467e-8833-b813e2c48d82",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "6aa069b140054caebfa0dfc47ca8fb1c",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "0it [00:00, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "donezo\n"
     ]
    }
   ],
   "source": [
    "# Assume student A is in one groups of three. \n",
    "# Then, WLOG, the first week is DEFGABC and the student is in groups \n",
    "# ABC, AD, AE, AF\n",
    "w1 = 'DEFGABC'\n",
    "g11,g12,g13 = w1[:2],w1[2:4],w1[4:]\n",
    "for _w2 in tqdm(permutations('BCEFG',5)):\n",
    "    w2 = 'AD' + ''.join(_w2)\n",
    "    g21,g22,g23 = w2[:2],w2[2:4],w2[4:]\n",
    "    for _w3 in permutations('BCDFG',5):\n",
    "        w3 = 'AE' + ''.join(_w3)\n",
    "        g31,g32,g33 = w3[:2],w3[2:4],w3[4:]\n",
    "        for _w4 in permutations('BCDEG',5):\n",
    "            w4 = 'AF' + ''.join(_w4)\n",
    "            g41,g42,g43 = w4[:2],w4[2:4],w4[4:]\n",
    "            seen = {s:{ss:0 for ss in students if s != ss} for s in students}\n",
    "            for g in g11,g12,g21,g22,g31,g32,g41,g42:\n",
    "                s1,s2 = g\n",
    "                seen[s1][s2] += 1\n",
    "                seen[s2][s1] += 1\n",
    "            for g in g13,g23,g33,g43:\n",
    "                s1,s2,s3 = g\n",
    "                seen[s1][s2] += 1\n",
    "                seen[s1][s3] += 1\n",
    "                seen[s2][s1] += 1\n",
    "                seen[s2][s3] += 1\n",
    "                seen[s3][s1] += 1\n",
    "                seen[s3][s2] += 1\n",
    "            good = True\n",
    "            for s1 in seen:\n",
    "                for s2 in seen[s1]:\n",
    "                    if seen[s1][s2] > 1:\n",
    "                        good = False\n",
    "            if good:\n",
    "                print(w1)\n",
    "                print(w2)\n",
    "                print(w3)\n",
    "                print(w4)\n",
    "                print(seen)\n",
    "print('donezo.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2eba2460-0ba2-468f-a7e0-97e5aa5d190a",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}