[Python] How do I get turn a permutation into an index (and back) in a context where there is...

The problem


Let's say you have 4 red balls, 2 blue balls and 1 green ball. That is 7 balls, and considering a ball can't be distinguished from another if it has the exact same color, this makes for a total of (7!)/(4!2!1!) = 105 possible permutations (Source).

Meaning, say we associate red with 0, blue with 1 and green with 2, there are 105 ways to arrange the [0, 0, 0, 0, 1, 1, 2] array.

More generally, this can be seen as n balls, m ball types, and nₖ balls of type k with 1 <= k <= m and (n₁+n₂+...+nₖ) = n, having (n!)/(n₁!*n₂!*...*nₖ!) possible permutations.

I need an algorithm that can get a unique number from a given permutated array, and get this permutated array back from that exact, same, unique number (also refered to as index).

Constraints

• 
  The number, in the case of the given example, must be a value between 0 and (n!)/(n₁!*n₂!*...*nₖ!) - 1.
  
  With the example I've given, this would be between 0 and 104.
  
  
• 
  The algorithm must not require calculating all possible permutations.
  
  While I'm taking an easy example with 105 permutations here, I'd like this to be usable for something that could have 30 trillions of them, which we obviously can't possibly all calculate, so your algorithm's complexity very much matters here.
  
  
• 
  Please, do not solely rely on libraries. I need the algorithm, not magic.
  
  Using libraries for basic structures like lists is fine, but a magic function from an existing library that's a bajillion lines long and lost in some gigantic codebase that does all the job is not fine.
  
  Since I'm looking for the algorithm here, it needs to be understandable and theoratically rewritable in any language, hence this constraint.
  

Allowed


I've tagged this question javascript and python, but really, I'm fine with any type-C language, including but not limited to TypeScript, C++, Java, C#, PHP. Even pseudocode is fine.

I don't care about the order of the permutations, the only thing that matters is that you can get a unique index from each one, and get the permutation back from its index.

This isn't a duplicate of:

• 
  Fast permutation -> number -> permutation mapping algorithms
  
  How can I generate all permutations of length n from a set of k elements?
  
  How to find the index of a k-permutation from n elements?
  
  Generate one permutation from an index
  
  These questions only feature arrays where there is one of each permutable element (meaning n! possible permutations for an array of size n). I want the possibility to have an individual, fixed, >1 amount of each element (significantly reducing the number of possible permutations for that same array of size n if some elements are present multiple times).
  
  
• 
  Coding the mathematical approach for finding index of a permutation that has repetition
  
  While this question features the possibility of having multiple of one element, it's not a fixed amount per element, significantly increasing the number of possible permutations
  
  
• 
  Generate permutations of indices of identical items
  
  This question asks to generate every single possible permutation, which I want to avoid (as with huge arrays, it would be too much to compute), and its answer even uses a library for this.
  
  
• 
  Find the index of a given permutation in the sorted list of the permutations of a given string
  
  This question does not account for duplicate elements. There will be some permutations that will be obtainable from multiple indices, which is not what I'm looking for. Additionally, the answer provided does not include a way to go back from an index to a permutation, only the other way around.
  

Considering all of these questions are on SO, and that I'm asking for a software algorithm, I'm assuming this is on-topic. Please don't redirect me to Math.SE, I need code, not lone formulas. If think this is still off-topic, please explain how so and I'll edit the question accordingly.

Footnotes


Bonus points if you can explain the algorithm, provide your reasoning and/or sources for formulas, and give the complexity of the algorithm. Just working code is also fine, though.

Continue reading...