Convert a recursive python code to a non-recursive version

Question

The code provided here works unless we start to increase the distinct and n-symbols and length, for example, on my computer n_symbols=512, length=512, distinct=300 ends up with this error RecursionError: maximum recursion depth exceeded in comparison and then overflow errors if I increase the lru_cache value.
What I want is to have a non-recursive version of this code.

from functools import lru_cache
@lru_cache
def get_permutations_count(n_symbols, length, distinct, used=0):
    '''
     - n_symbols: number of symbols in the alphabet
     - length: the number of symbols in each sequence
     - distinct: the number of distinct symbols in each sequence
    '''
    if distinct < 0:
        return 0
    if length == 0:
        return 1 if distinct == 0 else 0
    else:
        return \
          get_permutations_count(n_symbols, length-1, distinct-0, used+0) * used + \
          get_permutations_count(n_symbols, length-1, distinct-1, used+1) * (n_symbols - used)

Then

get_permutations_count(n_symbols=300, length=300, distinct=270)

runs in ~0.5 second giving the answer

2729511887951350984580070745513114266766906881300774347439917775
7093985721949669285469996223829969654724957176705978029888262889
8157939885553971500652353177628564896814078569667364402373549268
5524290993833663948683375995196081654415976659499171897405039547
1546236260377859451955180752885715923847446106509971875543496023
2494854876774756172488117802642800540206851318332940739395445903
6305051887120804168979339693187702655904071331731936748927759927
3688881301614948043182289382736687065840703041231428800720854767
0713406956719647313048146023960093662879015837313428567467555885
3564982943420444850950866922223974844727296000000000000000000000
000000000000000000000000000000000000000000000000

What does "overflow errors if I increase the lru_cache value" mean? — Pychopath
– Pychopath, Commented Feb 18, 2022 at 8:55
Can you write it in closed form, calling math.factorial and math.comb or math.perm? It'll be very fast. Otherwise, turning a recursive function into an iterative one requires pushing and popping values on a list instead of the stack. — Jerry101
– Jerry101, Commented Feb 18, 2022 at 8:58
What is it that this is computing? The function name includes the word "permutations", but it doesn't seem to be about permutations. — Pychopath
– Pychopath, Commented Feb 18, 2022 at 9:02

Pychopath · Accepted Answer · 2022-02-18 11:18:39Z

4

+100

Here's mine:

def get_permutations_count_improved(n_symbols, length, distinct):
    if distinct > length or distinct > n_symbols:
        return 0
    ways = [1]
    for _ in range(length):
        ways = [used * (distinct - d) + new
               for d, used, new in zip(range(distinct+1), [*ways, 0], [0, *ways])]
    return ways[distinct] * comb(n_symbols, distinct) * factorial(distinct)

Speed comparison for some argument sets:

n_symbols length distinct   yours    mine
   300      300    270      0.62 s   0.012 s (~51 times faster)
   512      512    300        -      0.035 s
  1024     1024    600        -      0.22 s
  3000     3000   2700        -      6.0 s

In my last line you see I split the overall result into three factors:

comb(n_symbols, distinct) for choosing which distinct out of the n_symbols symbols actually get used. That essentially gets rid of the n_symbols parameter, or think of it as compensating setting n_symbols = distinct.
factorial(distinct) for the order in which the symbols get used first. This gets rid of the * (n_symbols - used) in your recurrence.
ways[distinct] is the number of ways to build a sequence of length length with exactly distinct distinct symbols, where the order in which they get used first is fixed.

It might be easier to think of the ways table as two-dimensional: ways[length][distinct]. But for more memory-efficiency, I compute it row by row and only keep the latest row.

Benchmark and some correctness checks (Try it online!):

from timeit import timeit
from functools import lru_cache
from math import comb, factorial

@lru_cache
def get_permutations_count(n_symbols, length, distinct, used=0):
    '''
     - n_symbols: number of symbols in the alphabet
     - length: the number of symbols in each sequence
     - distinct: the number of distinct symbols in each sequence
    '''
    if distinct < 0:
        return 0
    if length == 0:
        return 1 if distinct == 0 else 0
    else:
        return \
          get_permutations_count(n_symbols, length-1, distinct-0, used+0) * used + \
          get_permutations_count(n_symbols, length-1, distinct-1, used+1) * (n_symbols - used)

def get_permutations_count_improved(n_symbols, length, distinct):
    if distinct > length or distinct > n_symbols:
        return 0
    ways = [1]
    for _ in range(length):
        ways = [used * (distinct - d) + new
               for d, used, new in zip(range(distinct+1), [*ways, 0], [0, *ways])]
    return ways[distinct] * comb(n_symbols, distinct) * factorial(distinct)

funcs = get_permutations_count, get_permutations_count_improved

# Check correctness
stop = 20
for a in range(stop):
    for b in range(stop):
        for c in range(stop):
            expect = get_permutations_count(a, b, c)
            result = get_permutations_count_improved(a, b, c)
            assert result == expect, (a, b, c, expect, result)

# Benchmark
n_symbols, length, distinct = 300, 300, 270
#n_symbols, length, distinct = 512, 512, 300
#n_symbols, length, distinct = 1024, 1024, 600
#n_symbols, length, distinct = 3000, 3000, 2700
for func in funcs[0:] * 3:
    funcs[0].cache_clear()
    t = timeit(lambda: func(n_symbols, length, distinct), number=1)
    print('%.3f seconds ' % t, func.__name__)

edited Feb 18, 2022 at 11:18

answered Feb 18, 2022 at 10:52

Pychopath

1,5803 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Eftekhari Over a year ago

Thank you. I'll give it a bounty.

Bob Over a year ago

Welcome @Pychopath, that was a very good answer :)

Pychopath Over a year ago

@Bob You wrote the solution in this question, right? Thanks for that, partly because it made the task fairly easy to understand, easier than the earlier question you wrote it for :-)

Bob Over a year ago

Yes It was me @Pychopath it was me, I even provided an iterative here, but the idea there was to give the complete table of counts, to used by other mehods, I recognize two differences in your implementation. You are not iterating over the zeros, building a triangular matrix. You add new instead of new * d and then you leave the multiplications to be performed in the end. This is good because all the intermediate values are smaller, thus, faster.

Eftekhari Over a year ago

@Pychopath Could you help with this question? >> stackoverflow.com/questions/71207863/…

|

Collectives™ on Stack Overflow

Convert a recursive python code to a non-recursive version

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related