
hPc           @   s  d  d l  Z  d  d l Z d  d l Z d  d l Z d  d l Z d f  d     YZ d   Z d   Z d   Z d   Z	 d   Z
 d	   Z d
   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d  d l Z e d k rd e j f d     YZ e j   n  d S(   iNt   pmtc_tc           B   s   e  Z d    Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z	 d   Z
 d	   Z d
   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z RS(   c         C   sv   t  |  | k r1 t d t  |  | f   n  | d k  rP t d |   n  | |  _ d g t j |  |  _ d  S(   Ns   Images length (%d) != n (%d).i   s   n must be >= 1; got %d.i    (   t   lent   RuntimeErrort   nt   copyt   zimages(   t   selft   imagesR   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __init__   s    	c         C   sy   t  j  |  j  } | j   xV t d |  j d  D]> } | | | k r3 t d t |  j  t |  f   q3 q3 Wd  S(   Ni   s!   Not a permutation: %s.  Test: %s.(   R   R   t   sortt   rangeR   R   t   str(   R   t   testt   i(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   check_permutation'   s
    
c         C   s   |  j  | j  k S(   N(   R   (   t   at   b(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __eq__.   s    c         C   s   |  j  | j  k S(   N(   R   (   R   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __ne__1   s    c   	      C   s   |  j    } | j    } t |  } xG t d |  D]6 } | | | | k  rR d S| | | | k r4 d Sq4 W|  j } xU t d | d  D]@ } |  j | } | j | } | | k  r d S| | k r d Sq Wd S(   Ni    ii   (   t
   cycle_typeR   R
   R   R   (	   R   R   t   ctat   ctbt   mR   R   t   azit   bzi(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __cmp__:   s"    	c         C   s   |  j  | j  k r1 t d |  j  | j  f   n  t t d |  j  d  |  j   } x9 t d |  j  d  D]! } |  j | j | | j | <qj W| S(   Ns   mul() length mismatch: %d != %di   (   R   R   R    R
   R   (   R   R   t   cR   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __mul__M   s    "c         C   s[   t  t d |  j d  |  j  } x2 t d | j d  D] } | | j |  j | <q9 W| S(   Ni   (   R    R
   R   R   (   R   R   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   invU   s    "c         C   s&   | d k r t  d   n  |  j | S(   Ni    s   pmtc: zimage[0] is protected.(   R   R   (   R   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __getitem__[   s    c         C   sS   t  j  |  } x= t d t |  j   D]# } | |  j | d | | d <q( W| S(   Ni   (   R   R
   R   R   (   R   t   inputt   outputR   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   ofb   s    !c         C   s|   x5 t  d |  j d  D] } |  j | | k r | Sq Wt j d IJt j d I| IJt j d I|  IJt j d  d  S(   Ni   s    pmtc.inv_img: inverse not found.s   input       = s   permutation = (   R
   R   R   t   syst   stderrt   exit(   R   t   dstt   src(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   inv_imgm   s    c   
      C   s   d } d } |  j  } x t d | d  D]j } |  j | } xT t | d | d  D]; } |  j | } | | } | | }	 | | 9} | |	 9} qT Wq) W| | S(   Ni   (   R   R
   R   (
   R   t   numerst   denomsR   R   t   sit   jt   sjt   numert   denom(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   sgnw   s    	


c         C   s   |  j    d k r d Sd Sd  S(   Ni   i    (   R.   (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   parity   s    c         C   s   d } t  |  j  d } t j |  j  } | } x | d k r xf t d |  D]U } | | | | d k rP | | } | | d | | <| | | d <| d 7} qP qP W| d 8} q4 W| d @S(   Ni    i   (   R   R   R   R
   (   R   t   nswapR   t   imsortt   topR   t   temp(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt	   oldparity   s    
c         C   s   |  j    d k r d Sd Sd  S(   Ni    i   i(   R/   (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   oldsgn   s    c         C   s   |  j  } g  } d g | d } x t d | d  D]s } | | rJ q4 n  g  } | } d | | <x7 | | g } |  j | } | | k r Pn  d | | <qc | | g } q4 W| S(   Ni    i   (   R   R
   R   (   R   R   t   cdt   marksR   t   cyclet   next(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   cycle_decomposition   s"    	

c         C   s/   |  j    } t t |  } | j d t  | S(   Nt   reverse(   R:   t   mapR   R	   t   True(   R   R6   t   ct(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyR      s    c   
      C   s   g  } |  j  } t d | d  } t |  j d |  } t } x | s d } x8 t d | d  D]# } | j | | k ra | } Pqa qa W| d k r t } Pn  t | |  } | j | }	 |	 | j | <| | j |	 <| j |  | | } qA W| S(   Ni   i(   R   R
   R    R   t   FalseR=   t   append(
   R   t   tausR   t   id_imgst   sigmat   doneR   t   kt   tauR*   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   transposition_decomposition   s*    		c         C   s+  t  d | d  } t j d |  } t |  } | d } x | d k r| | } t j d |  } g  }	 x! | D] }
 |	 j t |
   qs Wt |	  } | d } xL | d k r | |	 d } | |	 | | |	 d <| | |	 | <| d 8} q W| d 8} q> W| d } |  j | |  |  j   d  S(   Ni    i   t   :t   ,(   R
   t   ret   splitR   R@   t   intR   R   (   R   t   cycles_stringR   R   t   cycle_stringst
   num_cyclest   cidxt   cycle_stringt   index_stringst   indicest   index_stringt   num_indicesRE   R3   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   scan   s*    



c         C   s   t  d | d  } t |  } | d } x | d k r | | } t |  } | d } xL | d k r | | d }	 | | | | | d <|	 | | | <| d 8} q[ W| d 8} q, W| d }
 |  j |
 |  |  j   d  S(   Ni    i   (   R
   R   R   R   (   R   t   cyclesR   R   RO   RP   R8   RU   RE   R3   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt
   cycle_fill  s     



c         C   s   |  j    } d } d } x | D] } t |  d k r | d 7} n q t | d  } t |  } x5 t d |  D]$ } | d 7} | t | |  7} qs W| d k r | d 7} n  | | 7} q W| d k r d } n  | S(   Ni    t    i   RI   RH   t   1(   R:   R   R   R
   (   R   R6   t   num_non_trivial_cyclest	   cd_stringR8   RQ   t	   cycle_lenR*   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __str__/  s$    
	c         C   s
   |  j    S(   N(   R^   (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   __repr__G  s    (   t   __name__t
   __module__R   R   R   R   R   R   R   R   R    R&   R.   R/   R4   R5   R:   R   RG   RV   RX   R^   R_   (    (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyR       s*   											
								#		c         C   s0   t  t d | d  |  } | j |  |  | S(   Ni   (   R    R
   RX   (   RW   R   t   obj(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   from_cycles[  s    c         C   s3   t  t d | d  |  } | j |  g |  | S(   Ni   (   R    R
   RX   (   R8   R   Rb   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt
   from_cycle`  s    c         C   sd   d } d } g  } xB |  D]: } t  | | |  } | j |  | | 7} | | 7} q Wt | |  S(   Ni    i   (   R
   R@   Rc   (   R>   R   RE   RW   t   eltR8   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   from_cycle_typef  s    
c         C   s=   t  j |   } g  } x! | D] } | j t |   q W| S(   N(   t   sackintt   ptnsR@   Rf   (   R   Rh   t   repst   ptn(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   cycle_type_repsr  s
    c         C   s   |  g  k r g  Sg  } |  d } d } xF |  D]> } | | k rL | d 7} q- | j  | | g  | } d } q- W| j  | | g  | S(   Ni    i   (   R@   (   R>   t   pairst   previoust   countt   e(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   type_to_counts}  s    

c         C   s   d } x |  D] } | | 7} q Wt  j |  } x |  D] } | | :} q7 Wt |   } x% | D] } | t  j | d  :} q^ W| S(   Ni    i   (   Rg   t	   factorialRp   (   R>   R   Ro   t   rvRl   t   pair(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   num_ct_reps  s    c         C   s   t  |   } | S(   N(   RL   (   t   params_stringR   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   params_from_string  s    c         C   s<   t  |  } t t d | d  |  } | j |  |  | S(   Ni   (   Rv   R    R
   RV   (   t   value_stringRu   R   Rb   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   from_string  s    c   
      C   s   | } t  d |  } t  d | d  } | } x^ t  d |  D]M } | | :} |  | } |  | }	 | }  | |	 d | | <| |	 =| d 8} q> Wt | |  S(   Ni    i   (   R
   R    (
   RE   R   t   nfactt   nifactR   R3   t   nit   post   rt   q(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   kth_pmtc  s    


c         C   s   t  t d |  d  |   S(   Ni   (   R    R
   (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   identity_pmtc  s    c         C   s   t  d |  d  } d } |  } xk t  d |  d  D]V } t j | | | d  } | | } | | | | <| | | <| d 7} | d 8} q3 Wt | d |   S(   Ni    i   (   R
   t   randomt   randintR    (   t   NR   t   unused_startt
   num_unusedRE   t   uR3   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt	   rand_pmtc  s    


c         C   sv   t  d |  d  } xO t  d |  d  D]: } t j d |   } | | } | | | | <| | | <q' Wt | d |   S(   Ni    i   (   R
   R   R   R    (   R   R   RE   R   R3   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   bad_rand_pmtc)  s    
c         C   s  |  d } | d } | | k  r$ d S| | k r4 d S|  d } | d } xG t  d |  D]6 } | | | | k  rv d S| | | | k rX d SqX W|  d } | d } | j }	 xU t  d |	 d  D]@ } | j | }
 | j | } |
 | k  r d S|
 | k r d Sq Wd S(   Ni   i   ii    (   R
   R   R   (   t   tat   tbt   ncat   ncbR   R   R   t   pmtat   pmtbR   R   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   pmtc_cmpC  s0    





	c         C   s   t  |   } g  } x6 |  D]. } | j   } | j | | t  |  g  q W| j t  x) t d |  D] } | | d |  | <qh Wd  S(   Ni    (   R   R   R@   R	   R   R
   (   t   listR   Rl   t   pmtR>   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt
   sort_pmtcsi  s     t   __main__t	   test_pmtcc           B   s:  e  Z d    Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z	 d   Z
 d	   Z d
   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z d   Z  d   Z! d    Z" d!   Z# RS("   c         C   s   |  j  t   t d d d g d  } Wd  QX|  j  t   t g  d  } Wd  QXt d g d  } t d d g d  } t d d d g d  } d  S(   Ni   i   i   i   i    (   t   assertRaisesR   R    (   R   t   pi(    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt	   test_ctor  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_check_permutation  s    c         C   sl   |  j  t d d d g d  t d d d g d   |  j t d d d g d  t d d d g d   d  S(   Ni   i   i   (   t   assertEqualR    t   assertNotEqual(   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_eq  s    4c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_ne  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_cmp  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_mul  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_inv  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_getitem  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_of  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_inv_mg  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_sgn  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_parity  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_oldparity  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_oldsgn  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_cycle_decomposition  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_cycle_type  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt    test_transposition_decomposition  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt	   test_scan  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_cycle_fill  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_str  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt	   test_repr  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_from_cycles  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_from_cycle  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_from_cycle_type  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_cycle_type_reps  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_type_to_counts  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_num_ct_reps  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test__params_from_string  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_from_string  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_kth_pmtc  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_identity_pmtc  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_rand_pmtc  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_pmtc_cmp"  s    c         C   s   d  S(   N(    (   R   (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   test_sort_pmtcs&  s    ($   R`   Ra   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   R   (    (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyR   {  sD   																										
								(   RJ   R   R!   R   Rg   R    Rc   Rd   Rf   Rk   Rp   Rt   Rv   Rx   R   R   R   R   R   R   t   unittestR`   t   TestCaseR   t   main(    (    (    sE   /homepages/25/d321765456/htdocs/pub_http_internet/src/sack/pmtc_tm.pyt   <module>   s*   0 @										<	!		&	