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

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]

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