Converting a natural number to a permutation matrix in Python. How to speed it up perhaps avoiding messing around with lists, sets and dicts?

Question

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 < 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 >= 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 > 1:
        res, bit = divmod(res, base)
        if res + bit == 0:
            bit = 0
        for ta in taboo:
            if bit >= 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))
    ))

Answer 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)

?

Answer 2

With a great help from a mathematician (at least in spirit) regarding permutations, factoradic and matrices, I could implement the following, which is 30 times faster.

I provide the opposite function as a bonus.

def pmatrix2int(m):
    """Convert permutation matrix to number."""
    return fac2int(pmatrix2fac(m))


def int2pmatrix(big_number):
    """Convert number to permutation matrix."""
    return fac2pmatrix((int2fac(big_number)))


def pmatrix2fac(matrix):
    """Convert permutation matrix to factoradic number."""
    available = list(range(len(matrix)))
    digits = []
    for row in matrix:
        idx = available.index(row)
        del available[idx]
        digits.append(idx)
    return list(reversed(digits))


def fac2pmatrix(digits):
    """Convert factoradic number to permutation matrix."""
    available = list(range(len(digits)))
    mat = []
    for digit in reversed(digits):
        # print(digit, available)
        mat.append(available.pop(digit))
    return mat


def int2fac(number):
    """Convert decimal into factorial numeric system. Left-most is LSB."""
    i = 2
    res = [0]
    while number > 0:
        number, r = divmod(number, i)
        res.append(r)
        i += 1
    return res


def fac2int(digits):
    """Convert factorial numeric system into decimal. Left-most is LSB."""
    radix = 1
    i = 1
    res = 0
    for digit in digits[1:]:
        res += digit * i
        radix += 1
        i *= radix
    return res