;ò TE*Fc@s…dZdddZdgd„Zd„Zd„Zdd„Zed „Zd „Zed „Z ed „Z d fd„ƒYZ dS(s×Permutations and related stuff. Provides: chose(N, i) -- number of ways of chosing i things from among N of them. factorial(n) -- number of permutations of n things, n!. unfixed(n) -- number of fixed-point-free permutations of n things; tends to n!/e. permute(seq, ind, ..., dex) -- composes permutations and applies them to seq. compose(ind, ..., dex) -- composes permutations (tolerates abbreviation). cycle(seq, [by=1]) -- shunts sequence cyclicly rightwards. order(seq, [cmp=cmp]) -- returns permutation s for which permute(seq,s) is sorted. invert(perm) -- inverts a permutation. sorted(seq), sort(seq) -- deploy some of the above. Iterator(n) -- iterator over all n! permutations of a list of length n. See individual doc strings for further details of these; see module attribute Theory for fuller discussion of permutations. Note that Numeric python's numarray infrastructure provides for quite a lot of the same things as the following. sc Permutations ============ In what follows, I'll (orthodoxly treat any natural number as synonymous with the collection of smaller ones, effectively n = range(n), and) write r@p for permute(row, p); r@p = (: r[p[i]] <- i :len(p)) Theorem (associativity): When sequences r, q, p allow formation of the composites (r@q)@p and r@(q@p), the two are equal. Proof: assert len(r@(q@p)) is len(q@p) is len(p) is len((r@q)@p) for i in len(p): assert ((r@q)@p)[i] is (r@q)[p[i]] is r[q[p[i]]] is r[(q@p)[i]] is (r@(q@p))[i] Each `is' just instanciates the definition of @ - QED. This simple algebraic truth allows us to skip the brackets and just write r@p@q and likewise for longer sequences of sequences, in so far as these allow formation of the composite. Thus permute(row, ind, ..., dex) is row@ind@...@dex. Note, however, that r@q might not be allowed even when r@(q@p) is: e.g. when r's length appears as an entry in q, but its position in q doesn't appear in p; if all other entries in q are valid indices into r, q@p's entries will all be valid indices into r. Definition: A sequence, p, is described as a permutation if it contains all the entries of range(len(p)). Note that, given its length, this leaves it with no room to repeat any of its entries. If you ever want to discuss infinite permutations, you'll need to define them explicitly as one-to-one mappings; but for finite permutations, the `pidgeon-hole principle' makes the above sum up `one-to-one' neatly. sö Inverses ======== Given a sequence, row, and a permutation, p, of the same length, row@p is described as `a permutation of' row: it contains the same entries as row but in a different order; any repeated entry in row is repeated just as often in a permutation of row; permutations of row have the same length as row. A permutation of a permutation is thus a permutation with the same length. From the definition of permute, the identity permutation of any given length is trivially a right identity: r@id == r for any sequence, r, of the given length. Likewise, for any sequence, p, of entries in id, e.g. any permutation of id, id@p == p; thus id is a left identity on permutations of id. Thus, as a binary operator on permutations of some given length, @ has, as (both left and right) identity, the range of the given length. Using q = order(p), p@q is a sorted permutation of p; so, when p is a permutation, p@q is sorted and has the same entries as p, which has the same entries as id, which is sorted; so p@q == id, making q a right-inverse for p. Theorem: If @ is an associative binary operator closed on some collection, P - i.e. for any a, b in P we have a@b in P - having an identity, id, in P - i.e. for any a in P, id@a = a = a@id - and (having) right-inverses for all elements of P, then these right-inverses also serve as left inverses. Proof: Given p in P, consider its right-inverse, q, and q's right-inverse, d: so p@q = id = q@d, whence p = p@id = p@q@d = id@d = d, so q@p = id. QED. Our composition, @, meets the preconditions of this, with P the collection of permutations with the same length as p, hence order() would, on permutations, serve as invert(). There is, however, a cheaper answer: see invert(). sb Iteration ========= To iterate over permutations it suffices to specify a well-ordering of permutations - i.e. a choice of one of them as `first', combined with a `next' opertion which will, starting from the first, iterate over all candidates. An obvious well-ordering to use is the one obtained from `lexicographic order', in which one compares two sequences by finding the first entry in which they differ and comparing those. Among permutations of any given length, this makes the identity `less than' all others, so it's our `first' permutation. Note that a reverse-sorted (big values before little ones) sequence is later than any other sequence with the same entries. To find the `next' permutation, in the lexicographic order, one must change as late a chunk of the permutation as possible. To this end, find the longest reverse-sorted tail of the permutation: no shuffling of only that can yield a later permutation, so our next permutation must bring in at least the previous entry; since the previous entry (by construction) is less than the first entry in the reverse-sorted tail, shuffling it into the tail can produce a later entry. A little thought will then reveal that we should swap it with the smallest entry in the tail bigger than it, then reverse (i.e. forward-sort) the thus-amended tail. This is the .step() method used by the Iterator() class. icCsõ|djodSny ||SWntj onXt|ƒ|df\}}|do d}nd}xx||jojy|||}Wn'tj ot |ƒ||}nX|i |ƒ|d| |f\}}}qqW||SdS(s¦Returns the number of permutations of num without fixed points. Subtracting from num!, we get the sum over 0 < i <= num of: the number of ways of chosing i things to keep fixed, times the number of ways of permuting the remaining (num-i) items without any of these staying fixed. Indeed, num! = sum(: chose(num,i) * unfixed(num-i) <- i :1+num) as every permutation of num keeps i items fixed, for some i, while permuting the remaining i items without (further) fixed points. This yields (as chose(num,i) = chose(num, num-i) and (1+num| num-i <- i |1+num) is a permutation) num! = sum(: chose(num, i) * unfixed(i) <- i :1+num) Whence, as 1 = chose(num, num) unfixed(num) = num! - sum(: chose(num,i) * unfixed(i) <- i :num) I find that unfixed(num) * e - factorial(num) gets rapidly close to 0. We get a glitch in the sequence of values at 17 and 19, arising from rounding of the floating-point product, between the initial slide towards 0 and the subsequent exact zero. Now, factorial(num) / e is sum(: pow(-1,i) * num! / i! <- i :natural) which is, in turn, sum(: pow(-1,i) * num! / i! <- i :1+num) plus something smaller than 1. So, consider any natural N for which, for each num in N, unfixed(num) = sum(: pow(-1,i)*num!/i! <- i :1+num). An example would be N = 0, since there is no num in 0 = {}. In such a case, unfixed(N) = N! - sum(: chose(N,i) * sum(: pow(-1,j)*i!/j! <- j :1+i) <- i :1+N) # n=N-i+j = N! - sum(: sum(: N! / (n-j)! * pow(-1,j) / j! <- j :n) <- n-1 :1+N) = N! - sum(: N!/n! * sum(: chose(n,j)*pow(-1,j) <- j :n) <- n-1 :N) = N! + sum(: N!/n! * pow(-1,n) <- n-1 :N) = sum(: pow(-1,i) * N! / i! <- i :1+N) Thus unfixed has this form for num=N also, so that 1+N has the same property we demanded of N and, inductively, the equation holds for all num. Furthermore, we have unfixed(N) = N*unfixed(N-1) + pow(-1,N) which gives us a nice cheap way to evaluate unfixed; which clearly indicates that unfixed(N) must grow proportional to factorial in the long run (as witnessed in the clue which lead me here, exp(-1) being the constant of proportionality). iiÿÿÿÿiiN( snumscaches IndexErrorslensNslastssignsnexts OverflowErrorslongsappend(snumscachesNsnextslastssign((s)/home/eddy/.sys/py/study/maths/permute.pysunfixed„s(*     "cGs~y|d |df\}}Wntj o |SnXx;|o3|d |df\}}t|d„|ƒ}q;W|SdS(síReturns row permuted by a sequence of indices. All arguments must be sequences. The first is the row to be permuted; each subsequent argument will be used to permute the row; entries in each argument after the first are read as indices into the preceding argument. Returns sequence with permute(row, ind, ..., dex)[i] == row[ind[...dex[i]...]], which may be understood as the composite of the sequences, read as functions (see permute.py's Theory docstring). iÿÿÿÿcCs||S(N(s_rsi(sis_r((s)/home/eddy/.sys/py/study/maths/permute.pysÝsN(sindicessanss IndexErrorslastsmap(sindicesslastsans((s)/home/eddy/.sys/py/study/maths/permute.pyspermuteËs  cGs¶yttt|ƒƒ}Wntj o |SnXt|ƒ}|iƒg}xVt |ƒD]H}x2|D]*}y||}Wqit j oqiXqiW|i|ƒq\Wt|ƒSdS(sÒComposes arbitrarily many permutations. Presumes that all arguments are permutations and interprets each as coinciding with the identity beyond its length - e.g. (1, 2, 0) is implicitly (1, 2, 0, 3, 4, 5, 6, ...) - so as to resolve any differences in length. Otherwise, functionally equivalent to permute, though implemented with the two loops rolled out the other way (to implement the identity-default behaviour by catching IndexErrors). N(smaxsmapslenspermssns ValueErrorslistsrowsreversesresultsrangesisps IndexErrorsappendstuple(spermsspsnsisresultsrow((s)/home/eddy/.sys/py/study/maths/permute.pyscomposeás$     cCs%| t|ƒ}|||| SdS(svPermutes a sequence cyclicly. Optional argument, by, has a default of 1: it is the position to which the first item in the sequence is to be moved; a portion of this length is moved from the end of the sequence to the start; all other entries in the list are moved down the list this far. For example: cycle((0, 1, 2, 3, 4), 2) yields (3, 4, 0, 1, 2). N(sbyslensrow(srowsby((s)/home/eddy/.sys/py/study/maths/permute.pyscycleùscCsGt|ƒ}|djot|ƒSn|d}gdggf\}}}xx|djoj|d}||||ƒ}|djo|i |ƒqO|djo|i |ƒqO|i |ƒqOWt|ƒdjo%t |t t ||ƒ|ƒƒ}nt|ƒdjo%t |t t ||ƒ|ƒƒ}n|||SdS(s€Returns a permutation which will sort a sequence. The sequence permute(row, order(row)) is sorted, contains each entry of row exactly as often as it appears in row and has the same length as row. See invert(), below, for discussion of what this implies when row is a permutation. If row has the form r@q, then p = order(row) is a permutation with the same length as q and makes r@q@p a sorted list with this same length, making q@p a useful replacement for q: it contains the same entries as q, but r@(q@p) is sorted. This is exploited in the recursive calls to order which model the qsort algorithm. iiiN( slensrowsnsrangespivotslowsmidshighscmpssignsappendspermutesorder(srowscmpssignsmidsnshighslowspivot((s)/home/eddy/.sys/py/study/maths/permute.pysorders(        %%cCsñt|ƒ}tg|}yHx*|djo|d}||||psiN(ssizesNonesselfslivesstepsrestartsranges_Iterator__row(sselfssize((s)/home/eddy/.sys/py/study/maths/permute.pys__init__hs   cCsr|o|ioT|dt|ƒ jot|iƒSn|dt|ƒ jot|iƒSqent|‚dS(Ns permutationsinverse(skeysselfsliveslenstuples_Iterator__rowsinvertsAttributeError(sselfskey((s)/home/eddy/.sys/py/study/maths/permute.pys __getattr__us cCs2|i otddƒ‚nt||iƒSdS(s(Apply current permutation to a sequence.s permutationsexhausted iteratorN(sselfslivesAttributeErrorspermutesseqs_Iterator__row(sselfsseq((s)/home/eddy/.sys/py/study/maths/permute.pyspermute|s cCsEy |`Wntj onXtt|iƒƒ|_d|_dS(Ni(sselfsstepsAttributeErrorsrangeslens_Iterator__rowslive(sself((s)/home/eddy/.sys/py/study/maths/permute.pysrestarts  cCs}t|iƒd}x;|djo|i|d|i|jo|d}qW|djot|_d„|_dSn|dt|iƒdf\}}x*|i||i|jo|d}q¡W|i||i|f\|i|<|i|“sN(slensselfs_Iterator__rowsisNoneslivesstepsj(sselfsisj((s)/home/eddy/.sys/py/study/maths/permute.pysstep‡s&,   #.# .(s__name__s __module__s__doc__s__init__s __getattr__spermutesrestartsstep(((s)/home/eddy/.sys/py/study/maths/permute.pysIteratorGs    N( s__doc__sTheorysunfixedspermutescomposescyclescmpsordersinvertssortedssortsIterator( ssortsunfixedscomposesTheorysIteratorsinvertspermutessortedsorderscycle((s)/home/eddy/.sys/py/study/maths/permute.pys?sjG