Re: Enumerating Permutations
- To: mathgroup at smc.vnet.net
- Subject: [mg20038] Re: [mg20006] Enumerating Permutations
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Sat, 25 Sep 1999 18:46:05 -0400
- Sender: owner-wri-mathgroup at wolfram.com
I must admit I can't really understand what you want. What do you mean by
the n-th permutation of a group T? Do you mean you have a subgroup of the
symmetric group on 7 elements and want to rank its elements? Or are you
talking about ranking all the permutations (in other words elements of the
whole symmetric group)?
As for the latter: such a function, using lexicographic ranking, already
exists in the Combinatorica package. You load in that package with:
In[1]:=
<< Discretemath`Combinatorica`
then
In[2]:=
?NthPermutation
"NthPermutation[n, l] gives the nth lexicographic permutation of list l."
For example:
In[3]:=
NthPermutation[3, {a, b, c, d}]
Out[3]=
{a, c, d, b}
The algorithm that does this is the obvious one. I can describe it in words
if you really want it but it is better to just look at the code in the
Combinatorica package.
If on the other hand you want to rank the element sof some subgroup of the
symmetric group you can do this as follows: first sort them using their
ranking in the whole symmetric group as your sorting function and then rank
them using their index in the list you get in this way.
Finally if you have something else in mind you have to find some way to
explain it better or perhaps someone else will show better empathy than me.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp
http://eri2.tuins.ac.jp
----------
>From: "Vic Fanberg" <fanberg at email.msn.com>
To: mathgroup at smc.vnet.net
>To: mathgroup at smc.vnet.net
>Subject: [mg20038] [mg20006] Enumerating Permutations
>Date: Sat, Sep 25, 1999, 3:40 PM
>
> I am looking for an algorithm for determining the Nth permutation (P) of a
> group T. I don't really care the ordering of the permutations within T, as
> long as all the permutations of P are members of T exactly once. (Each
> element of the permutation P is unique.)
>
> Actually, each of the permutations are only 7 digits long and I could list
> all 5040 permutations in a file about 35K, but I was hoping for something a
> little cleaner, in case I change to 8 or 9 digits long later.
>
> Does anyone know of such an algorithm?
>
> Sorry I don't have the math background to phrase the question any better.
> But I would very much appreciate any help or references you can point me to.
>
> Vic
>
>
>
>
>