D-optimal-01-seqs.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def int_to_seq(i, N):\n",
    "    bitstr = \"{:0{width}b}\".format(i, width=N)\n",
    "    return [int(c) for c in bitstr]\n",
    "\n",
    "def all_01_seqs(N = 3):\n",
    "    return (int_to_seq(i, N) for i in range(2 ** N))\n",
    "\n",
    "def all_01_seqpairs(N = 3):\n",
    "    return ((a,b) for a in all_01_seqs(N) for b in all_01_seqs(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from lib import paf\n",
    "\n",
    "def paf_invariant(A, B):\n",
    "    assert len(A) == len(B), \"len mismatch\"\n",
    "    N = len(A)\n",
    "    for i in range(1, 1 + (N-1)//2):\n",
    "        comp = 2 * (paf(A, i) + paf(B, i) - sum(A) - sum(B)) + N\n",
    "        if comp != 1: return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N = 3 -> found 24 D-optimal pairs out of 64 total pairs.\n",
      "N = 5 -> found 100 D-optimal pairs out of 1024 total pairs.\n",
      "N = 7 -> found 784 D-optimal pairs out of 16384 total pairs.\n",
      "N = 9 -> found 3888 D-optimal pairs out of 262144 total pairs.\n"
     ]
    }
   ],
   "source": [
    "for n in [3, 5, 7, 9]:\n",
    "    dopt_pairs = [(a, b) for a, b in all_01_seqpairs(n) if paf_invariant(a, b)]\n",
    "    found = len(dopt_pairs)\n",
    "    possible = (2 ** n) ** 2\n",
    "    print(\"N = {} -> found {} D-optimal pairs out of {} total pairs.\".format(n, found, possible))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "from math import ceil\n",
    "\n",
    "def doptimal(A, B):\n",
    "    N = len(A)\n",
    "    lags = 0\n",
    "    sumA, sumB = sum(A), sum(B)\n",
    "    for i in range(1, N):  # 1 to N-1\n",
    "        lag_term = 2 * (paf(A, i) + paf(B, i) - sumA - sumB) + N - 1\n",
    "        lags += abs(lag_term)\n",
    "    \n",
    "    return (1 + ceil(lags/(N**2))) % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N = 3 -> found 24 D-optimal pairs out of 64 total pairs.\n",
      "N = 5 -> found 100 D-optimal pairs out of 1024 total pairs.\n",
      "N = 7 -> found 784 D-optimal pairs out of 16384 total pairs.\n",
      "N = 9 -> found 3888 D-optimal pairs out of 262144 total pairs.\n"
     ]
    }
   ],
   "source": [
    "for n in [3, 5, 7, 9]:\n",
    "    dopt_pairs = [(a, b) for a, b in all_01_seqpairs(n) if doptimal(a, b) == 1]\n",
    "    found = len(dopt_pairs)\n",
    "    possible = (2 ** n) ** 2\n",
    "    print(\"N = {} -> found {} D-optimal pairs out of {} total pairs.\".format(n, found, possible))"
   ]
  }
 ],
 "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.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}