{ "cells": [ { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "test = \"\"\"\n", " 1 2\n", " 3 4\n", " 5 6\n", "\"\"\"" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import itertools" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "smaller = np.array([[int(x) for x in line.strip().split()] for line in test.split('\\n') if line != ''])" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "v = 7\n", "l = len(smaller)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[2, 3, 1],\n", " [4, 5, 1],\n", " [6, 7, 1],\n", " [1, 3, 2],\n", " [4, 5, 2],\n", " [6, 7, 2],\n", " [1, 2, 3],\n", " [4, 5, 3],\n", " [6, 7, 3],\n", " [1, 2, 4],\n", " [3, 5, 4],\n", " [6, 7, 4],\n", " [1, 2, 5],\n", " [3, 4, 5],\n", " [6, 7, 5],\n", " [1, 2, 6],\n", " [3, 4, 6],\n", " [5, 7, 6],\n", " [1, 2, 7],\n", " [3, 4, 7],\n", " [5, 6, 7]])" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rows = []\n", "for i in range(1, v+1):\n", " rows.append ( np.hstack( (smaller + (smaller >= i), [[i]]*l) ) )\n", "rows = np.concatenate(rows)\n", "# rows = np.sort(rows, axis=1)\n", "# rows = np.unique(rows, axis=0)\n", "rows" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{1, 2} 7\n", "{1, 3} 3\n", "{1, 4} 2\n", "{1, 5} 2\n", "{1, 6} 2\n", "{1, 7} 2\n", "{2, 3} 3\n", "{2, 4} 2\n", "{2, 5} 2\n", "{2, 6} 2\n", "{2, 7} 2\n", "{3, 4} 5\n", "{3, 5} 3\n", "{3, 6} 2\n", "{3, 7} 2\n", "{4, 5} 5\n", "{4, 6} 2\n", "{4, 7} 2\n", "{5, 6} 3\n", "{5, 7} 3\n", "{6, 7} 7\n" ] } ], "source": [ "k = 2\n", "sets = [set(i) for i in list(itertools.combinations(range(1, v+1), k))]\n", "for p in sets:\n", " print(p, sum([len(p.intersection(r)) == k for r in rows]) )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is too many. Gotta try a different strategy. Maybe more symmetric?" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "extended = np.hstack( (smaller, [[v]]*l) )" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[0, 1, 2],\n", " [0, 3, 4],\n", " [0, 5, 6],\n", " [1, 2, 3],\n", " [1, 4, 5],\n", " [0, 1, 6],\n", " [2, 3, 4],\n", " [2, 5, 6],\n", " [0, 1, 2],\n", " [3, 4, 5],\n", " [0, 3, 6],\n", " [1, 2, 3],\n", " [4, 5, 6],\n", " [0, 1, 4],\n", " [2, 3, 4],\n", " [0, 5, 6],\n", " [1, 2, 5],\n", " [3, 4, 5],\n", " [0, 1, 6],\n", " [2, 3, 6],\n", " [4, 5, 6]])" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rows = []\n", "for i in range(v):\n", " rows.append( (extended + i) % v)\n", "rows = np.concatenate(rows)\n", "rows = np.sort(rows, axis=1)\n", "# rows = np.unique(rows, axis=0)\n", "rows" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{0, 1} 5\n", "{0, 2} 2\n", "{0, 3} 2\n", "{0, 4} 2\n", "{0, 5} 2\n", "{0, 6} 5\n", "{1, 2} 5\n", "{1, 3} 2\n", "{1, 4} 2\n", "{1, 5} 2\n", "{1, 6} 2\n", "{2, 3} 5\n", "{2, 4} 2\n", "{2, 5} 2\n", "{2, 6} 2\n", "{3, 4} 5\n", "{3, 5} 2\n", "{3, 6} 2\n", "{4, 5} 5\n", "{4, 6} 2\n", "{5, 6} 5\n", "CPU times: user 10.3 ms, sys: 268 µs, total: 10.6 ms\n", "Wall time: 7.53 ms\n" ] } ], "source": [ "%%time\n", "k = 2\n", "sets = [set(i) for i in list(itertools.combinations(range(v), k))]\n", "for p in sets:\n", " print(p, sum([len(p.intersection(r)) == k for r in rows]) )" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{0, 1} 5\n", "{0, 2} 2\n", "{0, 3} 2\n", "{0, 4} 2\n", "{0, 5} 2\n", "{0, 6} 5\n", "{1, 2} 5\n", "{1, 3} 2\n", "{1, 4} 2\n", "{1, 5} 2\n", "{1, 6} 2\n", "{2, 3} 5\n", "{2, 4} 2\n", "{2, 5} 2\n", "{2, 6} 2\n", "{3, 4} 5\n", "{3, 5} 2\n", "{3, 6} 2\n", "{4, 5} 5\n", "{4, 6} 2\n", "{5, 6} 5\n", "CPU times: user 15.5 ms, sys: 554 µs, total: 16.1 ms\n", "Wall time: 11.4 ms\n" ] } ], "source": [ "%%time\n", "k = 2\n", "sets = [set(i) for i in list(itertools.combinations(range(v), k))]\n", "for p in sets:\n", " print(p, sum([p.issubset(r) for r in rows]) )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ok, so this overshoots, but it does find a cover.\n", "\n", "# trying 5,6,48" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "# https://ljcr.dmgordon.org/cover/LARGE/C_48_6_5.html\n", "with open('s-5-6-48.txt') as f:\n", " s_5_6_48 = f.read()\n", "f.close()\n", "s_5_6_48 = s_5_6_48.split('\\n')\n", "assert len(s_5_6_48) == 285384" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "bigger = np.array([[int(x) for x in line.strip().split()] for line in s_5_6_48 if line != ''])" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "285384" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(bigger)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "v = 49\n", "l = len(bigger)" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "extended = np.hstack( (bigger, [[v]]*l) )" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "rows = []\n", "for i in range(v):\n", " rows.append( (extended + i) % v)\n", "rows = np.concatenate(rows)\n", "rows = np.sort(rows, axis=1)\n", "rows = np.unique(rows, axis=0)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1997688" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l*7" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "11894701" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(rows)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[ 0, 1, 2, ..., 4, 5, 21],\n", " [ 0, 1, 2, ..., 4, 5, 27],\n", " [ 0, 1, 2, ..., 4, 6, 22],\n", " ...,\n", " [40, 41, 42, ..., 45, 46, 48],\n", " [40, 42, 43, ..., 45, 46, 48],\n", " [40, 42, 43, ..., 46, 47, 48]])" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rows" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "# k = 2\n", "# sets = [set(i) for i in list(itertools.combinations(range(v), k))]\n", "# for p in sets:\n", "# print(p, sum([len(p.intersection(r)) == k for r in rows]) )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## trying something different" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "what about just simplifying the covering?" ] }, { "cell_type": "code", "execution_count": 764, "metadata": {}, "outputs": [], "source": [ "# https://ljcr.dmgordon.org/show_cover.php?v=21&k=7&t=6\n", "v = 22\n", "with open('c-22-5-4.txt') as f:\n", " data = f.read()\n", "f.close()\n", "data = data.split('\\n')\n", "# assert len(data) == 9218" ] }, { "cell_type": "code", "execution_count": 765, "metadata": {}, "outputs": [], "source": [ "cover = np.array([[int(x) for x in line.strip().split()] for line in data if line != ''])" ] }, { "cell_type": "code", "execution_count": 766, "metadata": {}, "outputs": [], "source": [ "from collections import Counter" ] }, { "cell_type": "code", "execution_count": 767, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7315\n", "0\n", "200\n", "400\n", "600\n", "800\n", "1000\n", "1200\n", "1400\n", "1600\n", "1800\n", "2000\n", "2200\n", "2400\n", "2600\n", "2800\n", "3000\n", "3200\n", "3400\n", "3600\n", "3800\n", "4000\n", "4200\n", "4400\n", "4600\n", "4800\n", "5000\n", "5200\n", "5400\n", "5600\n", "5800\n", "6000\n", "6200\n", "6400\n", "6600\n", "6800\n", "7000\n", "7200\n", "CPU times: user 14.5 s, sys: 3.98 ms, total: 14.5 s\n", "Wall time: 14.5 s\n" ] } ], "source": [ "%%time\n", "c = Counter()\n", "d = {}\n", "k = 4\n", "sets = [set(i) for i in list(itertools.combinations(range(1, v+1), k))]\n", "print(len(sets))\n", "for idx, p in enumerate(sets):\n", " if idx % 200 == 0:\n", " print(idx)\n", " ct = sum([p.issubset(r) for r in cover])\n", " c[ct] += 1\n", " if ct not in d:\n", " d[ct] = []\n", " d[ct].append(p)\n", "# print(p, ct)" ] }, { "cell_type": "code", "execution_count": 768, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": 769, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 769, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAASYklEQVR4nO3dX4yd9X3n8fcnODQtbWoTBmTZ1pqqVra0UoAdGSqkqBt3jSFRzEWQiHaDhVx5L9wq0a7UJb2xCo1Eb5ou0hbJwu6abhrqJUVYKQodOYm6vYAwBEoCDrJLKR6Z4mltSFPUVKTfvZifmwPMnzOe8Rzbv/dLOnqe5/v8zpnv74LPefw7zzmkqpAk9eF9o25AkrRyDH1J6oihL0kdMfQlqSOGviR1ZNWoG5jPFVdcURs3bhx1G5J0QXnmmWf+vqrGZjt3Xof+xo0bmZycHHUbknRBSfK3c51zeUeSOmLoS1JHFgz9JB9O8tzA4/tJPpfk8iQTSY627Zo2PknuT3IsyfNJrh94rR1t/NEkO87lxCRJ77Vg6FfVS1V1bVVdC/wH4C3gUeBu4HBVbQIOt2OAW4BN7bELeAAgyeXAHuAGYDOw58wbhSRpZSx2eWcL8NdV9bfAduBAqx8Abmv724GHasaTwOoka4GbgYmqOlVVp4EJYNuSZyBJGtpiQ/8O4Mtt/6qqeg2gba9s9XXA8YHnTLXaXPV3SLIryWSSyenp6UW2J0maz9Chn+RS4JPA/11o6Cy1mqf+zkLV3qoar6rxsbFZbzOVJJ2lxVzp3wJ8u6peb8evt2Ub2vZkq08BGwaetx44MU9dkrRCFhP6n+bHSzsAh4Azd+DsAB4bqN/Z7uK5EXizLf88AWxNsqZ9gLu11SRJK2Sob+Qm+SngPwH/daB8H3AwyU7gVeD2Vn8cuBU4xsydPncBVNWpJPcCT7dx91TVqSXPYB4b7/6zc/nyy+aV+z4+6hYkdWKo0K+qt4APvav2D8zczfPusQXsnuN19gP7F9+mJGk5+I1cSeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4MFfpJVid5JMn3khxJ8stJLk8ykeRo265pY5Pk/iTHkjyf5PqB19nRxh9NsuNcTUqSNLthr/T/J/C1qvr3wEeAI8DdwOGq2gQcbscAtwCb2mMX8ABAksuBPcANwGZgz5k3CknSylgw9JN8EPgosA+gqv6lqt4AtgMH2rADwG1tfzvwUM14ElidZC1wMzBRVaeq6jQwAWxb1tlIkuY1zJX+zwHTwB8meTbJg0kuA66qqtcA2vbKNn4dcHzg+VOtNlf9HZLsSjKZZHJ6enrRE5IkzW2Y0F8FXA88UFXXAf/Ej5dyZpNZajVP/Z2Fqr1VNV5V42NjY0O0J0ka1jChPwVMVdVT7fgRZt4EXm/LNrTtyYHxGwaevx44MU9dkrRCFgz9qvo74HiSD7fSFuBF4BBw5g6cHcBjbf8QcGe7i+dG4M22/PMEsDXJmvYB7tZWkyStkFVDjvsN4EtJLgVeBu5i5g3jYJKdwKvA7W3s48CtwDHgrTaWqjqV5F7g6Tbunqo6tSyzkCQNZajQr6rngPFZTm2ZZWwBu+d4nf3A/sU0KElaPn4jV5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0JakjQ4V+kleSfCfJc0kmW+3yJBNJjrbtmlZPkvuTHEvyfJLrB15nRxt/NMmOczMlSdJcFnOl/x+r6tqqGm/HdwOHq2oTcLgdA9wCbGqPXcADMPMmAewBbgA2A3vOvFFIklbGUpZ3tgMH2v4B4LaB+kM140lgdZK1wM3ARFWdqqrTwASwbQl/X5K0SMOGfgF/nuSZJLta7aqqeg2gba9s9XXA8YHnTrXaXPV3SLIryWSSyenp6eFnIkla0Kohx91UVSeSXAlMJPnePGMzS63mqb+zULUX2AswPj7+nvOSpLM31JV+VZ1o25PAo8ysyb/elm1o25Nt+BSwYeDp64ET89QlSStkwdBPclmSnzmzD2wFvgscAs7cgbMDeKztHwLubHfx3Ai82ZZ/ngC2JlnTPsDd2mqSpBUyzPLOVcCjSc6M/+Oq+lqSp4GDSXYCrwK3t/GPA7cCx4C3gLsAqupUknuBp9u4e6rq1LLNRJK0oAVDv6peBj4yS/0fgC2z1AvYPcdr7Qf2L75NSdJy8Bu5ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0ZOvSTXJLk2SRfbcdXJ3kqydEkf5Lk0lb/iXZ8rJ3fOPAan2/1l5LcvNyTkSTNbzFX+p8Fjgwc/y7wxaraBJwGdrb6TuB0Vf088MU2jiTXAHcAvwhsA/4gySVLa1+StBhDhX6S9cDHgQfbcYCPAY+0IQeA29r+9nZMO7+ljd8OPFxVP6yqvwGOAZuXYxKSpOEMe6X/+8BvAv/ajj8EvFFVb7fjKWBd218HHAdo599s4/+tPstz/k2SXUkmk0xOT08vYiqSpIUsGPpJPgGcrKpnBsuzDK0Fzs33nB8XqvZW1XhVjY+NjS3UniRpEVYNMeYm4JNJbgU+AHyQmSv/1UlWtav59cCJNn4K2ABMJVkF/CxwaqB+xuBzJEkrYMEr/ar6fFWtr6qNzHwQ+/Wq+s/AN4BPtWE7gMfa/qF2TDv/9aqqVr+j3d1zNbAJ+NayzUSStKBhrvTn8j+Ah5P8DvAssK/V9wF/lOQYM1f4dwBU1QtJDgIvAm8Du6vqR0v4+5KkRVpU6FfVN4Fvtv2XmeXum6r6Z+D2OZ7/BeALi21SkrQ8/EauJHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcWDP0kH0jyrSR/leSFJL/d6lcneSrJ0SR/kuTSVv+Jdnysnd848Fqfb/WXktx8riYlSZrdMFf6PwQ+VlUfAa4FtiW5Efhd4ItVtQk4Dexs43cCp6vq54EvtnEkuQa4A/hFYBvwB0kuWc7JSJLmt2Do14wftMP3t0cBHwMeafUDwG1tf3s7pp3fkiSt/nBV/bCq/gY4BmxelllIkoYy1Jp+kkuSPAecBCaAvwbeqKq325ApYF3bXwccB2jn3wQ+NFif5TmDf2tXkskkk9PT04ufkSRpTkOFflX9qKquBdYzc3X+C7MNa9vMcW6u+rv/1t6qGq+q8bGxsWHakyQNaVF371TVG8A3gRuB1UlWtVPrgRNtfwrYANDO/yxwarA+y3MkSStgmLt3xpKsbvs/CfwqcAT4BvCpNmwH8FjbP9SOaee/XlXV6ne0u3uuBjYB31quiUiSFrZq4SGsBQ60O23eBxysqq8meRF4OMnvAM8C+9r4fcAfJTnGzBX+HQBV9UKSg8CLwNvA7qr60fJOR5I0nwVDv6qeB66bpf4ys9x9U1X/DNw+x2t9AfjC4tuUJC0Hv5ErSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1JEFQz/JhiTfSHIkyQtJPtvqlyeZSHK0bde0epLcn+RYkueTXD/wWjva+KNJdpy7aUmSZjPMlf7bwH+vql8AbgR2J7kGuBs4XFWbgMPtGOAWYFN77AIegJk3CWAPcAOwGdhz5o1CkrQyFgz9qnqtqr7d9v8ROAKsA7YDB9qwA8BtbX878FDNeBJYnWQtcDMwUVWnquo0MAFsW9bZSJLmtag1/SQbgeuAp4Crquo1mHljAK5sw9YBxweeNtVqc9Xf/Td2JZlMMjk9Pb2Y9iRJCxg69JP8NPAV4HNV9f35hs5Sq3nq7yxU7a2q8aoaHxsbG7Y9SdIQhgr9JO9nJvC/VFV/2sqvt2Ub2vZkq08BGwaevh44MU9dkrRChrl7J8A+4EhV/d7AqUPAmTtwdgCPDdTvbHfx3Ai82ZZ/ngC2JlnTPsDd2mqSpBWyaogxNwGfAb6T5LlW+y3gPuBgkp3Aq8Dt7dzjwK3AMeAt4C6AqjqV5F7g6Tbunqo6tSyzkCQNZcHQr6q/ZPb1eIAts4wvYPccr7Uf2L+YBiVJy8dv5EpSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1ZMHQT7I/yckk3x2oXZ5kIsnRtl3T6klyf5JjSZ5Pcv3Ac3a08UeT7Dg305EkzWeYK/3/DWx7V+1u4HBVbQIOt2OAW4BN7bELeABm3iSAPcANwGZgz5k3CknSylkw9KvqL4BT7ypvBw60/QPAbQP1h2rGk8DqJGuBm4GJqjpVVaeBCd77RiJJOsfOdk3/qqp6DaBtr2z1dcDxgXFTrTZXXZK0gpb7g9zMUqt56u99gWRXkskkk9PT08vanCT17mxD//W2bEPbnmz1KWDDwLj1wIl56u9RVXuraryqxsfGxs6yPUnSbM429A8BZ+7A2QE8NlC/s93FcyPwZlv+eQLYmmRN+wB3a6tJklbQqoUGJPky8CvAFUmmmLkL5z7gYJKdwKvA7W3448CtwDHgLeAugKo6leRe4Ok27p6qeveHw5Kkc2zB0K+qT89xasssYwvYPcfr7Af2L6o7SdKy8hu5ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SerIgj+4pvPHxrv/bNQtDOWV+z4+6hYkzcErfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6siKh36SbUleSnIsyd0r/fclqWcrGvpJLgH+F3ALcA3w6STXrGQPktSzlf7tnc3Asap6GSDJw8B24MUV7kPSEC7G33u6GOe0GKmqc/LCs/6x5FPAtqr6tXb8GeCGqvr1gTG7gF3t8MPASyvW4HCuAP5+1E0sI+dz/rvY5nSxzQfOvzn9u6oam+3ESl/pZ5baO951qmovsHdl2lm8JJNVNT7qPpaL8zn/XWxzutjmAxfWnFb6g9wpYMPA8XrgxAr3IEndWunQfxrYlOTqJJcCdwCHVrgHSerWii7vVNXbSX4deAK4BNhfVS+sZA/L4LxdejpLzuf8d7HN6WKbD1xAc1rRD3IlSaPlN3IlqSOGviR1xNAfQpL9SU4m+e6oe1kuSTYk+UaSI0leSPLZUfe0FEk+kORbSf6qzee3R93TckhySZJnk3x11L0shySvJPlOkueSTI66n6VKsjrJI0m+1/5b+uVR97QQ1/SHkOSjwA+Ah6rql0bdz3JIshZYW1XfTvIzwDPAbVV1QX47OkmAy6rqB0neD/wl8NmqenLErS1Jkv8GjAMfrKpPjLqfpUryCjBeVefTF5nOWpIDwP+rqgfbHYk/VVVvjLqv+XilP4Sq+gvg1Kj7WE5V9VpVfbvt/yNwBFg32q7OXs34QTt8f3tc0Fc0SdYDHwceHHUveq8kHwQ+CuwDqKp/Od8DHwx9AUk2AtcBT422k6VpSyHPASeBiaq6oOcD/D7wm8C/jrqRZVTAnyd5pv3kyoXs54Bp4A/bEtyDSS4bdVMLMfQ7l+Snga8An6uq74+6n6Woqh9V1bXMfNN7c5ILdikuySeAk1X1zKh7WWY3VdX1zPzS7u62dHqhWgVcDzxQVdcB/wSc9z8Xb+h3rK19fwX4UlX96aj7WS7tn9jfBLaNuJWluAn4ZFsDfxj4WJL/M9qWlq6qTrTtSeBRZn5590I1BUwN/IvyEWbeBM5rhn6n2gef+4AjVfV7o+5nqZKMJVnd9n8S+FXge6Pt6uxV1eeran1VbWTm50q+XlX/ZcRtLUmSy9pNA7RlkK3ABXtHXFX9HXA8yYdbaQsXwM/Er/SvbF6QknwZ+BXgiiRTwJ6q2jfarpbsJuAzwHfaOjjAb1XV4yPsaSnWAgfa/6jnfcDBqroobnO8iFwFPDpzvcEq4I+r6mujbWnJfgP4Urtz52XgrhH3syBv2ZSkjri8I0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSR/4/QvNCLv5cjx8AAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.bar(c.keys(), c.values())" ] }, { "cell_type": "code", "execution_count": 770, "metadata": {}, "outputs": [], "source": [ "# %%time\n", "# c = Counter()\n", "# d = {}\n", "# t = 4\n", "# sets = [set(i) for i in list(itertools.combinations(range(1, v+1), t))]\n", "# print(len(sets))\n", "# for idx, p in enumerate(sets):\n", "# if idx % 1000 == 0:\n", "# print(idx)\n", "# ct = sum([p.issubset(r) for r in cover])\n", "# c[ct] += 1\n", "# if ct not in d:\n", "# d[ct] = []\n", "# d[ct].append(p)\n", "# # print(p, ct)" ] }, { "cell_type": "code", "execution_count": 771, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 771, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAASYklEQVR4nO3dX4yd9X3n8fcnODQtbWoTBmTZ1pqqVra0UoAdGSqkqBt3jSFRzEWQiHaDhVx5L9wq0a7UJb2xCo1Eb5ou0hbJwu6abhrqJUVYKQodOYm6vYAwBEoCDrJLKR6Z4mltSFPUVKTfvZifmwPMnzOe8Rzbv/dLOnqe5/v8zpnv74LPefw7zzmkqpAk9eF9o25AkrRyDH1J6oihL0kdMfQlqSOGviR1ZNWoG5jPFVdcURs3bhx1G5J0QXnmmWf+vqrGZjt3Xof+xo0bmZycHHUbknRBSfK3c51zeUeSOmLoS1JHFgz9JB9O8tzA4/tJPpfk8iQTSY627Zo2PknuT3IsyfNJrh94rR1t/NEkO87lxCRJ77Vg6FfVS1V1bVVdC/wH4C3gUeBu4HBVbQIOt2OAW4BN7bELeAAgyeXAHuAGYDOw58wbhSRpZSx2eWcL8NdV9bfAduBAqx8Abmv724GHasaTwOoka4GbgYmqOlVVp4EJYNuSZyBJGtpiQ/8O4Mtt/6qqeg2gba9s9XXA8YHnTLXaXPV3SLIryWSSyenp6UW2J0maz9Chn+RS4JPA/11o6Cy1mqf+zkLV3qoar6rxsbFZbzOVJJ2lxVzp3wJ8u6peb8evt2Ub2vZkq08BGwaetx44MU9dkrRCFhP6n+bHSzsAh4Azd+DsAB4bqN/Z7uK5EXizLf88AWxNsqZ9gLu11SRJK2Sob+Qm+SngPwH/daB8H3AwyU7gVeD2Vn8cuBU4xsydPncBVNWpJPcCT7dx91TVqSXPYB4b7/6zc/nyy+aV+z4+6hYkdWKo0K+qt4APvav2D8zczfPusQXsnuN19gP7F9+mJGk5+I1cSeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4MFfpJVid5JMn3khxJ8stJLk8ykeRo265pY5Pk/iTHkjyf5PqB19nRxh9NsuNcTUqSNLthr/T/J/C1qvr3wEeAI8DdwOGq2gQcbscAtwCb2mMX8ABAksuBPcANwGZgz5k3CknSylgw9JN8EPgosA+gqv6lqt4AtgMH2rADwG1tfzvwUM14ElidZC1wMzBRVaeq6jQwAWxb1tlIkuY1zJX+zwHTwB8meTbJg0kuA66qqtcA2vbKNn4dcHzg+VOtNlf9HZLsSjKZZHJ6enrRE5IkzW2Y0F8FXA88UFXXAf/Ej5dyZpNZajVP/Z2Fqr1VNV5V42NjY0O0J0ka1jChPwVMVdVT7fgRZt4EXm/LNrTtyYHxGwaevx44MU9dkrRCFgz9qvo74HiSD7fSFuBF4BBw5g6cHcBjbf8QcGe7i+dG4M22/PMEsDXJmvYB7tZWkyStkFVDjvsN4EtJLgVeBu5i5g3jYJKdwKvA7W3s48CtwDHgrTaWqjqV5F7g6Tbunqo6tSyzkCQNZajQr6rngPFZTm2ZZWwBu+d4nf3A/sU0KElaPn4jV5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0JakjQ4V+kleSfCfJc0kmW+3yJBNJjrbtmlZPkvuTHEvyfJLrB15nRxt/NMmOczMlSdJcFnOl/x+r6tqqGm/HdwOHq2oTcLgdA9wCbGqPXcADMPMmAewBbgA2A3vOvFFIklbGUpZ3tgMH2v4B4LaB+kM140lgdZK1wM3ARFWdqqrTwASwbQl/X5K0SMOGfgF/nuSZJLta7aqqeg2gba9s9XXA8YHnTrXaXPV3SLIryWSSyenp6eFnIkla0Kohx91UVSeSXAlMJPnePGMzS63mqb+zULUX2AswPj7+nvOSpLM31JV+VZ1o25PAo8ysyb/elm1o25Nt+BSwYeDp64ET89QlSStkwdBPclmSnzmzD2wFvgscAs7cgbMDeKztHwLubHfx3Ai82ZZ/ngC2JlnTPsDd2mqSpBUyzPLOVcCjSc6M/+Oq+lqSp4GDSXYCrwK3t/GPA7cCx4C3gLsAqupUknuBp9u4e6rq1LLNRJK0oAVDv6peBj4yS/0fgC2z1AvYPcdr7Qf2L75NSdJy8Bu5ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0ZOvSTXJLk2SRfbcdXJ3kqydEkf5Lk0lb/iXZ8rJ3fOPAan2/1l5LcvNyTkSTNbzFX+p8Fjgwc/y7wxaraBJwGdrb6TuB0Vf088MU2jiTXAHcAvwhsA/4gySVLa1+StBhDhX6S9cDHgQfbcYCPAY+0IQeA29r+9nZMO7+ljd8OPFxVP6yqvwGOAZuXYxKSpOEMe6X/+8BvAv/ajj8EvFFVb7fjKWBd218HHAdo599s4/+tPstz/k2SXUkmk0xOT08vYiqSpIUsGPpJPgGcrKpnBsuzDK0Fzs33nB8XqvZW1XhVjY+NjS3UniRpEVYNMeYm4JNJbgU+AHyQmSv/1UlWtav59cCJNn4K2ABMJVkF/CxwaqB+xuBzJEkrYMEr/ar6fFWtr6qNzHwQ+/Wq+s/AN4BPtWE7gMfa/qF2TDv/9aqqVr+j3d1zNbAJ+NayzUSStKBhrvTn8j+Ah5P8DvAssK/V9wF/lOQYM1f4dwBU1QtJDgIvAm8Du6vqR0v4+5KkRVpU6FfVN4Fvtv2XmeXum6r6Z+D2OZ7/BeALi21SkrQ8/EauJHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcWDP0kH0jyrSR/leSFJL/d6lcneSrJ0SR/kuTSVv+Jdnysnd848Fqfb/WXktx8riYlSZrdMFf6PwQ+VlUfAa4FtiW5Efhd4ItVtQk4Dexs43cCp6vq54EvtnEkuQa4A/hFYBvwB0kuWc7JSJLmt2Do14wftMP3t0cBHwMeafUDwG1tf3s7pp3fkiSt/nBV/bCq/gY4BmxelllIkoYy1Jp+kkuSPAecBCaAvwbeqKq325ApYF3bXwccB2jn3wQ+NFif5TmDf2tXkskkk9PT04ufkSRpTkOFflX9qKquBdYzc3X+C7MNa9vMcW6u+rv/1t6qGq+q8bGxsWHakyQNaVF371TVG8A3gRuB1UlWtVPrgRNtfwrYANDO/yxwarA+y3MkSStgmLt3xpKsbvs/CfwqcAT4BvCpNmwH8FjbP9SOaee/XlXV6ne0u3uuBjYB31quiUiSFrZq4SGsBQ60O23eBxysqq8meRF4OMnvAM8C+9r4fcAfJTnGzBX+HQBV9UKSg8CLwNvA7qr60fJOR5I0nwVDv6qeB66bpf4ys9x9U1X/DNw+x2t9AfjC4tuUJC0Hv5ErSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1JEFQz/JhiTfSHIkyQtJPtvqlyeZSHK0bde0epLcn+RYkueTXD/wWjva+KNJdpy7aUmSZjPMlf7bwH+vql8AbgR2J7kGuBs4XFWbgMPtGOAWYFN77AIegJk3CWAPcAOwGdhz5o1CkrQyFgz9qnqtqr7d9v8ROAKsA7YDB9qwA8BtbX878FDNeBJYnWQtcDMwUVWnquo0MAFsW9bZSJLmtag1/SQbgeuAp4Crquo1mHljAK5sw9YBxweeNtVqc9Xf/Td2JZlMMjk9Pb2Y9iRJCxg69JP8NPAV4HNV9f35hs5Sq3nq7yxU7a2q8aoaHxsbG7Y9SdIQhgr9JO9nJvC/VFV/2sqvt2Ub2vZkq08BGwaevh44MU9dkrRChrl7J8A+4EhV/d7AqUPAmTtwdgCPDdTvbHfx3Ai82ZZ/ngC2JlnTPsDd2mqSpBWyaogxNwGfAb6T5LlW+y3gPuBgkp3Aq8Dt7dzjwK3AMeAt4C6AqjqV5F7g6Tbunqo6tSyzkCQNZcHQr6q/ZPb1eIAts4wvYPccr7Uf2L+YBiVJy8dv5EpSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1ZMHQT7I/yckk3x2oXZ5kIsnRtl3T6klyf5JjSZ5Pcv3Ac3a08UeT7Dg305EkzWeYK/3/DWx7V+1u4HBVbQIOt2OAW4BN7bELeABm3iSAPcANwGZgz5k3CknSylkw9KvqL4BT7ypvBw60/QPAbQP1h2rGk8DqJGuBm4GJqjpVVaeBCd77RiJJOsfOdk3/qqp6DaBtr2z1dcDxgXFTrTZXXZK0gpb7g9zMUqt56u99gWRXkskkk9PT08vanCT17mxD//W2bEPbnmz1KWDDwLj1wIl56u9RVXuraryqxsfGxs6yPUnSbM429A8BZ+7A2QE8NlC/s93FcyPwZlv+eQLYmmRN+wB3a6tJklbQqoUGJPky8CvAFUmmmLkL5z7gYJKdwKvA7W3448CtwDHgLeAugKo6leRe4Ok27p6qeveHw5Kkc2zB0K+qT89xasssYwvYPcfr7Af2L6o7SdKy8hu5ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SerIgj+4pvPHxrv/bNQtDOWV+z4+6hYkzcErfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6siKh36SbUleSnIsyd0r/fclqWcrGvpJLgH+F3ALcA3w6STXrGQPktSzlf7tnc3Asap6GSDJw8B24MUV7kPSEC7G33u6GOe0GKmqc/LCs/6x5FPAtqr6tXb8GeCGqvr1gTG7gF3t8MPASyvW4HCuAP5+1E0sI+dz/rvY5nSxzQfOvzn9u6oam+3ESl/pZ5baO951qmovsHdl2lm8JJNVNT7qPpaL8zn/XWxzutjmAxfWnFb6g9wpYMPA8XrgxAr3IEndWunQfxrYlOTqJJcCdwCHVrgHSerWii7vVNXbSX4deAK4BNhfVS+sZA/L4LxdejpLzuf8d7HN6WKbD1xAc1rRD3IlSaPlN3IlqSOGviR1xNAfQpL9SU4m+e6oe1kuSTYk+UaSI0leSPLZUfe0FEk+kORbSf6qzee3R93TckhySZJnk3x11L0shySvJPlOkueSTI66n6VKsjrJI0m+1/5b+uVR97QQ1/SHkOSjwA+Ah6rql0bdz3JIshZYW1XfTvIzwDPAbVV1QX47OkmAy6rqB0neD/wl8NmqenLErS1Jkv8GjAMfrKpPjLqfpUryCjBeVefTF5nOWpIDwP+rqgfbHYk/VVVvjLqv+XilP4Sq+gvg1Kj7WE5V9VpVfbvt/yNwBFg32q7OXs34QTt8f3tc0Fc0SdYDHwceHHUveq8kHwQ+CuwDqKp/Od8DHwx9AUk2AtcBT422k6VpSyHPASeBiaq6oOcD/D7wm8C/jrqRZVTAnyd5pv3kyoXs54Bp4A/bEtyDSS4bdVMLMfQ7l+Snga8An6uq74+6n6Woqh9V1bXMfNN7c5ILdikuySeAk1X1zKh7WWY3VdX1zPzS7u62dHqhWgVcDzxQVdcB/wSc9z8Xb+h3rK19fwX4UlX96aj7WS7tn9jfBLaNuJWluAn4ZFsDfxj4WJL/M9qWlq6qTrTtSeBRZn5590I1BUwN/IvyEWbeBM5rhn6n2gef+4AjVfV7o+5nqZKMJVnd9n8S+FXge6Pt6uxV1eeran1VbWTm50q+XlX/ZcRtLUmSy9pNA7RlkK3ABXtHXFX9HXA8yYdbaQsXwM/Er/SvbF6QknwZ+BXgiiRTwJ6q2jfarpbsJuAzwHfaOjjAb1XV4yPsaSnWAgfa/6jnfcDBqroobnO8iFwFPDpzvcEq4I+r6mujbWnJfgP4Urtz52XgrhH3syBv2ZSkjri8I0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSR/4/QvNCLv5cjx8AAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.bar(c.keys(), c.values())" ] }, { "cell_type": "code", "execution_count": 772, "metadata": {}, "outputs": [], "source": [ "e = d.copy()" ] }, { "cell_type": "code", "execution_count": 773, "metadata": {}, "outputs": [], "source": [ "del e[1]" ] }, { "cell_type": "code", "execution_count": 774, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 774, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAREUlEQVR4nO3df6zddX3H8edrBdGpsypXwtpmZdptoomF3DEWksWB2RCNxUQWzKbEkNQluGA0m+A/m8lINNnEmWwknTjr5oYENTSKTsaPGP8QvMWKYDV22NlrO3o3AWVGFvC9P86n2bU97T33nnvusZ8+H8nJ+X7f38/3nPc3gVe//fT7Pd9UFZKkvvzCtBuQJK0+w12SOmS4S1KHDHdJ6pDhLkkdOm3aDQCceeaZtXnz5mm3IUknld27d/9XVc0M2/ZzEe6bN29mbm5u2m1I0kklyX8cb5vTMpLUIcNdkjpkuEtShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1KGfiztUx7H5us9Nu4VVs//9r5t2C5I64Zm7JHXIcJekDhnuktQhw12SOjRyuCdZl+RrST7b1s9Jcl+S7yT5ZJJntfoZbX1f2755Mq1Lko5nOWfu1wJ7F61/ALixqrYAjwFXt/rVwGNV9TLgxjZOkrSGRgr3JBuB1wEfaesBLgZua0N2Ape35W1tnbb9kjZekrRGRj1z/xDwZ8BP2/qLgcer6um2Pg9saMsbgAMAbfsTbbwkaY0sGe5JXg8crqrdi8tDhtYI2xZ/7vYkc0nmFhYWRmpWkjSaUc7cLwLekGQ/cAuD6ZgPAeuTHLnDdSNwsC3PA5sA2vYXAD84+kOrakdVzVbV7MzM0Oe7SpJWaMlwr6rrq2pjVW0GrgTurqo/BO4B3tSGXQXc3pZ3tXXa9rur6pgzd0nS5Ixznft7gHcl2cdgTv3mVr8ZeHGrvwu4brwWJUnLtawfDquqe4F72/IjwAVDxvwEuGIVepMkrZB3qEpShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOjTKA7KfneT+JF9P8nCS97X6x5J8N8me9tra6kny4ST7kjyY5PxJH4Qk6WeN8iSmp4CLq+rJJKcDX07y+bbtT6vqtqPGvxbY0l6/BdzU3iVJa2SUB2RXVT3ZVk9vrxM98Hob8PG231eA9UnOHr9VSdKoRppzT7IuyR7gMHBnVd3XNt3Qpl5uTHJGq20ADizafb7Vjv7M7UnmkswtLCyMcQiSpKONFO5V9UxVbQU2AhckeSVwPfAbwG8CLwLe04Zn2EcM+cwdVTVbVbMzMzMral6SNNyyrpapqseBe4FLq+pQm3p5CvgH4II2bB7YtGi3jcDBVehVkjSiUa6WmUmyvi0/B3gN8K0j8+hJAlwOPNR22QW8tV01cyHwRFUdmkj3kqShRrla5mxgZ5J1DP4wuLWqPpvk7iQzDKZh9gB/3MbfAVwG7AN+DLxt9duWJJ3IkuFeVQ8C5w2pX3yc8QVcM35rkqSV8g5VSeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHRnnM3rOT3J/k60keTvK+Vj8nyX1JvpPkk0me1epntPV9bfvmyR6CJOloo5y5PwVcXFWvArYCl7Zno34AuLGqtgCPAVe38VcDj1XVy4Ab2zhJ0hpaMtxr4Mm2enp7FXAxcFur72TwkGyAbW2dtv2S9hBtSdIaGWnOPcm6JHuAw8CdwL8Dj1fV023IPLChLW8ADgC07U8ALx7ymduTzCWZW1hYGO8oJEk/Y6Rwr6pnqmorsBG4AHj5sGHtfdhZeh1TqNpRVbNVNTszMzNqv5KkESzrapmqehy4F7gQWJ/ktLZpI3CwLc8DmwDa9hcAP1iNZiVJoxnlapmZJOvb8nOA1wB7gXuAN7VhVwG3t+VdbZ22/e6qOubMXZI0OactPYSzgZ1J1jH4w+DWqvpskm8CtyT5S+BrwM1t/M3APybZx+CM/coJ9C1JOoElw72qHgTOG1J/hMH8+9H1nwBXrEp3kqQV8Q5VSeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHRnnM3qYk9yTZm+ThJNe2+l8k+X6SPe112aJ9rk+yL8m3k/z+JA9AknSsUR6z9zTw7qp6IMnzgd1J7mzbbqyqv1o8OMm5DB6t9wrgl4F/S/JrVfXMajYuSTq+Jc/cq+pQVT3Qln/E4OHYG06wyzbglqp6qqq+C+xjyOP4JEmTs6w59ySbGTxP9b5WekeSB5N8NMkLW20DcGDRbvMM+cMgyfYkc0nmFhYWlt24JOn4Rg73JM8DPgW8s6p+CNwEvBTYChwC/vrI0CG71zGFqh1VNVtVszMzM8tuXJJ0fCOFe5LTGQT7J6rq0wBV9WhVPVNVPwX+nv+fepkHNi3afSNwcPValiQtZZSrZQLcDOytqg8uqp+9aNgbgYfa8i7gyiRnJDkH2ALcv3otS5KWMsrVMhcBbwG+kWRPq70XeHOSrQymXPYDbweoqoeT3Ap8k8GVNtd4pYwkra0lw72qvszwefQ7TrDPDcANY/QlSRqDd6hKUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHDHdJ6pDhLkkdMtwlqUOGuyR1yHCXpA4Z7pLUIcNdkjo0ymP2NiW5J8neJA8nubbVX5TkziTfae8vbPUk+XCSfUkeTHL+pA9CkvSzRjlzfxp4d1W9HLgQuCbJucB1wF1VtQW4q60DvJbBc1O3ANuBm1a9a0nSCS0Z7lV1qKoeaMs/AvYCG4BtwM42bCdweVveBny8Br4CrD/qYdqSpAlb1px7ks3AecB9wFlVdQgGfwAAL2nDNgAHFu0232pHf9b2JHNJ5hYWFpbfuSTpuEYO9yTPAz4FvLOqfniioUNqdUyhakdVzVbV7MzMzKhtSJJGMFK4JzmdQbB/oqo+3cqPHpluae+HW30e2LRo943AwdVpV5I0ilGulglwM7C3qj64aNMu4Kq2fBVw+6L6W9tVMxcCTxyZvpEkrY3TRhhzEfAW4BtJ9rTae4H3A7cmuRr4HnBF23YHcBmwD/gx8LZV7ViStKQlw72qvszweXSAS4aML+CaMfuSJI3BO1QlqUOGuyR1yHCXpA4Z7pLUIcNdkjpkuEtShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nq0ChPYvpoksNJHlpU+4sk30+yp70uW7Tt+iT7knw7ye9PqnFJ0vGNcub+MeDSIfUbq2pre90BkORc4ErgFW2fv0uybrWalSSNZslwr6ovAT8Y8fO2AbdU1VNV9V0Gj9q7YIz+JEkrMM6c+zuSPNimbV7YahuAA4vGzLfaMZJsTzKXZG5hYWGMNiRJR1tpuN8EvBTYChwC/rrVhz1rtYZ9QFXtqKrZqpqdmZlZYRuSpGFWFO5V9WhVPVNVPwX+nv+fepkHNi0auhE4OF6LkqTlWlG4Jzl70eobgSNX0uwCrkxyRpJzgC3A/eO1KElartOWGpDkX4BXA2cmmQf+HHh1kq0Mplz2A28HqKqHk9wKfBN4Grimqp6ZTOuSpONZMtyr6s1DyjefYPwNwA3jNCVJGo93qEpShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOrRkuCf5aJLDSR5aVHtRkjuTfKe9v7DVk+TDSfYleTDJ+ZNsXpI03Chn7h8DLj2qdh1wV1VtAe5q6wCvZfDc1C3AduCm1WlTkrQcS4Z7VX0J+MFR5W3Azra8E7h8Uf3jNfAVYP1RD9OWJK2Blc65n1VVhwDa+0tafQNwYNG4+VY7RpLtSeaSzC0sLKywDUnSMKv9D6oZUqthA6tqR1XNVtXszMzMKrchSae2lYb7o0emW9r74VafBzYtGrcROLjy9iRJK7HScN8FXNWWrwJuX1R/a7tq5kLgiSPTN5KktXPaUgOS/AvwauDMJPPAnwPvB25NcjXwPeCKNvwO4DJgH/Bj4G0T6FmStIQlw72q3nycTZcMGVvANeM2JUkaj3eoSlKHDHdJ6pDhLkkdMtwlqUOGuyR1yHCXpA4Z7pLUIcNdkjpkuEtShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6tOTDOk4kyX7gR8AzwNNVNZvkRcAngc3AfuAPquqx8dqUJC3Hapy5/25Vba2q2bZ+HXBXVW0B7mrrkqQ1NIlpmW3Azra8E7h8At8hSTqBccO9gC8m2Z1ke6udVVWHANr7S4btmGR7krkkcwsLC2O2IUlabKw5d+CiqjqY5CXAnUm+NeqOVbUD2AEwOztbY/YhSVpkrDP3qjrY3g8DnwEuAB5NcjZAez88bpOSpOVZcbgneW6S5x9ZBn4PeAjYBVzVhl0F3D5uk5Kk5RlnWuYs4DNJjnzOP1fVF5J8Fbg1ydXA94Arxm9TkrQcKw73qnoEeNWQ+n8Dl4zTlCRpPN6hKkkdMtwlqUOGuyR1yHCXpA4Z7pLUIcNdkjpkuEtShwx3SeqQ4S5JHTLcJalD4/7kr6Qp2Xzd56bdwqrY//7XTbuFLnnmLkkdMtwlqUNOy0g66fQyJQWTm5byzF2SOmS4S1KHJhbuSS5N8u0k+5JcN6nvkSQdayLhnmQd8LfAa4FzgTcnOXcS3yVJOtakztwvAPZV1SNV9b/ALcC2CX2XJOkok7paZgNwYNH6PPBbiwck2Q5sb6tPJvn2hHpZLWcC/zXJL8gHJvnpY5n4sf+cO5WP3//uJ2zM4/+V422YVLhnSK1+ZqVqB7BjQt+/6pLMVdXstPuYhlP52OHUPn6P/eQ99klNy8wDmxatbwQOTui7JElHmVS4fxXYkuScJM8CrgR2Tei7JElHmci0TFU9neQdwL8C64CPVtXDk/iuNXTSTCFNwKl87HBqH7/HfpJKVS09SpJ0UvEOVUnqkOEuSR0y3E8gyaYk9yTZm+ThJNdOu6e1lOTZSe5P8vV2/O+bdk9rLcm6JF9L8tlp97LWkuxP8o0ke5LMTbuftZRkfZLbknyr/f//29Puabn8yd8Texp4d1U9kOT5wO4kd1bVN6fd2Bp5Cri4qp5Mcjrw5SSfr6qvTLuxNXQtsBf4pWk3MiW/W1Wn4g1cfwN8oare1K74+8VpN7RcnrmfQFUdqqoH2vKPGPxPvmG6Xa2dGniyrZ7eXqfMv8An2Qi8DvjItHvR2knyS8DvADcDVNX/VtXj0+1q+Qz3ESXZDJwH3DfdTtZWm5bYAxwG7qyqU+n4PwT8GfDTaTcyJQV8Mcnu9nMhp4pfBRaAf2hTch9J8txpN7VchvsIkjwP+BTwzqr64bT7WUtV9UxVbWVwl/EFSV457Z7WQpLXA4erave0e5mii6rqfAa/7npNkt+ZdkNr5DTgfOCmqjoP+B/gpPvZcsN9CW2u+VPAJ6rq09PuZ1raX0vvBS6dcitr5SLgDUn2M/hV04uT/NN0W1pbVXWwvR8GPsPg115PBfPA/KK/pd7GIOxPKob7CSQJg3m3vVX1wWn3s9aSzCRZ35afA7wG+NZ0u1obVXV9VW2sqs0Mfj7j7qr6oym3tWaSPLddRECbkvg94KHpdrU2quo/gQNJfr2VLgFOuosovFrmxC4C3gJ8o807A7y3qu6YYk9r6WxgZ3v4yi8At1bVKXdJ4CnqLOAzg/MbTgP+uaq+MN2W1tSfAJ9oV8o8Arxtyv0smz8/IEkdclpGkjpkuEtShwx3SeqQ4S5JHTLcJalDhrskdchwl6QO/R/zToZgrWHeqgAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.bar(e.keys(), [len(x) for x in e.values()])" ] }, { "cell_type": "code", "execution_count": 775, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "dict_keys([6, 5, 2])" ] }, "execution_count": 775, "metadata": {}, "output_type": "execute_result" } ], "source": [ "e.keys()" ] }, { "cell_type": "code", "execution_count": 776, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{1, 2, 3, 10},\n", " {1, 4, 8, 10},\n", " {1, 5, 9, 10},\n", " {1, 6, 7, 10},\n", " {2, 4, 9, 10},\n", " {2, 5, 7, 10},\n", " {2, 6, 8, 10},\n", " {3, 4, 7, 10},\n", " {3, 5, 8, 10},\n", " {3, 6, 9, 10},\n", " {4, 5, 6, 10},\n", " {7, 8, 9, 10}]" ] }, "execution_count": 776, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d[6]" ] }, { "cell_type": "code", "execution_count": 779, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[array([ 1, 2, 4, 5, 11]),\n", " array([ 1, 2, 4, 5, 12]),\n", " array([ 1, 2, 4, 5, 14]),\n", " array([ 1, 2, 4, 5, 15]),\n", " array([ 1, 2, 4, 5, 20])]" ] }, "execution_count": 779, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[s for s in cover if set(d[5][0]).issubset(s)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Method 2:" ] }, { "cell_type": "code", "execution_count": 780, "metadata": {}, "outputs": [], "source": [ "lst = []\n", "for x in e:\n", " lst += e[x]" ] }, { "cell_type": "code", "execution_count": 781, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1540\n", "0\n", "1000\n", "CPU times: user 92 ms, sys: 4.02 ms, total: 96 ms\n", "Wall time: 94.4 ms\n" ] } ], "source": [ "%%time\n", "c2 = Counter()\n", "d2 = {}\n", "t = 3\n", "sets = [set(i) for i in list(itertools.combinations(range(1, v+1), t))]\n", "print(len(sets))\n", "for idx, p in enumerate(sets):\n", " if idx % 1000 == 0:\n", " print(idx)\n", " ct = sum([p.issubset(r) for r in lst])\n", " c2[ct] += 1\n", " if ct not in d2:\n", " d2[ct] = []\n", " d2[ct].append(p)\n", "# print(p, ct)" ] }, { "cell_type": "code", "execution_count": 782, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 782, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAD4CAYAAAAKA1qZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAR70lEQVR4nO3dcayd913f8feHOEkpHXUa35bM9nAY1lioYPWs1KwSijBrkxTFkdZIiSbiZpmsbWGUdRN1QcJaEVKrTWTLxoIM9upMVdoodIspKZ2Xtqr4I6E3oU2TuiV3oYsvCfUFpy4sg87suz/Oz+T2+l7fe8+5vsfHv/dLOjrP83u+z3l+Pz3O+dzn95xzkqpCktSn7xh3ByRJ42MISFLHDAFJ6pghIEkdMwQkqWMbxt2B89m0aVNt27Zt3N2QpIny5JNP/nFVTa2k9qIOgW3btjE9PT3ubkjSREnyv1Za63SQJHXMEJCkji0bAkkOJzmZ5JlFtv2rJJVkU1tPkvuSzCR5OsmOebV7kzzXHnvXdhiSpGGs5Ergw8CNCxuTbAX+PvDCvOabgO3tsQ+4v9W+ATgAvBW4HjiQ5KpROi5JGt2yIVBVnwNOLbLpXuBngfk/PrQHeKAGHgc2JrkGeAdwrKpOVdXLwDEWCRZJ0voa6p5AkluAP6yqLy7YtBk4MW99trUt1b7Ya+9LMp1kem5ubpjuSZJWaNUhkOS1wM8Dv7DY5kXa6jzt5zZWHayqnVW1c2pqRR9zlSQNaZgrgb8JXAt8McnXgC3AU0m+h8Ff+Fvn1W4BXjxPuyRpjFYdAlX1pap6Y1Vtq6ptDN7gd1TVHwFHgTvbp4R2Aaer6iXgU8Dbk1zVbgi/vbVJksZo2W8MJ3kQuAHYlGQWOFBVh5YofxS4GZgBXgHuAqiqU0l+Efh8q/tAVS12s3lNbdv/Wxf6EN362gffOe4uSFoDy4ZAVd2xzPZt85YLuGeJusPA4VX2T5J0AfmNYUnqmCEgSR0zBCSpY4aAJHXMEJCkjhkCktQxQ0CSOmYISFLHDAFJ6pghIEkdMwQkqWOGgCR1zBCQpI4ZApLUMUNAkjpmCEhSxwwBSeqYISBJHTMEJKljhoAkdcwQkKSOLRsCSQ4nOZnkmXlt/ybJV5I8neS/Jtk4b9v7k8wk+WqSd8xrv7G1zSTZv/ZDkSSt1kquBD4M3Lig7Rjw5qr6IeD3gfcDJLkOuB34wbbPf0pyWZLLgF8BbgKuA+5otZKkMVo2BKrqc8CpBW3/varOtNXHgS1teQ/w0ar6i6r6A2AGuL49Zqrq+ar6FvDRVitJGqO1uCfwj4BPtuXNwIl522Zb21Lt50iyL8l0kum5ubk16J4kaSkjhUCSnwfOAB8527RIWZ2n/dzGqoNVtbOqdk5NTY3SPUnSMjYMu2OSvcBPALur6uwb+iywdV7ZFuDFtrxUuyRpTIa6EkhyI/A+4JaqemXepqPA7UmuTHItsB34XeDzwPYk1ya5gsHN46OjdV2SNKplrwSSPAjcAGxKMgscYPBpoCuBY0kAHq+qf1JVzyZ5CPgyg2mie6rqL9vr/BTwKeAy4HBVPXsBxiNJWoVlQ6Cq7lik+dB56n8J+KVF2h8FHl1V7yRJF5TfGJakjhkCktQxQ0CSOmYISFLHDAFJ6pghIEkdMwQkqWOGgCR1zBCQpI4ZApLUMUNAkjpmCEhSxwwBSeqYISBJHTMEJKljhoAkdcwQkKSOGQKS1DFDQJI6ZghIUscMAUnq2LIhkORwkpNJnpnX9oYkx5I8156vau1Jcl+SmSRPJ9kxb5+9rf65JHsvzHAkSauxkiuBDwM3LmjbDzxWVduBx9o6wE3A9vbYB9wPg9AADgBvBa4HDpwNDknS+CwbAlX1OeDUguY9wJG2fAS4dV77AzXwOLAxyTXAO4BjVXWqql4GjnFusEiS1tmw9wTeVFUvAbTnN7b2zcCJeXWzrW2pdknSGK31jeEs0lbnaT/3BZJ9SaaTTM/Nza1p5yRJ327YEPh6m+ahPZ9s7bPA1nl1W4AXz9N+jqo6WFU7q2rn1NTUkN2TJK3EsCFwFDj7CZ+9wCPz2u9snxLaBZxu00WfAt6e5Kp2Q/jtrU2SNEYblitI8iBwA7ApySyDT/l8EHgoyd3AC8BtrfxR4GZgBngFuAugqk4l+UXg863uA1W18GazJGmdLRsCVXXHEpt2L1JbwD1LvM5h4PCqeidJuqD8xrAkdcwQkKSOGQKS1DFDQJI6ZghIUscMAUnqmCEgSR0zBCSpY4aAJHXMEJCkjhkCktQxQ0CSOmYISFLHDAFJ6pghIEkdMwQkqWOGgCR1zBCQpI4ZApLUMUNAkjpmCEhSx0YKgST/IsmzSZ5J8mCS1yS5NskTSZ5L8rEkV7TaK9v6TNu+bS0GIEka3tAhkGQz8NPAzqp6M3AZcDvwIeDeqtoOvAzc3Xa5G3i5qr4fuLfVSZLGaNTpoA3AdybZALwWeAn4MeDhtv0IcGtb3tPWadt3J8mIx5ckjWDoEKiqPwT+LfACgzf/08CTwDeq6kwrmwU2t+XNwIm275lWf/Wwx5ckjW6U6aCrGPx1fy3w14HvAm5apLTO7nKebfNfd1+S6STTc3Nzw3ZPkrQCo0wH/TjwB1U1V1X/F/g48PeAjW16CGAL8GJbngW2ArTtrwdOLXzRqjpYVTuraufU1NQI3ZMkLWeUEHgB2JXktW1ufzfwZeAzwLtazV7gkbZ8tK3Ttn+6qs65EpAkrZ9R7gk8weAG71PAl9prHQTeB7w3yQyDOf9DbZdDwNWt/b3A/hH6LUlaAxuWL1laVR0ADixofh64fpHaPwduG+V4kqS15TeGJaljhoAkdcwQkKSOGQKS1DFDQJI6ZghIUscMAUnqmCEgSR0zBCSpY4aAJHXMEJCkjhkCktQxQ0CSOmYISFLHDAFJ6pghIEkdMwQkqWOGgCR1zBCQpI4ZApLUMUNAkjo2Uggk2Zjk4SRfSXI8yY8keUOSY0mea89XtdokuS/JTJKnk+xYmyFIkoY16pXAvwd+u6p+APhh4DiwH3isqrYDj7V1gJuA7e2xD7h/xGNLkkY0dAgk+W7gR4FDAFX1rar6BrAHONLKjgC3tuU9wAM18DiwMck1Q/dckjSyUa4Evg+YA/5zkt9L8utJvgt4U1W9BNCe39jqNwMn5u0/29okSWMySghsAHYA91fVW4D/zatTP4vJIm11TlGyL8l0kum5ubkRuidJWs4oITALzFbVE239YQah8PWz0zzt+eS8+q3z9t8CvLjwRavqYFXtrKqdU1NTI3RPkrScoUOgqv4IOJHkb7Wm3cCXgaPA3ta2F3ikLR8F7myfEtoFnD47bSRJGo8NI+7/z4GPJLkCeB64i0GwPJTkbuAF4LZW+yhwMzADvNJqJUljNFIIVNUXgJ2LbNq9SG0B94xyPEnS2vIbw5LUMUNAkjpmCEhSxwwBSeqYISBJHTMEJKljhoAkdcwQkKSOGQKS1DFDQJI6ZghIUscMAUnqmCEgSR0zBCSpY4aAJHXMEJCkjhkCktQxQ0CSOmYISFLHDAFJ6pghIEkdMwQkqWMjh0CSy5L8XpJPtPVrkzyR5LkkH0tyRWu/sq3PtO3bRj22JGk0a3El8B7g+Lz1DwH3VtV24GXg7tZ+N/ByVX0/cG+rkySN0UghkGQL8E7g19t6gB8DHm4lR4Bb2/Ketk7bvrvVS5LGZNQrgX8H/Czw/9r61cA3qupMW58FNrflzcAJgLb9dKv/Nkn2JZlOMj03Nzdi9yRJ5zN0CCT5CeBkVT05v3mR0lrBtlcbqg5W1c6q2jk1NTVs9yRJK7BhhH3fBtyS5GbgNcB3M7gy2JhkQ/trfwvwYqufBbYCs0k2AK8HTo1wfEnSiIa+Eqiq91fVlqraBtwOfLqq/iHwGeBdrWwv8EhbPtrWads/XVXnXAlIktbPhfiewPuA9yaZYTDnf6i1HwKubu3vBfZfgGNLklZhlOmgv1JVnwU+25afB65fpObPgdvW4niSpLXhN4YlqWOGgCR1zBCQpI4ZApLUMUNAkjpmCEhSxwwBSeqYISBJHTMEJKljhoAkdcwQkKSOGQKS1DFDQJI6ZghIUscMAUnqmCEgSR0zBCSpY4aAJHXMEJCkjhkCktQxQ0CSOjZ0CCTZmuQzSY4neTbJe1r7G5IcS/Jce76qtSfJfUlmkjydZMdaDUKSNJxRrgTOAP+yqv42sAu4J8l1wH7gsaraDjzW1gFuAra3xz7g/hGOLUlaA0OHQFW9VFVPteU/BY4Dm4E9wJFWdgS4tS3vAR6ogceBjUmuGbrnkqSRrck9gSTbgLcATwBvqqqXYBAUwBtb2WbgxLzdZlvbwtfal2Q6yfTc3NxadE+StISRQyDJ64DfAH6mqr55vtJF2uqchqqDVbWzqnZOTU2N2j1J0nmMFAJJLmcQAB+pqo+35q+fneZpzydb+yywdd7uW4AXRzm+JGk0o3w6KMAh4HhV/fK8TUeBvW15L/DIvPY726eEdgGnz04bSZLGY8MI+74N+EngS0m+0Np+Dvgg8FCSu4EXgNvatkeBm4EZ4BXgrhGOLUlaA0OHQFX9DovP8wPsXqS+gHuGPZ4kae35jWFJ6pghIEkdMwQkqWOGgCR1zBCQpI4ZApLUMUNAkjpmCEhSxwwBSeqYISBJHRvlt4MkdW7b/t8adxcuWV/74DvX5TheCUhSxwwBSeqY00G6aDi1cOGs19SCJo9XApLUMUNAkjpmCEhSxwwBSeqYISBJHTMEJKljhoAkdWzdQyDJjUm+mmQmyf71Pr4k6VXrGgJJLgN+BbgJuA64I8l169kHSdKr1vtK4Hpgpqqer6pvAR8F9qxzHyRJzXr/bMRm4MS89VngrfMLkuwD9rXVP0vy1QWvsQn44wvWw/GZqHHlQysunahxrdLEjG0V5wsmaFxDmJixjXjOvnelO653CGSRtvq2laqDwMElXyCZrqqda92xcXNck+dSHdulOi64dMc2yrjWezpoFtg6b30L8OI690GS1Kx3CHwe2J7k2iRXALcDR9e5D5KkZl2ng6rqTJKfAj4FXAYcrqpnV/kyS04VTTjHNXku1bFdquOCS3dsQ48rVbV8lSTpkuQ3hiWpY4aAJHXsogyB5X5aIsm7k8wl+UJ7/ONx9HO1khxOcjLJM0tsT5L72rifTrJjvfs4rBWM7YYkp+eds19Y7z4OI8nWJJ9JcjzJs0nes0jNxJ23FY5r4s5Zktck+d0kX2zj+teL1FyZ5GPtfD2RZNv693T1Vji21b83VtVF9WBww/h/At8HXAF8EbhuQc27gf847r4OMbYfBXYAzyyx/Wbgkwy+T7ELeGLcfV7Dsd0AfGLc/RxiXNcAO9ryXwN+f5F/jxN33lY4rok7Z+0cvK4tXw48AexaUPPPgF9ty7cDHxt3v9dwbKt+b7wYrwQu2Z+WqKrPAafOU7IHeKAGHgc2JrlmfXo3mhWMbSJV1UtV9VRb/lPgOINvvs83cedtheOaOO0c/Flbvbw9Fn76ZQ9wpC0/DOxOstgXWS8qKxzbql2MIbDYT0ss9o/zH7RL74eTbF1k+yRa6dgn1Y+0S9lPJvnBcXdmtdq0wVsY/AU230Sft/OMCybwnCW5LMkXgJPAsapa8nxV1RngNHD1+vZyOCsYG6zyvfFiDIFlf1oC+E1gW1X9EPA/eDXVJ91Kxj6pngK+t6p+GPgPwH8bc39WJcnrgN8Afqaqvrlw8yK7TMR5W2ZcE3nOquovq+rvMPhFguuTvHlBycSerxWMbdXvjRdjCCz70xJV9SdV9Rdt9deAv7tOfbvQLtmf1aiqb569lK2qR4HLk2wac7dWJMnlDN4oP1JVH1+kZCLP23LjmuRzBlBV3wA+C9y4YNNfna8kG4DXM2FTmUuNbZj3xosxBJb9aYkF8623MJjPvBQcBe5snzbZBZyuqpfG3am1kOR7zs67Jrmewb+9Pxlvr5bX+nwIOF5Vv7xE2cSdt5WMaxLPWZKpJBvb8ncCPw58ZUHZUWBvW34X8Olqd1UvZisZ2zDvjev9K6LLqiV+WiLJB4DpqjoK/HSSW4AzDBL83WPr8CokeZDBJy42JZkFDjC4uUNV/SrwKINPmswArwB3jaenq7eCsb0L+KdJzgD/B7h9Ev7DA94G/CTwpTYXC/BzwN+AiT5vKxnXJJ6za4AjGfwPrL4DeKiqPrHg/eMQ8F+SzDB4/7h9fN1dlZWMbdXvjf5shCR17GKcDpIkrRNDQJI6ZghIUscMAUnqmCEgSR0zBCSpY4aAJHXs/wPwTzfOndv+2AAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.bar(c2.keys(),c2.values())" ] }, { "cell_type": "code", "execution_count": 783, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Counter({1: 1378, 2: 72, 3: 90})" ] }, "execution_count": 783, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c2" ] }, { "cell_type": "code", "execution_count": 784, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3]" ] }, "execution_count": 784, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sorted(c2.keys())[-5:]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "trying for all of them..." ] }, { "cell_type": "code", "execution_count": 785, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1573\n", "0\n", "100\n", "200\n", "300\n", "400\n", "500\n", "600\n", "700\n", "800\n", "900\n", "1000\n", "1100\n", "1200\n", "1300\n", "1400\n", "1500\n" ] } ], "source": [ "outs = []\n", "print(len(cover))\n", "for idx, testval in enumerate(cover):\n", " if idx % 100 == 0:\n", " print(idx)\n", " testval = list(testval)\n", " vals = []\n", " for i in range(len(testval)):\n", " matches = [set(s) for s in cover if (set(testval[:i] + testval[i+1:]).issubset(s))]\n", " vals.append(len(matches))\n", " outs.append(vals)" ] }, { "cell_type": "code", "execution_count": 787, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(array([ 2., 0., 28., 0., 0., 60., 0., 786., 0., 697.]),\n", " array([1. , 1.4, 1.8, 2.2, 2.6, 3. , 3.4, 3.8, 4.2, 4.6, 5. ]),\n", " )" ] }, "execution_count": 787, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAATFElEQVR4nO3da4yc133f8e8vouR7TF1WqkqypQoTbtyglpmFylSA4YpuoEsgCogEyGgtWmDAXpTGrgukdF7USJEXMlBEqdpCAWu5pVxfJChWxciKG5WSEfSFlKwukSXTrjaqIm7JihtLopOqTsvk3xdzGK+WQ+4sd2aXOvl+gME8zzln9vnPIfe3z555ZjZVhSSpLz+y1gVIksbPcJekDhnuktQhw12SOmS4S1KH1q11AQAXXXRRbd68ea3LkKS3lCeffPIPq2pqWN9ZEe6bN29mZmZmrcuQpLeUJH9wqj6XZSSpQ4a7JHVopHBP8k+TPJ/kuSRfSfL2JJcleSLJC0nuTXJeG/u2tj/b+jdP8glIkk62ZLgn2QD8PDBdVT8OnAPcDHwOuKOqtgCvAbvaQ3YBr1XV+4A72jhJ0ioadVlmHfCOJOuAdwJHgKuA+1v/PuCGtr2j7dP6tyfJeMqVJI1iyXCvqv8J/CvgZQahfgx4Eni9qo63YXPAhra9ATjUHnu8jb9w8ddNsjvJTJKZ+fn5lT4PSdICoyzLnM/gbPwy4C8D7wKuGTL0xMdLDjtLP+mjJ6tqb1VNV9X01NTQyzQlSWdolGWZjwL/o6rmq+r/AV8D/jawvi3TAGwEDrftOWATQOt/L/DqWKuWJJ3WKOH+MrAtyTvb2vl24NvAY8CNbcxO4MG2vb/t0/ofLT80XpJW1ZLvUK2qJ5LcDzwFHAeeBvYCXwe+muSXW9vd7SF3A19MMsvgjP3mSRQuaTI27/n6mh37pduvW7Nj92akjx+oqs8Cn13U/CJwxZCxPwBuWnlpkqQz5TtUJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHDHdJ6pDhLkkdMtwlqUNLhnuS9yd5ZsHt+0k+leSCJI8keaHdn9/GJ8mdSWaTPJtk6+SfhiRpoSXDvaq+W1WXV9XlwE8AbwAPAHuAA1W1BTjQ9gGuAba0227grkkULkk6teUuy2wHfr+q/gDYAexr7fuAG9r2DuCeGngcWJ/k0rFUK0kayXLD/WbgK237kqo6AtDuL27tG4BDCx4z19reJMnuJDNJZubn55dZhiTpdNaNOjDJecD1wGeWGjqkrU5qqNoL7AWYnp4+qV+SVsvmPV9fs2O/dPt1E/m6yzlzvwZ4qqpeafuvnFhuafdHW/scsGnB4zYCh1daqCRpdMsJ94/xwyUZgP3Azra9E3hwQfst7aqZbcCxE8s3kqTVMdKyTJJ3An8X+AcLmm8H7kuyC3gZuKm1PwxcC8wyuLLm1rFVK0kayUjhXlVvABcuavseg6tnFo8t4LaxVCdJOiO+Q1WSOmS4S1KHDHdJ6pDhLkkdMtwlqUOGuyR1yHCXpA4Z7pLUIcNdkjpkuEtShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUodGCvck65Pcn+Q7SQ4m+ckkFyR5JMkL7f78NjZJ7kwym+TZJFsn+xQkSYuNeub+r4FvVNVfBz4IHAT2AAeqagtwoO0DXANsabfdwF1jrViStKQlwz3JjwIfBu4GqKr/W1WvAzuAfW3YPuCGtr0DuKcGHgfWJ7l07JVLkk5plDP3vwbMA/8hydNJPp/kXcAlVXUEoN1f3MZvAA4tePxca3uTJLuTzCSZmZ+fX9GTkCS92Sjhvg7YCtxVVR8C/jc/XIIZJkPa6qSGqr1VNV1V01NTUyMVK0kazSjhPgfMVdUTbf9+BmH/yonllnZ/dMH4TQsevxE4PJ5yJUmjWDLcq+p/AYeSvL81bQe+DewHdra2ncCDbXs/cEu7amYbcOzE8o0kaXWsG3HcPwG+lOQ84EXgVgY/GO5Lsgt4GbipjX0YuBaYBd5oYyVJq2ikcK+qZ4DpIV3bh4wt4LYV1iVJWgHfoSpJHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHDHdJ6pDhLkkdGinck7yU5FtJnkky09ouSPJIkhfa/fmtPUnuTDKb5NkkWyf5BCRJJ1vOmfvfqarLq+rEn9vbAxyoqi3AgbYPcA2wpd12A3eNq1hJ0mhWsiyzA9jXtvcBNyxov6cGHgfWJ7l0BceRJC3TqOFewG8leTLJ7tZ2SVUdAWj3F7f2DcChBY+da21vkmR3kpkkM/Pz82dWvSRpqHUjjruyqg4nuRh4JMl3TjM2Q9rqpIaqvcBegOnp6ZP6JUlnbqQz96o63O6PAg8AVwCvnFhuafdH2/A5YNOCh28EDo+rYEnS0pYM9yTvSvKeE9vATwHPAfuBnW3YTuDBtr0fuKVdNbMNOHZi+UaStDpGWZa5BHggyYnxX66qbyT5XeC+JLuAl4Gb2viHgWuBWeAN4NaxVy1JOq0lw72qXgQ+OKT9e8D2Ie0F3DaW6iRJZ8R3qEpShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHRg73JOckeTrJQ23/siRPJHkhyb1Jzmvtb2v7s61/82RKlySdynLO3D8JHFyw/zngjqraArwG7Grtu4DXqup9wB1tnCRpFY0U7kk2AtcBn2/7Aa4C7m9D9gE3tO0dbZ/Wv72NlyStklHP3H8V+AXgz9r+hcDrVXW87c8BG9r2BuAQQOs/1sa/SZLdSWaSzMzPz59h+ZKkYZYM9yQ/DRytqicXNg8ZWiP0/bCham9VTVfV9NTU1EjFSpJGs26EMVcC1ye5Fng78KMMzuTXJ1nXzs43Aofb+DlgEzCXZB3wXuDVsVcuSTqlJc/cq+ozVbWxqjYDNwOPVtXfAx4DbmzDdgIPtu39bZ/W/2hVnXTmLkmanJVc5/7PgU8nmWWwpn53a78buLC1fxrYs7ISJUnLNcqyzJ+rqm8C32zbLwJXDBnzA+CmMdQmSTpDvkNVkjpkuEtShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHlgz3JG9P8jtJfi/J80l+qbVfluSJJC8kuTfJea39bW1/tvVvnuxTkCQtNsqZ+58AV1XVB4HLgauTbAM+B9xRVVuA14Bdbfwu4LWqeh9wRxsnSVpFS4Z7Dfxx2z233Qq4Cri/te8DbmjbO9o+rX97koytYknSkkZac09yTpJngKPAI8DvA69X1fE2ZA7Y0LY3AIcAWv8x4MIhX3N3kpkkM/Pz8yt7FpKkNxkp3KvqT6vqcmAjcAXwY8OGtfthZ+l1UkPV3qqarqrpqampUeuVJI1gWVfLVNXrwDeBbcD6JOta10bgcNueAzYBtP73Aq+Oo1hJ0mhGuVpmKsn6tv0O4KPAQeAx4MY2bCfwYNve3/Zp/Y9W1Uln7pKkyVm39BAuBfYlOYfBD4P7quqhJN8Gvprkl4Gngbvb+LuBLyaZZXDGfvME6pYkncaS4V5VzwIfGtL+IoP198XtPwBuGkt1kqQz4jtUJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHDHdJ6pDhLkkdMtwlqUOj/A3VTUkeS3IwyfNJPtnaL0jySJIX2v35rT1J7kwym+TZJFsn/SQkSW82ypn7ceCfVdWPAduA25J8ANgDHKiqLcCBtg9wDbCl3XYDd429aknSaS0Z7lV1pKqeatt/BBwENgA7gH1t2D7ghra9A7inBh4H1ie5dOyVS5JOaVlr7kk2M/hj2U8Al1TVERj8AAAubsM2AIcWPGyutS3+WruTzCSZmZ+fX37lkqRTGjnck7wb+HXgU1X1/dMNHdJWJzVU7a2q6aqanpqaGrUMSdIIRgr3JOcyCPYvVdXXWvMrJ5Zb2v3R1j4HbFrw8I3A4fGUK0kaxShXywS4GzhYVb+yoGs/sLNt7wQeXNB+S7tqZhtw7MTyjSRpdawbYcyVwMeBbyV5prX9InA7cF+SXcDLwE2t72HgWmAWeAO4dawVS5KWtGS4V9V/Y/g6OsD2IeMLuG2FdUmSVsB3qEpShwx3SeqQ4S5JHTLcJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkOEuSR0y3CWpQ4a7JHXIcJekDhnuktQhw12SOmS4S1KHRvkbql9IcjTJcwvaLkjySJIX2v35rT1J7kwym+TZJFsnWbwkabhRztz/I3D1orY9wIGq2gIcaPsA1wBb2m03cNd4ypQkLceS4V5Vvw28uqh5B7Cvbe8DbljQfk8NPA6sT3LpuIqVJI3mTNfcL6mqIwDt/uLWvgE4tGDcXGs7SZLdSWaSzMzPz59hGZKkYcb9gmqGtNWwgVW1t6qmq2p6ampqzGVI0l9sZxrur5xYbmn3R1v7HLBpwbiNwOEzL0+SdCbONNz3Azvb9k7gwQXtt7SrZrYBx04s30iSVs+6pQYk+QrwEeCiJHPAZ4HbgfuS7AJeBm5qwx8GrgVmgTeAWydQsyRpCUuGe1V97BRd24eMLeC2lRYlSVoZ36EqSR0y3CWpQ4a7JHXIcJekDhnuktShJa+Wkf4i27zn62t27Jduv27Njq23Ps/cJalDhrskdchwl6QOGe6S1CHDXZI6ZLhLUocMd0nqkNe5vwV57bWkpXjmLkkdMtwlqUOGuyR1yHCXpA5NJNyTXJ3ku0lmk+yZxDEkSac29nBPcg7w74BrgA8AH0vygXEfR5J0apO4FPIKYLaqXgRI8lVgB/DtCRzLywIlaYhU1Xi/YHIjcHVV/Wzb/zjwt6rq5xaN2w3sbrvvB757hoe8CPjDM3zsJFnX8ljX8p2ttVnX8qykrr9aVVPDOiZx5p4hbSf9BKmqvcDeFR8smamq6ZV+nXGzruWxruU7W2uzruWZVF2TeEF1Dti0YH8jcHgCx5EkncIkwv13gS1JLktyHnAzsH8Cx5EkncLYl2Wq6niSnwP+C3AO8IWqen7cx1lgxUs7E2Jdy2Ndy3e21mZdyzORusb+gqokae35DlVJ6pDhLkkdekuEe5IvJDma5LlT9CfJne3jDp5NsvUsqesjSY4leabd/sUq1bUpyWNJDiZ5Psknh4xZ9Tkbsa5Vn7Mkb0/yO0l+r9X1S0PGvC3JvW2+nkiy+Syp6xNJ5hfM189Ouq4Fxz4nydNJHhrSt+rzNWJdazlfLyX5VjvuzJD+8X5PVtVZfwM+DGwFnjtF/7XAbzK4xn4b8MRZUtdHgIfWYL4uBba27fcA/x34wFrP2Yh1rfqctTl4d9s+F3gC2LZozD8Gfq1t3wzce5bU9Qng3672/7F27E8DXx7277UW8zViXWs5Xy8BF52mf6zfk2+JM/eq+m3g1dMM2QHcUwOPA+uTXHoW1LUmqupIVT3Vtv8IOAhsWDRs1edsxLpWXZuDP26757bb4isNdgD72vb9wPYkw96wt9p1rYkkG4HrgM+fYsiqz9eIdZ3Nxvo9+ZYI9xFsAA4t2J/jLAiN5ifbr9W/meRvrPbB26/DH2Jw1rfQms7ZaeqCNZiz9qv8M8BR4JGqOuV8VdVx4Bhw4VlQF8DPtF/j70+yaUj/JPwq8AvAn52if03ma4S6YG3mCwY/mH8ryZMZfPzKYmP9nuwl3Ef6yIM18BSDz374IPBvgP+8mgdP8m7g14FPVdX3F3cPeciqzNkSda3JnFXVn1bV5QzeUX1Fkh9fNGRN5muEun4D2FxVfxP4r/zwbHlikvw0cLSqnjzdsCFtE52vEeta9fla4Mqq2srgE3NvS/LhRf1jnbNewv2s/MiDqvr+iV+rq+ph4NwkF63GsZOcyyBAv1RVXxsyZE3mbKm61nLO2jFfB74JXL2o68/nK8k64L2s4pLcqeqqqu9V1Z+03X8P/MQqlHMlcH2Sl4CvAlcl+U+LxqzFfC1Z1xrN14ljH273R4EHGHyC7kJj/Z7sJdz3A7e0V5u3Aceq6shaF5XkL51YZ0xyBYP5/t4qHDfA3cDBqvqVUwxb9Tkbpa61mLMkU0nWt+13AB8FvrNo2H5gZ9u+EXi02qtga1nXojXZ6xm8jjFRVfWZqtpYVZsZvFj6aFX9/UXDVn2+RqlrLearHfddSd5zYhv4KWDxVXZj/Z6cxKdCjl2SrzC4iuKiJHPAZxm8uERV/RrwMINXmmeBN4Bbz5K6bgT+UZLjwP8Bbp70f/DmSuDjwLfaei3ALwJ/ZUFtazFno9S1FnN2KbAvgz808yPAfVX1UJJ/CcxU1X4GP5S+mGSWwRnozROuadS6fj7J9cDxVtcnVqGuoc6C+RqlrrWar0uAB9p5yzrgy1X1jST/ECbzPenHD0hSh3pZlpEkLWC4S1KHDHdJ6pDhLkkdMtwlqUOGuyR1yHCXpA79f+rupuvijn1SAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.hist([o.count(1) for o in outs])" ] }, { "cell_type": "code", "execution_count": 788, "metadata": {}, "outputs": [], "source": [ "# where there are only 2 or 3 \"1s\"" ] }, { "cell_type": "code", "execution_count": 789, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[14, 18, 20, 21, 22],\n", " [14, 19, 20, 21, 22]])" ] }, "execution_count": 789, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cover[ np.array(list(range(len(outs))))[np.array([o.count(1) for o in outs]) == 1] ]" ] }, { "cell_type": "code", "execution_count": 813, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[11,15,19,20,22],\n", "[15, 19, 20, 22]\n", "[11, 19, 20, 22]\n", "[11, 15, 19, 22]\n", "[12,14,19,20,22],\n", "[12, 19, 20, 22]\n", "[12, 14, 20, 22]\n", "[12, 14, 19, 22]\n", "[14,19,20,21,22],\n", "[19, 20, 21, 22]\n" ] } ], "source": [ "# loose groupings\n", "todo = cover[ np.array(list(range(len(outs))))[np.array([o.count(1) for o in outs]) <= 3]]\n", "for testval in todo:\n", " if set({19, 20, 22}).issubset(testval):\n", " print('[' + ','.join([str(i) for i in testval]) + '],')\n", " testval = list(testval)\n", " for i in range(len(testval)):\n", " concat = testval[:i] + testval[i+1:]\n", " matches = [set(s) for s in cover if (set(concat).issubset(s))]\n", " if len(matches) == 1:\n", " print(concat)" ] }, { "cell_type": "raw", "metadata": {}, "source": [ "1,4,6,10,11,13,15\n", "[1, 6, 10, 11, 13, 15]\n", "1,4,8,10,11,13,15\n", "[1, 8, 10, 11, 13, 15]" ] }, { "cell_type": "code", "execution_count": 792, "metadata": {}, "outputs": [], "source": [ "to_remove = [\n", "[14,18,20,21,22],\n", " [14,19,20,21,22],\n", "]" ] }, { "cell_type": "code", "execution_count": 793, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "trying: [14, 18, 20, 21, 22]\n", "[18, 20, 21, 22]\n", "trying: [14, 19, 20, 21, 22]\n", "[19, 20, 21, 22]\n" ] } ], "source": [ "# loose groupings\n", "for testval in to_remove:\n", " print('trying:', testval)\n", " testval = list(testval)\n", " for i in range(len(testval)):\n", " matches = [set(s) for s in cover if (set(testval[:i] + testval[i+1:]).issubset(s))]\n", " if len(matches) == 1:\n", " print(testval[:i] + testval[i+1:])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "ah, but removing many of them might remove double / triple covers..." ] }, { "cell_type": "code", "execution_count": 794, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1573" ] }, "execution_count": 794, "metadata": {}, "output_type": "execute_result" } ], "source": [ "newcover = cover.copy()\n", "len(newcover)" ] }, { "cell_type": "code", "execution_count": 795, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1565\n", "1565\n" ] } ], "source": [ "for old in to_remove:\n", " assert 1 == sum(np.all(newcover == old, axis=1))\n", " idx = np.array(list(range(len(newcover))))[np.all(newcover == old, axis=1)][0]\n", " print(idx)\n", " newcover = np.delete(newcover, idx, 0)" ] }, { "cell_type": "code", "execution_count": 796, "metadata": {}, "outputs": [], "source": [ "# to_add = [\n", "# [1,3,6,8,10,4,13,15,16],\n", "# [3,6,8,10,11,4,13,15,16]\n", "# ]\n", "# newcover = np.concatenate((newcover, to_add))" ] }, { "cell_type": "code", "execution_count": 797, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1571" ] }, "execution_count": 797, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(newcover)" ] }, { "cell_type": "code", "execution_count": 801, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7315\n", "0\n", "1000\n", "2000\n", "3000\n", "4000\n", "5000\n", "6000\n", "7000\n", "CPU times: user 14 s, sys: 12 ms, total: 14 s\n", "Wall time: 14 s\n" ] } ], "source": [ "%%time\n", "c = Counter()\n", "d = {}\n", "t = 4\n", "sets = [set(i) for i in list(itertools.combinations(range(1, v+1), t))]\n", "print(len(sets))\n", "for idx, p in enumerate(sets):\n", " if idx % 1000 == 0:\n", " print(idx)\n", " ct = sum([p.issubset(r) for r in newcover])\n", " c[ct] += 1\n", " if ct not in d:\n", " d[ct] = []\n", " d[ct].append(p)\n", "# print(p, ct)" ] }, { "cell_type": "code", "execution_count": 802, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 802, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAASlklEQVR4nO3cYYxd5X3n8e8vODQtbWoTBoRsa01VK1u6UoAdGSqkqBu3xpAo5kWQiHaDhbzyvqBVol2pS/rGKjQSfdN0kbZIFnbXdNNQLynCSlGo5STq9gWEIVAScFi7lOKRKZ7WhjRFTUT63xfzOLmGmbl3YHyvnef7ka7OOf/znDv/g9DvHj/33JOqQpLUh/dMugFJ0vgY+pLUEUNfkjpi6EtSRwx9SerIqkk3sJRLLrmkNmzYMOk2JOm88tRTT/1DVU0ttO+cDv0NGzYwMzMz6TYk6byS5O8W2+f0jiR1xNCXpI4MDf0kH0zyzMDru0k+k+TiJAeTHGnLNW18ktyb5GiSZ5NcM/Be29v4I0m2n80TkyS93dDQr6oXquqqqroK+PfAG8DDwJ3AoaraCBxq2wA3AhvbaydwH0CSi4FdwLXAJmDX6Q8KSdJ4LHd6ZzPwN1X1d8A2YF+r7wNubuvbgAdq3uPA6iSXAzcAB6vqZFWdAg4CW9/1GUiSRrbc0L8V+GJbv6yqXgFoy0tbfS1wbOCY2VZbrH6GJDuTzCSZmZubW2Z7kqSljBz6SS4EPg78n2FDF6jVEvUzC1W7q2q6qqanpha8zVSS9A4t50r/RuCbVfVq2361TdvQlidafRZYP3DcOuD4EnVJ0pgsJ/Q/yY+ndgAOAKfvwNkOPDJQv63dxXMd8Hqb/nkM2JJkTfsCd0urSZLGZKRf5Cb5GeDXgf8yUL4H2J9kB/AycEurPwrcBBxl/k6f2wGq6mSSu4En27i7qurkuz6DnyAb7vzzSbdwhpfu+eikW5C0wkYK/ap6A/jAW2r/yPzdPG8dW8Adi7zPXmDv8tuUJK0Ef5ErSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1JGRQj/J6iQPJflOksNJfiXJxUkOJjnSlmva2CS5N8nRJM8muWbgfba38UeSbD9bJyVJWtioV/r/A/hKVf1b4EPAYeBO4FBVbQQOtW2AG4GN7bUTuA8gycXALuBaYBOw6/QHhSRpPIaGfpL3Ax8G9gBU1Q+q6jVgG7CvDdsH3NzWtwEP1LzHgdVJLgduAA5W1cmqOgUcBLau6NlIkpY0ypX+LwBzwB8leTrJ/UkuAi6rqlcA2vLSNn4tcGzg+NlWW6x+hiQ7k8wkmZmbm1v2CUmSFjdK6K8CrgHuq6qrgX/mx1M5C8kCtVqifmahandVTVfV9NTU1AjtSZJGNUrozwKzVfVE236I+Q+BV9u0DW15YmD8+oHj1wHHl6hLksZkaOhX1d8Dx5J8sJU2A88DB4DTd+BsBx5p6weA29pdPNcBr7fpn8eALUnWtC9wt7SaJGlMVo047jeBLyS5EHgRuJ35D4z9SXYALwO3tLGPAjcBR4E32liq6mSSu4En27i7qurkipyFJGkkI4V+VT0DTC+wa/MCYwu4Y5H32QvsXU6DkqSV4y9yJakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjoyUugneSnJt5I8k2Sm1S5OcjDJkbZc0+pJcm+So0meTXLNwPtsb+OPJNl+dk5JkrSY5Vzp/4equqqqptv2ncChqtoIHGrbADcCG9trJ3AfzH9IALuAa4FNwK7THxSSpPF4N9M724B9bX0fcPNA/YGa9ziwOsnlwA3Awao6WVWngIPA1nfx9yVJyzRq6BfwF0meSrKz1S6rqlcA2vLSVl8LHBs4drbVFqufIcnOJDNJZubm5kY/E0nSUKtGHHd9VR1PcilwMMl3lhibBWq1RP3MQtVuYDfA9PT02/ZLkt65ka70q+p4W54AHmZ+Tv7VNm1DW55ow2eB9QOHrwOOL1GXJI3J0NBPclGSnzu9DmwBvg0cAE7fgbMdeKStHwBua3fxXAe83qZ/HgO2JFnTvsDd0mqSpDEZZXrnMuDhJKfH/0lVfSXJk8D+JDuAl4Fb2vhHgZuAo8AbwO0AVXUyyd3Ak23cXVV1csXORJI01NDQr6oXgQ8tUP9HYPMC9QLuWOS99gJ7l9+mJGkl+ItcSeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI6MHPpJLkjydJIvt+0rkjyR5EiSP01yYav/VNs+2vZvGHiPz7b6C0luWOmTkSQtbTlX+p8GDg9s/x7w+araCJwCdrT6DuBUVf0i8Pk2jiRXArcCvwxsBf4wyQXvrn1J0nKMFPpJ1gEfBe5v2wE+AjzUhuwDbm7r29o2bf/mNn4b8GBVfb+q/hY4CmxaiZOQJI1m1Cv9PwB+C/jXtv0B4LWqerNtzwJr2/pa4BhA2/96G/+j+gLH/EiSnUlmkszMzc0t41QkScMMDf0kHwNOVNVTg+UFhtaQfUsd8+NC1e6qmq6q6ampqWHtSZKWYdUIY64HPp7kJuB9wPuZv/JfnWRVu5pfBxxv42eB9cBsklXAzwMnB+qnDR4jSRqDoVf6VfXZqlpXVRuY/yL2q1X1H4GvAZ9ow7YDj7T1A22btv+rVVWtfmu7u+cKYCPwjRU7E0nSUKNc6S/mvwMPJvld4GlgT6vvAf44yVHmr/BvBaiq55LsB54H3gTuqKofvou/L0lapmWFflV9Hfh6W3+RBe6+qap/AW5Z5PjPAZ9bbpOSpJXhL3IlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOjI09JO8L8k3kvx1kueS/E6rX5HkiSRHkvxpkgtb/afa9tG2f8PAe3221V9IcsPZOilJ0sJGudL/PvCRqvoQcBWwNcl1wO8Bn6+qjcApYEcbvwM4VVW/CHy+jSPJlcCtwC8DW4E/THLBSp6MJGlpQ0O/5n2vbb63vQr4CPBQq+8Dbm7r29o2bf/mJGn1B6vq+1X1t8BRYNOKnIUkaSQjzeknuSDJM8AJ4CDwN8BrVfVmGzILrG3ra4FjAG3/68AHBusLHDP4t3YmmUkyMzc3t/wzkiQtaqTQr6ofVtVVwDrmr85/aaFhbZlF9i1Wf+vf2l1V01U1PTU1NUp7kqQRLevunap6Dfg6cB2wOsmqtmsdcLytzwLrAdr+nwdODtYXOEaSNAaj3L0zlWR1W/9p4NeAw8DXgE+0YduBR9r6gbZN2//VqqpWv7Xd3XMFsBH4xkqdiCRpuFXDh3A5sK/dafMeYH9VfTnJ88CDSX4XeBrY08bvAf44yVHmr/BvBaiq55LsB54H3gTuqKofruzpSJKWMjT0q+pZ4OoF6i+ywN03VfUvwC2LvNfngM8tv01J0krwF7mS1BFDX5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHRka+knWJ/laksNJnkvy6Va/OMnBJEfack2rJ8m9SY4meTbJNQPvtb2NP5Jk+9k7LUnSQka50n8T+G9V9UvAdcAdSa4E7gQOVdVG4FDbBrgR2NheO4H7YP5DAtgFXAtsAnad/qCQJI3H0NCvqleq6ptt/Z+Aw8BaYBuwrw3bB9zc1rcBD9S8x4HVSS4HbgAOVtXJqjoFHAS2rujZSJKWtKw5/SQbgKuBJ4DLquoVmP9gAC5tw9YCxwYOm221xeqSpDEZOfST/CzwJeAzVfXdpYYuUKsl6m/9OzuTzCSZmZubG7U9SdIIRgr9JO9lPvC/UFV/1sqvtmkb2vJEq88C6wcOXwccX6J+hqraXVXTVTU9NTW1nHORJA0xyt07AfYAh6vq9wd2HQBO34GzHXhkoH5bu4vnOuD1Nv3zGLAlyZr2Be6WVpMkjcmqEcZcD3wK+FaSZ1rtt4F7gP1JdgAvA7e0fY8CNwFHgTeA2wGq6mSSu4En27i7qurkipyFJGkkQ0O/qv6KhefjATYvML6AOxZ5r73A3uU0KElaOf4iV5I6YuhLUkcMfUnqiKEvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdWRo6CfZm+REkm8P1C5OcjDJkbZc0+pJcm+So0meTXLNwDHb2/gjSbafndORJC1llCv9/wVsfUvtTuBQVW0EDrVtgBuBje21E7gP5j8kgF3AtcAmYNfpDwpJ0vgMDf2q+kvg5FvK24B9bX0fcPNA/YGa9ziwOsnlwA3Awao6WVWngIO8/YNEknSWvdM5/cuq6hWAtry01dcCxwbGzbbaYvW3SbIzyUySmbm5uXfYniRpISv9RW4WqNUS9bcXq3ZX1XRVTU9NTa1oc5LUu3ca+q+2aRva8kSrzwLrB8atA44vUZckjdE7Df0DwOk7cLYDjwzUb2t38VwHvN6mfx4DtiRZ077A3dJqkqQxWjVsQJIvAr8KXJJklvm7cO4B9ifZAbwM3NKGPwrcBBwF3gBuB6iqk0nuBp5s4+6qqrd+OSxJOsuGhn5VfXKRXZsXGFvAHYu8z15g77K6kyStKH+RK0kdMfQlqSOGviR1xNCXpI4Y+pLUEUNfkjpi6EtSRwx9SeqIoS9JHTH0Jakjhr4kdWTos3ekpWy4888n3cIZXrrno5NuQTqneaUvSR0x9CWpI4a+JHXE0Jekjhj6ktQRQ1+SOmLoS1JHDH1J6oihL0kdGXvoJ9ma5IUkR5PcOe6/L0k9G2voJ7kA+J/AjcCVwCeTXDnOHiSpZ+N+9s4m4GhVvQiQ5EFgG/D8mPuQdBadj89kOh97fidSVWfljRf8Y8kngK1V9Z/b9qeAa6vqNwbG7AR2ts0PAi+MrcGFXQL8w4R7WC57Ho/zrefzrV+w53fq31TV1EI7xn2lnwVqZ3zqVNVuYPd42hkuyUxVTU+6j+Ww5/E433o+3/oFez4bxv1F7iywfmB7HXB8zD1IUrfGHfpPAhuTXJHkQuBW4MCYe5Ckbo11eqeq3kzyG8BjwAXA3qp6bpw9vAPnzFTTMtjzeJxvPZ9v/YI9r7ixfpErSZosf5ErSR0x9CWpI4b+Es63R0Yk2ZvkRJJvT7qXUSVZn+RrSQ4neS7Jpyfd01KSvC/JN5L8dev3dybd06iSXJDk6SRfnnQvo0jyUpJvJXkmycyk+xlFktVJHkrynfb/9K9Muqe3ck5/Ee2REf8P+HXmbzV9EvhkVZ2zvx5O8mHge8ADVfXvJt3PKJJcDlxeVd9M8nPAU8DN5+p/5yQBLqqq7yV5L/BXwKer6vEJtzZUkv8KTAPvr6qPTbqfYZK8BExX1aR/6DSyJPuA/1tV97c7FH+mql6bdF+DvNJf3I8eGVFVPwBOPzLinFVVfwmcnHQfy1FVr1TVN9v6PwGHgbWT7WpxNe97bfO97XXOXzklWQd8FLh/0r38pEryfuDDwB6AqvrBuRb4YOgvZS1wbGB7lnM4jH4SJNkAXA08MdlOltamSZ4BTgAHq+qc7rf5A+C3gH+ddCPLUMBfJHmqPZ7lXPcLwBzwR20a7f4kF026qbcy9Bc39JERWjlJfhb4EvCZqvrupPtZSlX9sKquYv4X5ZuSnNNTaUk+Bpyoqqcm3csyXV9V1zD/VN472vTluWwVcA1wX1VdDfwzcM59F2joL85HRoxJmxv/EvCFqvqzSfczqvZP968DWyfcyjDXAx9vc+QPAh9J8r8n29JwVXW8LU8ADzM/5XoumwVmB/7l9xDzHwLnFEN/cT4yYgzaF6N7gMNV9fuT7meYJFNJVrf1nwZ+DfjOZLtaWlV9tqrWVdUG5v8//mpV/acJt7WkJBe1L/ZpUyRbgHP6rrSq+nvgWJIPttJmzsHHxo/7KZvnjfPxkRFJvgj8KnBJkllgV1XtmWxXQ10PfAr4VpsnB/jtqnp0gj0t5XJgX7u76z3A/qo6L26BPM9cBjw8f03AKuBPquork21pJL8JfKFdKL4I3D7hft7GWzYlqSNO70hSRwx9SeqIoS9JHTH0Jakjhr4kdcTQl6SOGPqS1JH/DwMsa9/rgCRCAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.bar(c.keys(), c.values())" ] }, { "cell_type": "code", "execution_count": 803, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 803, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c[0]" ] }, { "cell_type": "code", "execution_count": 804, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{14, 20, 21, 22}, {18, 20, 21, 22}, {19, 20, 21, 22}]" ] }, "execution_count": 804, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d[0]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "another strategy:" ] }, { "cell_type": "code", "execution_count": 280, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "trying: {1, 2, 3, 4, 5, 6, 14}\n", "[1, 3, 4, 5, 6, 14]\n", "[1, 2, 3, 5, 6, 14]\n", "[1, 2, 3, 4, 6, 14]\n", "trying: {1, 2, 3, 4, 5, 11, 14}\n", "[1, 3, 4, 5, 11, 14]\n", "[1, 2, 3, 5, 11, 14]\n", "[1, 2, 3, 4, 11, 14]\n", "trying: {2, 3, 4, 5, 6, 8, 14}\n", "[2, 3, 4, 5, 8, 14]\n", "[2, 3, 4, 5, 6, 8]\n", "trying: {2, 3, 4, 5, 7, 11, 14}\n", "[3, 4, 5, 7, 11, 14]\n", "[2, 4, 5, 7, 11, 14]\n", "[2, 3, 5, 7, 11, 14]\n", "[2, 3, 4, 7, 11, 14]\n", "[2, 3, 4, 5, 7, 14]\n", "[2, 3, 4, 5, 7, 11]\n", "trying: {2, 3, 4, 5, 9, 11, 14}\n", "[3, 4, 5, 9, 11, 14]\n", "[2, 4, 5, 9, 11, 14]\n", "[2, 3, 5, 9, 11, 14]\n", "[2, 3, 4, 9, 11, 14]\n", "[2, 3, 4, 5, 9, 14]\n", "[2, 3, 4, 5, 9, 11]\n", "trying: {2, 3, 4, 5, 10, 11, 14}\n", "[3, 4, 5, 10, 11, 14]\n", "[2, 4, 5, 10, 11, 14]\n", "[2, 3, 5, 10, 11, 14]\n", "[2, 3, 4, 10, 11, 14]\n", "[2, 3, 4, 5, 10, 14]\n", "[2, 3, 4, 5, 10, 11]\n", "trying: {2, 3, 4, 5, 11, 12, 14}\n", "[3, 4, 5, 11, 12, 14]\n", "[2, 4, 5, 11, 12, 14]\n", "[2, 3, 5, 11, 12, 14]\n", "[2, 3, 4, 11, 12, 14]\n", "[2, 3, 4, 5, 12, 14]\n", "[2, 3, 4, 5, 11, 12]\n", "trying: {2, 3, 4, 5, 11, 13, 14}\n", "[3, 4, 5, 11, 13, 14]\n", "[2, 4, 5, 11, 13, 14]\n", "[2, 3, 5, 11, 13, 14]\n", "[2, 3, 4, 11, 13, 14]\n", "[2, 3, 4, 5, 13, 14]\n", "[2, 3, 4, 5, 11, 13]\n", "trying: {2, 3, 4, 5, 11, 14, 15}\n", "[3, 4, 5, 11, 14, 15]\n", "[2, 4, 5, 11, 14, 15]\n", "[2, 3, 5, 11, 14, 15]\n", "[2, 3, 4, 11, 14, 15]\n", "[2, 3, 4, 5, 14, 15]\n", "[2, 3, 4, 5, 11, 15]\n" ] } ], "source": [ "# related groupings\n", "todo = [set(s) for s in cover if (set([2, 3, 4, 5, 14]).issubset(s))]\n", "for testval in todo:\n", " print('trying:', testval)\n", " testval = list(testval)\n", " for i in range(len(testval)):\n", " matches = [set(s) for s in cover if (set(testval[:i] + testval[i+1:]).issubset(s))]\n", " if len(matches) == 1:\n", " print(testval[:i] + testval[i+1:])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "1,2,6,11,17,20" ] }, { "cell_type": "code", "execution_count": 139, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[3, 9, 10, 15, 16, 18, 19],\n", " [5, 9, 10, 15, 16, 18, 19],\n", " [6, 9, 10, 15, 16, 18, 19],\n", " [7, 9, 10, 15, 16, 18, 19],\n", " [9, 10, 13, 15, 16, 18, 19]]" ] }, "execution_count": 139, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sorted([list(s) for s in cover if set({9, 10, 15, 16, 18, 19}).issubset(s)])" ] }, { "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.4" } }, "nbformat": 4, "nbformat_minor": 4 }