BaranyaiConstruction.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from fractions import Fraction\n",
    "from math import factorial\n",
    "from operator import itemgetter\n",
    "\n",
    "\n",
    "def binomial(n, k):\n",
    "    return factorial(n) // (factorial(k) * factorial(n - k))\n",
    "\n",
    "\n",
    "def find_path(graph, s, t):\n",
    "    stack = [s]\n",
    "    predecessor = {s: t}\n",
    "    while stack:\n",
    "        v = stack.pop()\n",
    "        for u in graph[v]:\n",
    "            if u not in predecessor:\n",
    "                stack.append(u)\n",
    "                predecessor[u] = v\n",
    "    assert t in predecessor\n",
    "    path = [t]\n",
    "    while path[-1] != s:\n",
    "        path.append(predecessor[path[-1]])\n",
    "    path.reverse()\n",
    "    return path\n",
    "\n",
    "\n",
    "def round_flow(flow):\n",
    "    while True:\n",
    "        capacities = []\n",
    "        for (u, v), x in flow.items():\n",
    "            z = x - x.numerator // x.denominator\n",
    "            if z:\n",
    "                capacities.append(((v, u), z))\n",
    "                capacities.append(((u, v), 1 - z))\n",
    "        if not capacities:\n",
    "            break\n",
    "        (t, s), delta = min(capacities, key=itemgetter(1))\n",
    "        graph = defaultdict(list)\n",
    "        for (v, u), z in capacities:\n",
    "            if (v, u) not in [(s, t), (t, s)]:\n",
    "                graph[v].append(u)\n",
    "        path = find_path(graph, s, t)\n",
    "        for i, v in enumerate(path):\n",
    "            u = path[i - 1]\n",
    "            if (u, v) in flow:\n",
    "                flow[(u, v)] += delta\n",
    "            else:\n",
    "                flow[(v, u)] -= delta\n",
    "\n",
    "\n",
    "def baranyai(n, k):\n",
    "    m, r = divmod(n, k)\n",
    "    assert not r, 'n (%s) must be divisible by k (%s)' % (n, k)\n",
    "\n",
    "    M = binomial(n - 1, k - 1)\n",
    "    partition = [[()] * m for i in range(M)]\n",
    "    for l in range(n):\n",
    "        flow = defaultdict(Fraction)\n",
    "        for i, A_i in enumerate(partition):\n",
    "            for S in A_i:\n",
    "                flow[(i, S)] += Fraction(k - len(S), n - l)\n",
    "        round_flow(flow)\n",
    "        next_partition = []\n",
    "        for i, A_i in enumerate(partition):\n",
    "            next_A_i = []\n",
    "            for S in A_i:\n",
    "                if flow[(i, S)]:\n",
    "                    next_A_i.append(S + (l,))\n",
    "                    flow[(i, S)] -= 1\n",
    "                else:\n",
    "                    next_A_i.append(S)\n",
    "            next_partition.append(next_A_i)\n",
    "        partition = next_partition\n",
    "    assert len(partition) == M\n",
    "    classes = set()\n",
    "    for A in partition:\n",
    "        assert len(A) == m\n",
    "        assert all(len(S) == k for S in A)\n",
    "        assert len({x for S in A for x in S}) == n\n",
    "        classes.update(map(frozenset, A))\n",
    "    assert len(classes) == binomial(n, k)\n",
    "    return partition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = [\n",
    "    [(0, 1, 2, 3), (4, 5, 6, 7)],\n",
    "    [(0, 2, 4, 6), (1, 3, 5, 7)],\n",
    "    [(0, 1, 3, 6), (2, 4, 5, 7)],\n",
    "\n",
    "    \n",
    "    [(0, 5, 6, 7), (1, 2, 3, 4)],\n",
    "    \n",
    "    \n",
    "    [(0, 1, 3, 4), (2, 5, 6, 7)],\n",
    "    [(0, 2, 4, 7), (1, 3, 5, 6)],\n",
    "    [(0, 2, 4, 5), (1, 3, 6, 7)],\n",
    "    [(0, 2, 3, 6), (1, 4, 5, 7)],\n",
    "    [(0, 2, 3, 7), (1, 4, 5, 6)],\n",
    "    [(0, 1, 3, 7), (2, 4, 5, 6)],\n",
    "    [(0, 3, 4, 5), (1, 2, 6, 7)],\n",
    "    [(0, 4, 5, 6), (1, 2, 3, 7)],\n",
    "    [(0, 2, 3, 4), (1, 5, 6, 7)],\n",
    "    [(0, 1, 5, 6), (2, 3, 4, 7)],\n",
    "    [(0, 3, 5, 7), (1, 2, 4, 6)],\n",
    "    [(0, 2, 5, 7), (1, 3, 4, 6)],\n",
    "    [(0, 4, 6, 7), (1, 2, 3, 5)],\n",
    "    [(0, 2, 3, 5), (1, 4, 6, 7)],\n",
    "    [(0, 3, 4, 6), (1, 2, 5, 7)],\n",
    "    [(0, 1, 4, 5), (2, 3, 6, 7)],\n",
    "    [(0, 3, 5, 6), (1, 2, 4, 7)],\n",
    "    [(0, 1, 4, 6), (2, 3, 5, 7)],\n",
    "    [(0, 1, 5, 7), (2, 3, 4, 6)],\n",
    "    [(0, 1, 2, 4), (3, 5, 6, 7)],\n",
    "    [(0, 2, 6, 7), (1, 3, 4, 5)],\n",
    "    [(0, 2, 5, 6), (1, 3, 4, 7)],\n",
    "    [(0, 2, 4, 6), (1, 3, 5, 7)],\n",
    "    [(0, 1, 2, 7), (3, 4, 5, 6)],\n",
    "    [(0, 1, 2, 5), (3, 4, 6, 7)],\n",
    "    [(0, 1, 4, 7), (2, 3, 5, 6)],\n",
    "    [(0, 1, 3, 5), (2, 4, 6, 7)],\n",
    "    [(0, 3, 4, 7), (1, 2, 5, 6)],\n",
    "    [(0, 1, 2, 6), (3, 4, 5, 7)],\n",
    "    [(0, 4, 5, 7), (1, 2, 3, 6)],\n",
    "    [(0, 1, 6, 7), (2, 3, 4, 5)],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(get_good(taken_edges))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_good(taken_edges):\n",
    "    taken_set = set()\n",
    "    for edge in taken_edges:\n",
    "        for group in edge:\n",
    "            i, j, k, l = group\n",
    "            taken_set.add((i, j))\n",
    "            taken_set.add((j, k))\n",
    "            taken_set.add((k, l))\n",
    "\n",
    "    for row in rows:\n",
    "        if row_is_okay(taken_set):\n",
    "            return row\n",
    "    return None\n",
    "                \n",
    "def row_is_okay(taken):\n",
    "    for group in row:\n",
    "        i, j, k, l = group\n",
    "        if (i, j) in taken:\n",
    "            return False\n",
    "        if (j, k) in taken:\n",
    "            return False\n",
    "        if (k, l) in taken:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = r\"\"\"$a^{\\dagger}_7 a^{\\dagger}_5 a_3 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_4 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_5 a_3 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_4 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_6 a_3 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_4 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_4 a_3 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_4 a_3 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_5 a^{\\dagger}_4 a_3 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_0$ \\quad $a^{\\dagger}_4 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_5 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_4 a_3 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_5 a_2 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_4 a_3 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_5 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_4 a_3 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_5 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_4 a_3 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_6 a_1 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_4 a_3 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_4 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_3 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_6 a_2 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_4 a_3 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_4 a_2 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_3 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_4 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_3 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_5 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_4 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_3 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_5 a^{\\dagger}_4 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_3 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_4 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_2$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_7 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_3$ \\\\ \\hline \n",
    "$a^{\\dagger}_5 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_6 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_3$ \\\\ \\hline \n",
    "$a^{\\dagger}_5 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_3$ \\\\ \\hline \n",
    "$a^{\\dagger}_5 a^{\\dagger}_4 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_3 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_4 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_3$ \\\\ \\hline \n",
    "$a^{\\dagger}_4 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_1$ \\\\ \\hline \n",
    "$a^{\\dagger}_3 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_4$ \\\\ \\hline \n",
    "\"\"\".split('hline')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "random.shuffle(rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "$a^{\\dagger}_6 a^{\\dagger}_4 a_3 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_5 a_2 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_4 a_3 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_5 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_4 a_3 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_3 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_4$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_5 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_4 a_3 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_5 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_4 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_3 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_5 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_4 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_3 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_3$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_6 a_2 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_4 a_3 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_6 a_1 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_4 a_3 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_4 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_3 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_5 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_4 a_3 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_5 a_3 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_4 a_2 a_1$ \\\\ \\hline \n",
      "hline$a^{\\dagger}_7 a^{\\dagger}_5 a_3 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_4 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_5 a^{\\dagger}_4 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_3 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_4 a_3 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_5 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_4 a_3$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_0$ \\quad $a^{\\dagger}_4 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_5 a^{\\dagger}_4 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_3 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_4 a_2 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_3 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_3$ \\\\ \\hline \n",
      "$a^{\\dagger}_5 a^{\\dagger}_4 a_3 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_5 a_4 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_3 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_4 a^{\\dagger}_2 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_3$ \\\\ \\hline \n",
      "$a^{\\dagger}_7 a^{\\dagger}_6 a_3 a_0$ \\quad $a^{\\dagger}_5 a^{\\dagger}_4 a_2 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_6 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_5 a_4 a_2$ \\\\ \\hline \n",
      "$a^{\\dagger}_4 a^{\\dagger}_3 a_2 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_1$ \\\\ \\hline \n",
      "$a^{\\dagger}_4 a^{\\dagger}_3 a_1 a_0$ \\quad $a^{\\dagger}_7 a^{\\dagger}_6 a_5 a_2$ \\\\ \\hline"
     ]
    }
   ],
   "source": [
    "for row in rows:\n",
    "    print(row + 'hline', end=\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}