Permutation with repetition algorithm needed

From: Emir Palandi (emirpalandi_at_pop.com.br)
Date: 09/08/04 

Date: 7 Sep 2004 18:09:45 -0700

Given an arbitrary permutation of n distinct numbers, I know how to
map it to a unique number within the range (0, ..., n! - 1). I know
also how to do the inverse: given a number between (0, ..., n! - 1),
construct the corresponding permutation.

Does someone know of an algorithm to do this for permutations with
repetitions?

Suppose, for example, that I have m distinct numbers, each one
repeated r_k times, 1 <= k <= m.

Now
     m
n = Sum r_k
    k=1

and let
       m
p = Product r_k!
      k=1

Then the desired range is (0, ..., n!/p - 1).

Thanks in advance.

Relevant Pages

  • Some PERL code for detecting/displaying "toroidal" trees "invariant under a half-turn
    ... This algorithm will be reviewed by Dr. David Wagner ... Such trees can be termed "invariant" under a half-turn ... not display "the same" oDAG as the first, ... and detects whether this permutation will yield a tree ...
    (sci.math.num-analysis)
  • Re: Challenae question for mathematician
    ... problems relating to permutation groups. ... adjacent books. ... called "bubble sort" - it is a quadratic time algorithm, ... efficient as a sorting method - efficient sorting is O. ...
    (sci.math)
  • Some PERL code for detecting/displaying "toroidal" trees " invariant under a half-tur
    ... This algorithm will be reviewed by Dr. David Wagner ... "oDAGs " invariant under a half-turn. ... Such trees can be termed "invariant" under a half-turn ... and detects whether this permutation will yield a tree ...
    (sci.math)
  • Imperfect random permutation of 2^k elements
    ... given that one has available the Algorithm P of ... from the given random bit sequence real-valued random numbers ... to any other permutation by applying to it a certain permutation ... It may be noted that the dynamically varying S-box of RC4 is ...
    (sci.crypt)
  • Re: permutations and combinations
    ... > Right now I'm using a string, sorting it and passing it repeated into ... In this article he defines a generic algorithm: ... for_each_permutation calls fn for each permutation of last-first items ... The printing functor keeps a simple state which is just the line number. ...
    (comp.lang.cpp)