Power Set Computation

readme.md

Computation of the Power Set of a Set

Given a set V compute its power set

sol.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "PowerSet20200801.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "L7szBMUBer-X",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\n",
        "def power_set(v): \n",
        "  if len(v)==0: return []\n",
        "  if len(v)==1: return [[], [v[0]]]\n",
        "  res = []\n",
        "  for i in range(len(v)-1): \n",
        "    temp = power_set(v[i+1:])\n",
        "    for e in temp: \n",
        "      t1 = e.copy()\n",
        "      t1.insert(0, v[i])\n",
        "      res.insert(0, t1)\n",
        "  return temp + res\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8D8uvUjSfM_x",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def print_ordered(v): \n",
        "  N = 0 \n",
        "  temp = len(v)\n",
        "  while temp>1: \n",
        "    N += 1\n",
        "    temp = temp / 2\n",
        "  for i in range(N+1): \n",
        "    res = \"\"\n",
        "    for e in v: \n",
        "      if len(e) == i: res += f\"{e},\"\n",
        "    print(res)\n"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "W28Lxl1Mexa0",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "aa1de301-2465-4416-9dfd-51bd6d27c1c9"
      },
      "source": [
        "print_ordered(power_set(range(1,4)))"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[],\n",
            "[3],[2],[1],\n",
            "[2, 3],[1, 2],[1, 3],\n",
            "[1, 2, 3],\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "svy9w0oGey6B",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "678724be-d550-4e28-b725-7c1e1a1a3794"
      },
      "source": [
        "print_ordered(power_set(range(1,5)))"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[],\n",
            "[4],[3],[2],[1],\n",
            "[3, 4],[2, 3],[2, 4],[1, 2],[1, 3],[1, 4],\n",
            "[2, 3, 4],[1, 2, 4],[1, 2, 3],[1, 3, 4],\n",
            "[1, 2, 3, 4],\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "klaPQxEsfFnc",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 119
        },
        "outputId": "95839d4e-ade8-47f1-8383-41e54cec6689"
      },
      "source": [
        "print_ordered(power_set(range(1,6)))"
      ],
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[],\n",
            "[5],[4],[3],[2],[1],\n",
            "[4, 5],[3, 4],[3, 5],[2, 3],[2, 4],[2, 5],[1, 2],[1, 3],[1, 4],[1, 5],\n",
            "[3, 4, 5],[2, 3, 5],[2, 3, 4],[2, 4, 5],[1, 2, 5],[1, 2, 4],[1, 2, 3],[1, 3, 5],[1, 3, 4],[1, 4, 5],\n",
            "[2, 3, 4, 5],[1, 2, 4, 5],[1, 2, 3, 4],[1, 2, 3, 5],[1, 3, 4, 5],\n",
            "[1, 2, 3, 4, 5],\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tqFsXcvEfG1K",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}