Converting a natural number to a permutation matrix in Python. How to speed it up perhaps avoiding messing around with lists, sets and dicts? It is something a bit complex to explain here, but the  code bellow takes a 128-bit number and converts it into a permutation matrix, a beast which I have already faced before. The matrix is represented as a list of numbers. Each number is a row. 
The way I've found to do the mapping number->matrix was to convert the number through a multi-radix (or something that could be considered one)  numeric system, so each digit corresponds to a row in the matrix. Since there can't be duplicate rows, some offset magic was needed (that is one of the uses of map taboo used below).
How could this code be improved regarding data structures and use of loops?
More conceptually, what about my choice of conversion through a multi-radix system?
Could it be simpler and still be a perfect mapping from naturals to permutation matrices?

ps. There are 2^128 numbers and 35! matrices.  2^128 &lt; 35! , So all numbers can have a unique corresponding matrix.

from sortedcontainers import SortedSet, SortedDict
def permutmatrix2int(m):
    """Convert permutation matrix 35x35 to number."""
    taboo = SortedSet()
    digits = []
    rowid = 34
    for bit in m[:-1]:
        bitold = bit
        for f in taboo:
            if bitold &gt;= f:
                bit -= 1
        taboo.add(bitold)
        digits.append(bit)
        rowid -= 1

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

    return big_number


def int2permutmatrix(big_number):
    """Convert number to permutation matrix 35x35."""
    taboo = SortedDict()
    res = big_number
    base = 35
    bit = 0
    while base &gt; 1:
        res, bit = divmod(res, base)
        if res + bit == 0:
            bit = 0
        for ta in taboo:
            if bit &gt;= ta:
                bit += 1
        base -= 1
        taboo[bit] = base

    for bit in range(35):
        if bit not in taboo:
            break
    taboo[bit] = base - 1

    return list(map(
        itemgetter(0), sorted(taboo.items(), reverse=True, key=itemgetter(1))
    ))
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)


?