Find the list of combination (with repetition) given rank and number of items. (Lexicographic ordering)

Question

The problem involves the fastest possible method to generate a list of combinations which repeats from all the possible combinations with repetition allowed. I know there needs to be a way to calculate n from gamma(n,r)=v given r and v in order to get the fastest possible approach, but it's probably not solvable, so to the realm of what we have now.

So, this means from a list of 3 items and maximum of 5 repetition, and rank, the list would look something like this:

Rank - Combinations

0 - 0,0,0,0,0
1 - 0,0,0,0,1
2 - 0,0,0,0,2
....
20 - 2,2,2,2,2

At the moment, my Python code to this problem:

import math

def calc_approximate_n(v,r):
    return max(r,int((v*math.factorial(r)-r)**(1/r)))

NUMBER_OF_ITEMS=3
REPETITIONS=5
DECREMENT_REPETITIONS=REPETITIONS-1
NUMBER_OF_COMBS=math.comb(NUMBER_OF_ITEMS+REPETITIONS-1,REPETITIONS)
MAX_COMB_RANK=NUMBER_OF_COMBS-1

rank=7
rank %= NUMBER_OF_COMBS
Tc=NUMBER_OF_ITEMS-1

if rank==0:
    print([0]*REPETITIONS)
elif rank==MAX_COMB_RANK:
    print([Tc]*REPETITIONS)
elif rank<NUMBER_OF_ITEMS:
    output_list=[0]*REPETITIONS
    output_list[-1]=rank
    print(output_list)
else:
    output_list=[0]*REPETITIONS
    
    while True:
        Tn=calc_approximate_n(rank,Tc)
        FTn=Tn-Tc+1
        last_n=math.comb(Tn,Tc)
        ncr_val=last_n
        
        while ncr_val<rank:
            Tn += 1
            ncr_val=math.comb(Tn,Tc)
            if ncr_val<=rank:
                last_n=ncr_val
                FTn += 1
        
        rank -= last_n
        Tc -= 1
        insertion_pos=DECREMENT_REPETITIONS
        
        for _ in range(FTn):
            output_list[insertion_pos] += 1
            insertion_pos -= 1
            
        if rank==0 or Tc==0:
            break
    
    print(output_list)

So, with 3 items and maximum repetition of 5 and rank 7, I get this combination => [0, 0, 1, 1, 2]

Now, with 5 items, and maximum repetition of 12 and rank 1700, I get this combination => [1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4]

Answer 1

First Take

Your code gets the job done and is correct as far as I can tell. It would be more convenient if it was converted to a function. I have taken the liberty to do so as follow:

import math

def calc_approximate_n(v,r):
    return max(r,int((v*math.factorial(r)-r)**(1/r)))


def unrank(NUMBER_OF_ITEMS, REPETITIONS, rank):

    DECREMENT_REPETITIONS=REPETITIONS-1
    NUMBER_OF_COMBS=math.comb(NUMBER_OF_ITEMS+REPETITIONS-1,REPETITIONS)
    MAX_COMB_RANK=NUMBER_OF_COMBS-1

    rank %= NUMBER_OF_COMBS
    Tc=NUMBER_OF_ITEMS-1
.
.
.

    # Add returns as well

And put it in a file called unrank_comb.py. So now the user can do the following in the console or script:

import unrank_comb as urc

urc.unrank(5, 12, 1700)
[1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4]

Code Style

Your code could be improved with more consistent spacing, especially around variable assignment. When I run pycodestyle on your code I get many departures from PEP8 standards:

% pycodestyle unrank_comb.py    
unrank_comb.py:3:1: E302 expected 2 blank lines, found 1
unrank_comb.py:3:25: E231 missing whitespace after ','
unrank_comb.py:4:17: E231 missing whitespace after ','
.
.
.
unrank_comb.py:48:20: E225 missing whitespace around operator
unrank_comb.py:48:29: E225 missing whitespace around operator
unrank_comb.py:50:1: W293 blank line contains whitespace

If this was the only function in your script/library, then I would add a bunch of sanitizing checks to ensure the code will run properly. I'm assuming all of this is taken care of outside of this function so I will skip this part.

Efficiency

We can speed up your code quite a bit by avoiding calls to math.comb using a little algebra.

For unranking, we will have to do the following tasks multiple times:

1. Start with \$ {n + r - 1 \choose r} = \frac{(n + r - 1)!}{r! \cdot (n - 1)!} \$
2. Then we want to calculate \$ {n + r - 2 \choose r} = \frac{(n + r - 2)!}{r! \cdot (n - 2)!} \$

In order to avoid the second call to math.comb we can do the following:

1. \$ \frac{(n + r - 1)!}{r \cdot (n - 1)!} \cdot (n - 1) = \frac{(n + r - 1)!}{r \cdot (n - 2)!}\$
2. \$ \frac{(n + r - 1)!}{r \cdot (n - 2)! \cdot (n + r - 1)} = \frac{(n + r - 2)!}{r! \cdot (n - 2)!} \$

We see that instead of calling math.comb a second time, we simply multiply the previous result by n - 1 and then divide by n + r - 2.

The code below is a simple implementation that does just that:

def unrank_fast(n, r, rank):
    '''
    Returns the lexicographic combination with repetition of n items of
    length r corresponding to a given rank.

        Parameters:
            n (int): The number of items
            r (int): The length of the combination
            rank (int): The nth lexicographic result


        Returns:
            output_list (list): A list of integers
    '''

    output_list = [0] * r
    temp = int(math.comb(n + r - 2, r - 1))

    r -= 1
    j = 0

    for k in range(r + 1):
        while temp <= rank:
            rank -= temp
            temp *= (n - 1)
            temp //= (n + r - 1)
            n -= 1
            j += 1

        temp *= r

        if n + r > 2:
            temp //= (n + r - 1)

        output_list[k] = j
        r -= 1

    return output_list

It is quite fast. Observe the following:

import timeit

timeit.timeit("urc.unrank(20, 200, 782090539377703617347883590)", "import unrank_comb as urc", number = 10000)
1.774310542000002

timeit.timeit("urc.unrank_fast(20, 200, 782090539377703617347883590)", "import unrank_comb as urc", number = 10000)
0.2731890419999985

Over 6x faster! It gives the correct results as well.

import itertools as it
import unrank_comb as urc

combs_it = [list(cmb) for cmb in it.combinations_with_replacement(range(5), 12)]

combs_fast = []
combs_op = []

for k in range(1820):
    combs_fast.append(urc.unrank_fast(5, 12, k))
    combs_op.append(urc.unrank(5, 12, k)) 

combs_op == combs_it
True

combs_fast == combs_it
True