day 91 - variations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import randrange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ffact(n, k, _cache={}):\n",
    "    if (n, k) not in _cache:\n",
    "        f = 1\n",
    "        for i in range(k):\n",
    "            f *= n - i\n",
    "        \n",
    "        _cache[n, k] = f\n",
    "        \n",
    "    return _cache[n, k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def variation_to_order(variation):\n",
    "    alphabet = list('0123456789')\n",
    "    n = len(variation)\n",
    "\n",
    "    order = 1\n",
    "    order -= ffact(9, n - 1)\n",
    "    for i in range(1, n):\n",
    "        order += ffact(10, i) - ffact(9, i - 1)\n",
    "\n",
    "    for i in range(n):\n",
    "        index = alphabet.index(variation[i])\n",
    "        order += index * ffact(9 - i, n - i - 1)\n",
    "        del alphabet[index]\n",
    "\n",
    "    return order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def order_to_variation(order):\n",
    "    for n in range(1, 11):\n",
    "        k = ffact(10, n) - ffact(9, n - 1)\n",
    "        if k >= order:\n",
    "            break\n",
    "        order -= k\n",
    "\n",
    "    order -= (n != 1)\n",
    "    alphabet = list('0123456789')\n",
    "    variation = ''\n",
    "\n",
    "    for i in range(n):\n",
    "        k = ffact(9 - i, n - i - 1)\n",
    "        index = order // k + (i == 0) - (n == 1)\n",
    "        order %= k\n",
    "        variation += alphabet[index]\n",
    "        del alphabet[index]\n",
    "\n",
    "    return variation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8877690"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "variation_to_order('9876543210')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " variation    order\n",
      " 598604732 ## 4158906\n",
      " 594216380 ## 4141709\n",
      "  63270914 ## 1687099\n",
      "2486703591 ## 6129220\n",
      " 948073165 ## 5446104\n",
      "  72149586 ## 1845426\n",
      "5647981230 ## 7288636\n",
      "3249076158 ## 6432655\n",
      "2768310954 ## 6245640\n",
      "9312078654 ## 8641626\n"
     ]
    }
   ],
   "source": [
    "print(' variation    order')\n",
    "for _ in range(10):\n",
    "    i = randrange(8877691)\n",
    "    variation = order_to_variation(i)\n",
    "    order = variation_to_order(variation)\n",
    "    assert i == order\n",
    "    print('%10s ## %d' % (variation, order))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}