Just for Fun: Python Permutation Jumbles

[Anton Vredegoor]

On Thu, 31 Oct 2002 19:45:12 GMT, Alex Martelli <aleax at aleax.it>
wrote:

>Anton Vredegoor wrote:
>   ...
>> By the way, there are ways af generating permutations by index number
>> that do not have to go through the list of permutations in order to
>> return a specific permutation. This can be fast too, and it's more
>
>One simple (not necessarily fastest) way:
>
>def perm_given_index(alist, apermindex):
>    for i in range(len(alist)-1):
>        apermindex, j = divmod(apermindex, len(alist)-i)
>        alist[i], alist[i+j] = alist[i+j], alist[i]

Yes, very nice. maybe even better than using generators. Although
generators seem to be faster for small ranges.

>> practical to do it this way if the number of permutations is too big
>> to generate them all. Randomly choosing a bridge dealing is an example
>> of such a situation, although then a permutation with "multiple
>> occurences" is neccessary. There's also a solution for this specific
>
>I'm not sure what a permutation with "multiple occurrences" would be,
>nor, in particular, of why such a thing would be necessary for
>"randomly choosing a bridge deal" (a subject dear and near to my
>heart).  If you have a hypothetical pseudo-random number generator
>uniform in the range 1 to 52 factorial, perm_given_index would let
>you rearrange a bridge deck (passed in as argument alist) according
>to the random number (passed in as argument apermindex).

To get my mind out of some troubling issues concerning unemployment I
was programming permutations again today. I have a script at 

http://home.hccnet.nl/a.vredegoor/multiperm

but it's way to complicated and I am always trying to reduce it to
more managable proportions.

>
>Of course, there are fewer significantly-different bridge deals than
>there are permutations of a 52-cards deck -- a bridge player does not
>care, when the SET of spades he or she receives among his or her 13
>cards for the deal is e.g. Ace and Two, whether the Ace came before
>or after the Two, or what cards in other suits, if any, came in
>between.  The number of significantly-different bridge deals is thus
>C(52,13) times C(39,13) times C(26,13), 53644737765488792839237440000
>vs 80658175170943878571660636856403766975289505440883277824000000000000
>which is the number of permutations of the deck (52 factorial).

No, not 52! :-) but something less, as in the beginning of the
paragraph.

>But the _handiest_ way to deal a random deal, assuming for the sake
>of argument that you have a uniform real pseudorandom number generator
>u() [therefore you can just as easily generate U(N), uniform integer
>pseudorandom generators for any integer N] is still to deal the cards
>one by one just about as above:
>
>def random_deal(alist, U):
>    for i in range(len(alist)-1):
>        j = U(len(alist)-i)
>        alist[i], alist[i+j] = alist[i+j], alist[i]

I have a hardware TRNG that is perfectly able to generate long
integers in the desired range so it could be used to deal the cards at
once. This would be satisfying for even the most subtle bridge players
I think. Since it's integrated on a not so expensive motherboard it
could be interesting for bridge players to buy a MB and deal this way.

But it's not portable. I mean the hardware, the python driver for the
hardware could be portable in principle:
(windows only for now)

http://home.hccnet.nl/a.vredegoor/truerand

>Yes, there are faster ways (mostly because generating 51 pseudorandom
>numbers tends to be costly), but it's hard to beat this simplicity
>(always an important issue).  Generally the processing you want to do
>after dealing the deal swamps the effort of generating the deal itself,
>anyway (when the post-processing you want to do is _trivially_ simple,
>it may be preferable to computer whatever statistics you're after on
>the universe of ALL possible deals, than to generate a random sample
>and do some counting on the sample -- but that's another issue).

The script I mentioned above can also *rank* a given permutation so it
is possible this way to find out which (indexed number) card deal was
used for a specific game.

>> problem using set partitions but lets not bore the readers.
>> 
>> However it's almost certainly not so concise and elegant as using
>> generators to permute small ranges.
>
>Not sure what's "it" in this context, but if "it" is generating
>a permutation from a permutation-index, it seems concise and elegant
>enough to me in the version above...
>
 I am not sure too but I am including a script below that permutes the
"hands" instead of the cards. I also have somewhere (not ready yet now
to wrap my head around this again) a script that generates a partition
of the set of cards in four subsets and then does a permutation of the
hands to deal the cards. After all there are 24 ways of assigning the
hands after partitioning.

It's just for fun, but see below for something not so elegant as I
would like it to be ... Not tested thoroughly see the (longer) script
at my homepage for a more stable version.

Regards,
		Anton.

#multiperm.py by Anton Vredegoor anton at vredegoor.doge.nl 31-10-2002
"""
    Mperm returns all different permutations of a list
    by index. The list can contain the same element more
    than once.
"""

from operator import mul, add

def fac(n):
    #faculty of n
    return reduce(mul,range(2,n+1),1L)

def freqs(L):
    #dictionary of frequencies of the elements of list L
    res = {}
    for x in L:
        res[x]= res.get(x,0)+1 
    return res

def nperm(f):
    #tuple of (number of elements,number of possible permutations) 
    #for this dictionary of frequencies
    fv = f.values()
    n,np = 1,1
    if fv:
        n = reduce(add,fv)
        up = fac(n)
        down = reduce(mul,[fac(x) for x in fv]) 
        np = up/down
    return n,np	

def findfirst(index,L):
    #tuple of  
    #(number of permutations used,first element of the permutation)
    f = freqs(L)
    n,np = nperm(f)
    cum = 0
    k = f.keys()
    k.sort() # for sorted output
    for e in k:
        contr = (np*f[e])/n
        cum += contr
        if cum > index:
            return cum-contr,e

def mperm(index,L):
    #indexed *different* permutations of the list  L
    T = L[:]
    res = []
    remain = index
    while T:
        done, e = findfirst(remain,T)
        remain -= done
        res.append(e)
        T.remove(e)
    return res

def test():
    #tests  mperm
    L = range(3)
    #n == len(L),np==number of possible different permutations
    n,np = nperm(freqs(L))
    for i in range(np):
        print '%2i %s' %(i,mperm(i,L))
    print
    L = list("aabc")
    #n == len(L),np==number of possible different permutations
    n,np = nperm(freqs(L))
    for i in range(np):
        print '%2i %s' %(i,"".join(mperm(i,L)))
    print
    #deal some bridge cards
    L = list("0123" *13)
    #generate some (not) very random number ...
    r = 2L**95 
    hands = [[],[],[],[]]
    i = 0
    for c in mperm(r,L):
        #map this permutation to the four hands
        hands[int(c)].append(i)
        i+=1
    for hand in hands:
        print hand
    print

if __name__=='__main__':
    test()