Converting a natural number to a permutation matrix in Python. How to speed it up perhaps avoiding messing around with lists, sets and dicts?
I haven't really tried to follow your code, but it sounds like you're complicating things unnecessarily by talking about "permutation matrices" instead of just "permutations." IIUC, it's trivial to get from a permutation matrix to a permutation or vice versa. The hard part is getting from an integer index ("give me the 42nd permutation of these elements") to the actual permutation.

So, the non-trivial functions you're looking for are

def nth_permutation(num_elements, which):
    [...]

def index_of_permutation(num_elements, which):
    [...]


The speedy algorithm for nth_permutation is described here (with C and PHP code)
and here in Python, although apparently the first version doesn't produce permutations in the traditional order and the second version is quadratic.



On your actual code, I'm confused by this passage:

    res, bit = divmod(res, base)
    if res + bit == 0:
        bit = 0


How can res + bit == 0, unless (res == 0) and (bit == 0)? But if (bit == 0), then it's redundant to assign bit = 0.



I also don't understand the significance of 35. Is it significant that there are 10+26-1 non-zero "digits" available in base 36? If 35 was picked completely at random, then you should really make it a parameter to the function. It'd be what I called num_elements in my signatures above.



Trivial nit: you forgot

from operator import itemgetter




big_number = digits[0]
pos = 0
base = b = 35
for digit in digits[1:]:
    big_number += b * digit
    pos += 1
    base -= 1
    b *= base


This looks suspiciously like "convert string to int." Is this essentially equivalent to

alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXY"
big_string = ''.join([alphabet[i] for i in digits])
big_number = int(big_string[::-1]], 35)


?