Just for Fun: Python Permutation Jumbles

[Alex Martelli]

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]

> 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).

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).

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]

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).

> 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...


Alex